Задача по методу бинарного поиска., Нужна помощь. Опции

[Sardukar]

Всем добрый вечер. Надеюсь обращаюсь туда)
Суть проблемы, к сожалению у меня некоторые проблемы с созданием скриптов (мозг не так заточен), не могу написать скрипт на алгоритм. Алгоритм бинарного поиска, с поиском ключа.
Как пример>
есть ряд чисел {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 - 28.11.2007 2:20

[Lapp]

Sardukar, не совсем понятно изъясняешься. Что ты называешь скриптом? Программу на Паскале?.. Если да, то, извини, впервые такое слышу.. Замечательный способ сбить отвечающих с толку!
А если нет - тогда что? и почему в разделе Паскаль? и какие могут быть у ТР7.1 проблемы с процедурами??..

Поясни, пожалуйста, а то неясно, как отвечать тебе.

[Sardukar]

Извиняюь если намудрил, всегда так выходит)
Для меня скрипт..ну тут скорее программа в данном случае нечто такое:

program pascaltask;
uses crt;
const N=чемунить;
var
a,b,c: integer;
x: array  [1..N] of integer;
begin
writeln('сама исполняемая программа...ну или код, кто как понимает');
end.

Эм, ну я не вижу иных разделов для публикации этого вопроса. К сожалению разницу между просто Pascal или TurboPascal я не особо улавливаю)

по процедурам, трудно сказать. Часто встречал программы которые схожи с тем что искал, но там присутствует сея процедура.

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; { конец поиска }

Tp у меня ругался по началу вообще не ясными вещами, я решил то что в скобке в функции, перенести под var, тогда tp стал ругаться что вообще за переменные item: DataArray и key: DataItem.
З.ы. вот такая вот фигня) код впринципе есть но понимание как его переделать чтоб работал-ноль.

[Гость]

тогда tp стал ругаться что вообще за переменные item: DataArray и key: DataItem.

Я бы сказал, проблема в типах, а не в переменных... Ты ж не описал, что такое DataArray и DataItem (по крайней мере не показал этого нам), а уже пытаешься использовать...

А по поводу пузырька... Что за привычка - давать КУСКИ кода, можно объяснить? Хочешь, я тебе скажу, что вот именно тот код (вообще без изменений), который ты привел выше (как процедуру Puzirek), правильно вставленный в программу, отработает прекрасно? Тебе это поможет? Показывай, как вызываешь, а не приводи ничего не значащие фрагменты кода...

[Lapp]

Извиняюь если намудрил, всегда так выходит)

Неплохой комплимент самому себе..

Для меня скрипт..ну тут скорее программа в данном случае нечто такое:

Вот и славно, на языке картинок мы смогли договориться. И все же рекомендую использовать принятую терминологию. Согласно ей скриптами называют обычно тексты на я зыках более высокого уровня, чем Паскаль или С (например, юниксовый shell или php). Есть еще одна разница: скриты не компилируются. Они выполняются непосредственно по тексту. Паскалевский текст требует компиляции.

К сожалению разницу между просто Pascal или TurboPascal я не особо улавливаю)

Разница примерно такая же, как между рисунком дома (или, скажем, его проектом) и самим домом. Заметь, что в доме всегда могут быть отличия от проекта. А если это типовой проект, то в каждом доме, построенном по нему, будут отличия как от проекта, так и между домами.

ТР - это реализация Паскаля, так же как FPC, ABC, TMT, GNU, Delphy.. В реализацию, как правило, входят и библиотеки.

[Sardukar]

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.

Зы, исходник потерял, нету данных по переменной "n X". Как видишь, ПРАВИЛЬНО вставлять в программу я не умею эти скрипты) Если научишь уму, буду благодарен.

To Lapp
2. иногда путаю термины. Для меня скрипт это html/css код страницы. В то время как программа, это конкретный файл запускаемый, или код программы, которые в последствии можно запустить.
3. Тоесть можно сказать что от Pascal уже пошёл Turbo Pascal и т.д.?

[Гость]

type
    DataItem = char;
    DataArray = array [1..N] of char;

Раз у Вас работа с числами, то поменять тип данных на integer

Параметр count из процедуры BSearch можно удалить. Верхняя граница у Вас будет N. Иначе непонятна цель ввода в процедуру этой константы.

В отделе объявления переменных X станет типа DataArray.

Процедура должна быть объявлена в разделе объявлений, например после объявления переменных. В теле программы должен идти ее вызов. Естесственно, после набивания исходного массива значениями.
Что-то типа вот такого.

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.

Чесгря, RTFM. В смысле, а не стОит ли купить и почитать книжку по синтаксису языка?
Я, конечно, понимаю, что для специалиста важнее знать алгоритмы, чем реализации языка. Но. Хоть какое-то базовое представление о языке, на котором пишешь, имеет смысл иметь.

