IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Задача по методу бинарного поиска., Нужна помощь.
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Alexander

Репутация: -  0  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Alexander

Репутация: -  0  +


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

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.
З.ы. вот такая вот фигня) код впринципе есть но понимание как его переделать чтоб работал-ноль.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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

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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Sardukar @ 28.11.2007 9:12) *
Извиняюь если намудрил, всегда так выходит)
Неплохой комплимент самому себе..

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

Цитата(Sardukar @ 28.11.2007 9:12) *
К сожалению разницу между просто Pascal или TurboPascal я не особо улавливаю)
Разница примерно такая же, как между рисунком дома (или, скажем, его проектом) и самим домом. Заметь, что в доме всегда могут быть отличия от проекта. А если это типовой проект, то в каждом доме, построенном по нему, будут отличия как от проекта, так и между домами.

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Alexander

Репутация: -  0  +


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 и т.д.?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Цитата(Sardukar @ 28.11.2007 14:33) *


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 - это реализация Паскаля от фирмы Борланд.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






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


Сообщение отредактировано: Lapp -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Alexander

Репутация: -  0  +


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

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


Гость






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

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





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Alexander

Репутация: -  0  +


Эмм.. по 1 пункту не понял по второму...тоесть скажем у нас const = 9, и надо вводить не рандомно а именно по возрастанию или как? 1 3 7 9 11 12 13 14 15 19 20 25 и т.д. так?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






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

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

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

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

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


Гость






Цитата(Sardukar @ 28.11.2007 17:08) *

Эмм.. по 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". А то ну очень много пива придется выпить, пока не освоитесь. smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Alexander

Репутация: -  0  +



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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Alexander

Репутация: -  0  +


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



Сообщение отредактировано: Sardukar -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 19:56
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name