Всем добрый вечер. Надеюсь обращаюсь туда)
Суть проблемы, к сожалению у меня некоторые проблемы с созданием скриптов (мозг не так заточен), не могу написать скрипт на алгоритм. Алгоритм бинарного поиска, с поиском ключа.
Как пример>
есть ряд чисел {2,4,5,6,8,10,12,14,16,17,18,20,22,24,25,27,28,30,31} Ключ=16
Метод основан на выделении центра этого множества, или массив, кому как угодно.
формулы:
Ц(центр)=[n/2]+1 если множество нечётное
Ц=[n/2] если множество чётное
n=количество чисел в множестве, в данном случае n=19 нечётно
решение
1. Ц=[19/2]+1=10
сравниваем с ключом
K10~K
17~16 » множество разделилось, идём в левую половину
{2,4,5,6,8,10,12,14,16,}
2. Ц=[9/2]+1=5
K5~K
8~16 » вправо
{10,12,14,16}
3. Ц=[4/2]+1=3
K3~K (на самом деле K8)
14~16 »вправо
{16}
4. Ц=ключ остался один соответвенно Ц=1
K1~K (K9)
16~16 »ключ найден
З.ы. ЭТО ТОЛЬКО ПРИМЕР ЗАДАЧИ НА АЛГОРИТМ!
Кто может помочь в данном вопросе?:D И помочь с осуществлением скрипта, если честно то скриптов то много, но к сожалению они довольно часто высокого уровня и мудрённости + во многих присутствует команда процедуры (Procedure) которая меня уже достала, ибо с моим TP7.1 она всегда конфликтит, что-то не нравиться.
З.з.ы если кто-то рискнёт помочь, отчёт не должен быть столь ясным, должен быть ввод чисел, ключа(кстати если его нет то соответсвенно ответ что ключа нет).
просто вычисление чентра, сравнение ключа и в какую сторону множества переходим))
Всем спасибо за внимание.
Sardukar, не совсем понятно изъясняешься. Что ты называешь скриптом? Программу на Паскале?.. Если да, то, извини, впервые такое слышу.. Замечательный способ сбить отвечающих с толку!
А если нет - тогда что? и почему в разделе Паскаль? и какие могут быть у ТР7.1 проблемы с процедурами??..
Поясни, пожалуйста, а то неясно, как отвечать тебе.
Извиняюь если намудрил, всегда так выходит)
Для меня скрипт..ну тут скорее программа в данном случае нечто такое:
program pascaltask;
uses crt;
const N=чемунить;
var
a,b,c: integer;
x: array [1..N] of integer;
begin
writeln('сама исполняемая программа...ну или код, кто как понимает');
end.
Procedure Puzirek;
Var i, j: Integer;
y:Integer;
Begin
For i := 2 to n do
For j := n downto i do
If X[j-1] > X[j] then begin y:=X[j-1];
X[j-1]:=X[j];
X[j]:=y
end;
End;
function BSearch (item: DataArray; count:integer;
key:DataItem):integer;
var
low, high, mid: integer;
found:boolean;
begin
low:=1; high:=count;
found:=false; { не найден }
while (low<=high) and (not found) do
begin
mid:=(low+high) div 2;
if key<item[mid] then high:=mid-1
else if key>item[mid] then low:=mid+1
else found:=true; { найден }
end;
if found then BSearch:=mid
else BSearch:=0; { не найден }
end; { конец поиска }
For Гость
мда, пару раз замечал что к данным 2 выражениям применяют команду type смысл которых не понял, в данном случае их не дали...хотя, возможно что этого куска нехватает
type
DataItem = char;
DataArray = array [1..80] of char;
program Puzirek;
uses crt;
Var i, j: Integer;
y:Integer;
Begin
For i := 2 to n do
For j := n downto i do
If X[j-1] > X[j] then begin y:=X[j-1];
X[j-1]:=X[j];
X[j]:=y
end;
end.
type
DataItem = char;
DataArray = array [1..N] of char;
program pascaltask;
uses crt;
const N=чемунить;
keyval = значение ключа;
type
DataItem = integer;
DataArray = array [1..N] of integer;
var
i , key, positionOFkey : DataItem ;
x: DataArray;
function BSearch (item: DataArray; count:integer;
key:DataItem):integer;
var
low, high, mid: integer;
found:boolean;
begin
low:=1; high:=count;
found:=false; { не найден }
while (low<=high) and (not found) do
begin
mid:=(low+high) div 2;
if key<item[mid] then high:=mid-1
else if key>item[mid] then low:=mid+1
else found:=true; { найден }
end;
if found then BSearch:=mid
else BSearch:=0; { не найден }
end; { конец поиска }
begin
randomize;
for i := 1 to N do
DataArray[i] := Random (какое-то число) ;
key := keyval ;
positionOFkey := BSearch (x, key);
writeln('ну и обработчик вывода');
end.
<..>, как говорят наши американские братья. Как написано выше параметр count из процедуры можно удалить. Вместо него использовать константу N. Если не удалять, то в основной программе должна присутствовать еще одна переменная, котоой присвоено значение N и которую передавать в процедуру.
Спасибо за приведёный пример...постараюсь понять) Кстати, есть ли в сети нормальные мануалы, я к сожалению наткнулся только на один когдато, к сожалению удалил ссылку.
По книжке, стоилобы, но дело в том что, времени нема, работу сдать надо с блок схемой теорией бинарного поиска его сути и т.д., листинг, работающая программа. По сути задание было вообще такое-БДЗ-любой алгоритм сортировки или поиска что изучали на любом языке. Учитывая что мы прошли только TurboPascal, Delphi в инсте вообще не пашет почему-то и учитывая что прошли материал который на самом деле за 1-3 дня можно выучить, выходит что группа вообще включая меня нихрена не понимает как правильно писать и работать в этой программе. + тема ко времени, еслибы было известно ранее что будет, купилбы, а задание дали перед сессией, когда и так перегруз( Вот такие пироги.
Эмм.. по 1 пункту не понял по второму...тоесть скажем у нас const = 9, и надо вводить не рандомно а именно по возрастанию или как? 1 3 7 9 11 12 13 14 15 19 20 25 и т.д. так?
В несортированном массиве метод бинарного поиска вообще работать не будет, т.к. это все равно, что тыкать пальцем в небо.
Т.е. с рандомайзом , конечно, погорячился.
Если задан сортированный массив, то программу, конечно, надо будет переписать с заданием сортированного массива в разделе описания констант, например. Если исходный массив несортированный, то можно посмотреть топики, например, про бинарные деревья поиска.
Идея бинарного поиска - в разбиении исходной последовательности для сокращения количества переборов. См. топики про быстрые сортировки.
ПС. Исправить очевидные ошибки.
ППС. Алгоритмы и реализации можно посмотреть в ФАКе.
program binPoisk;
uses crt;
const N=5;
var
i, p, q, s, b, t, POK, count: integer;
X: array [1..N] of integer;
{=====================================================}
procedure puzirek;
var
i, j, y: integer;
begin
for i:= 2 to n do
for j:= n downto i do
if X[j-1] > X[j] then
begin
y:=X[j-1];
X[j-1]:=X[j];
X[j]:=y
end;
end;
{=====================================================}
procedure BSearch;
var
low, high, mid: integer;
found:boolean;
begin
low:=1; high:=count;
found:=false;
while (low<=high) and (not found) do
begin
mid:=(low+high) div 2;
if b<X[mid] then high:=mid-1
else if b>X[mid] then low:=mid+1
else found:=true;
end;
if found then BSearch:=mid {Злостно ругается что тут не : а ; должна быть}
else BSearch:=0;
end;
{=====================================================}
begin
clrscr;
writeln('Vvodim ',N,'elementov massiva X');
for i:=1 to N do
read(X[i]);
writeln('Ne sortirovanii massive X');
for i:=1 to N do
write(X[i],' ');
writeln;
puzirek;
writeln('Otsortirovanii massive X');
for i:=1 to N do
write(X[i],' ');
writeln;
writeln('Vvedite iskomii klu4');
read(b);
POK:= BSearch (X, b);
readln;
end.
Спасибо за помощь, но разобрался всё таки сам.
Закрывайте тему.