3. Тоесть можно сказать что от Pascal уже пошёл Turbo Pascal и т.д.?

TP - это реализация Паскаля от фирмы Борланд.

[Гость]

<..>, как говорят наши американские братья. Как написано выше параметр count из процедуры можно удалить. Вместо него использовать константу N. Если не удалять, то в основной программе должна присутствовать еще одна переменная, котоой присвоено значение N и которую передавать в процедуру.


Сообщение отредактировано: Lapp - 28.11.2007 19:47

[Sardukar]

Спасибо за приведёный пример...постараюсь понять) Кстати, есть ли в сети нормальные мануалы, я к сожалению наткнулся только на один когдато, к сожалению удалил ссылку.

По книжке, стоилобы, но дело в том что, времени нема, работу сдать надо с блок схемой теорией бинарного поиска его сути и т.д., листинг, работающая программа. По сути задание было вообще такое-БДЗ-любой алгоритм сортировки или поиска что изучали на любом языке. Учитывая что мы прошли только TurboPascal, Delphi в инсте вообще не пашет почему-то и учитывая что прошли материал который на самом деле за 1-3 дня можно выучить, выходит что группа вообще включая меня нихрена не понимает как правильно писать и работать в этой программе. + тема ко времени, еслибы было известно ранее что будет, купилбы, а задание дали перед сессией, когда и так перегруз( Вот такие пироги.

[volvo]

Чесгря, RTFM.

Честно говоря, тебе бы тоже почитать азбуку не мешало... Я про то, что присваивать значения ТИПУ - это надо догадаться такое сделать... Это первое... Второе - мелочи, конечно, но ты ж тут начала посылать всех RTFM, так получаешь по полной - у тебя вызов BSearch с некорректным числом параметров (сказал А - говори и Б, для этого совсем не обязательно вводить новую переменную, достаточно передать собственно N)...

Ну, и это - не самое главное... Самое главное - что BSearch будет искать правильно только в упорядоченном массиве. О чем ты успешно умолчал. Если знал, конечно

[Sardukar]

Эмм.. по 1 пункту не понял по второму...тоесть скажем у нас const = 9, и надо вводить не рандомно а именно по возрастанию или как? 1 3 7 9 11 12 13 14 15 19 20 25 и т.д. так?

[Гость]

В несортированном массиве метод бинарного поиска вообще работать не будет, т.к. это все равно, что тыкать пальцем в небо.

Т.е. с рандомайзом , конечно, погорячился.

Если задан сортированный массив, то программу, конечно, надо будет переписать с заданием сортированного массива в разделе описания констант, например. Если исходный массив несортированный, то можно посмотреть топики, например, про бинарные деревья поиска.

Идея бинарного поиска - в разбиении исходной последовательности для сокращения количества переборов. См. топики про быстрые сортировки.

ПС. Исправить очевидные ошибки.
ППС. Алгоритмы и реализации можно посмотреть в ФАКе.

[Гость]

Эмм.. по 1 пункту не понял по второму...тоесть скажем у нас const = 9, и надо вводить не рандомно а именно по возрастанию или как? 1 3 7 9 11 12 13 14 15 19 20 25 и т.д. так?

Да. Или задать массив изначально в разделе констант. Во втором случае появится 2 раздела описания констант: один для n, второй для исходного массива. (только не забывайте, что константе впоследствии нельзя присвоить значение).
что-то вроде:

const
x : DataArray = (1,2,3,4,5,6,7,8,9)

Иначе массив надо сначала отсортировать.

Для выполнения единичного поиска - это, вообще говоря, бессмысленная операция, т.к. сама сортировка предполагает перебор всех элементов исходного массива.

ПС. Попробуйте задание массива в разделе констант, если прокатит Это проще, чем разбираться с деревьями и прочими сортировками.
ППС. В инете попробуйте в поисковике набрать "учебник Паскаль" или "Pascal". А то ну очень много пива придется выпить, пока не освоитесь.

[Sardukar]

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.

Нид хэлп как обычно)
Раз бинарную сортировку нельзя делать при не сортированном массиве, то его лучше отсортировать сразу после ввода с клавиатуры. Тут я смог это осуществить при помощи метода сортировки пузырьком. Попробовал вставить бинарную, но есть какие проблемы. Нид срочно хэлп))) В чём ошибка?

Сообщение отредактировано: Sardukar - 1.12.2007 5:35

[Sardukar]

Спасибо за помощь, но разобрался всё таки сам.
Закрывайте тему.



Сообщение отредактировано: Sardukar - 13.12.2007 6:22