Двоичный Поиск

  • Автор темы Annushka
  • Дата начала
A

Annushka

Гость
#1
Нужно написать программу, используя алгоритм двоичного поиска...количество символов в 1 строке:3...
Данные:
 - задан массив символов, элементы которого должны быть введены с клавиатуры;
 - результатом работы программы поиска является либо строка 'элемент найден', либо 'элемент не найден';
- символ для поиска должен вводиться с клавиатуры;
 - результат программы сортировки - исходный и отсортированный массивы;
 - программа должна быть зациклена, прекращение работы программы - нажатие <ESC>;
- количество элементов в массиве не менее 10.

Дополнительный теоретический материал:
Алгоритм двоичного поиска. Этот алгоритм широко применяется в системных программах и известен в литературе также и под другими названиями: бинарный, логарифмический, половинного деления и др. Идея его заключается в том, что ключ поиска на каждом шаге сравнивается с элементом,
расположенным в середине таблицы или ее части.
Если ключ поиска меньше "серединного" элемента, то "нижняя" часть таблицы из последующего рассмотрения исключается, и дальше алгоритм будет работать с "верхней" частью. В противном случае - будет исключаться "верхняя" часть и работа будет выполняться с "нижней". Для точного задания
алгоритма необходимо ввести две переменные: NG - нижнюю границу поиска и VG -верхнюю границу поиска. Перед началом поиска им присваиваются следующие значения: NG=1, VG=N. Номер элемента, расположенного в середине, определяется по формуле:
J = (VG + NG) / 2
Если ключ поиска X меньше "серединного" элемента Tj, то изменяется верхняя граница VG=j. Если наоборот - то нижняя граница: NG=j.

Помогите пожалуйста!!!
 
A

Annushka

Гость
#2
Нужно написать программу, используя алгоритм двоичного поиска...количество символов в 1 строке:3...
Данные:
 - задан массив символов, элементы которого должны быть введены с клавиатуры;
 - результатом работы программы поиска является либо строка 'элемент найден', либо 'элемент не найден';
- символ для поиска должен вводиться с клавиатуры;
 - результат программы сортировки - исходный и отсортированный массивы;
 - программа должна быть зациклена, прекращение работы программы - нажатие <ESC>;
- количество элементов в массиве не менее 10.

Дополнительный теоретический материал:
Алгоритм двоичного поиска. Этот алгоритм широко применяется в системных программах и известен в литературе также и под другими названиями: бинарный, логарифмический, половинного деления и др. Идея его заключается в том, что ключ поиска на каждом шаге сравнивается с элементом,
расположенным в середине таблицы или ее части.
Если ключ поиска меньше "серединного" элемента, то "нижняя" часть таблицы из последующего рассмотрения исключается, и дальше алгоритм будет работать с "верхней" частью. В противном случае - будет исключаться "верхняя" часть и работа будет выполняться с "нижней". Для точного задания
алгоритма необходимо ввести две переменные: NG - нижнюю границу поиска и VG -верхнюю границу поиска. Перед началом поиска им присваиваются следующие значения: NG=1, VG=N. Номер элемента, расположенного в середине, определяется по формуле:
J = (VG + NG) / 2
Если ключ поиска X меньше "серединного" элемента Tj, то изменяется верхняя граница VG=j. Если наоборот - то нижняя граница: NG=j.

Помогите пожалуйста!!!
я кажется написала:

Код:
uses crt;
var s:string;
i,k,n:integer;
c:char;
begin
write('s:');
readln(s);
for i:=1 to Length(s)-1 do
For k:= i+1 to Length(s) do
if s[i]>s[k] then
begin
c:=s[i];
s[i]:=s[k];
s[k]:=c;
end;
write('символ :');
readln©;
i:=1;n:=Length(s);
k:= (n-i+1) div 2+i;
while (n>i+1) and (s[k]<>c) do begin
if s[k]>c then n:=k;
if s[k]<c then i:=k;
k:=((n-i+1) div 2) +i;
end;
writeln('отсортированная строка :',s);
if s[k]=c then writeln('символ ',c,' найден #',k)
else writeln('символ ',c,' не найден')
end.
Но что-то не то....Помогите исправить ошибки...и помогите сделать блок-схему....
 

Cambur

Active Member
20.06.2010
27
0
venezuela@mail.ru
#3
по-моему - всё хорошо написала.
только осталось зациклить программу
поставь while в начале и до конца кода и запрашивай выход на следующий цикл после вывода результата..
:)
 

Cambur

Active Member
20.06.2010
27
0
venezuela@mail.ru
#5
uses crt;
var c : char;
begin
c := '1';
while c = '1' do begin

{
....... tut tvoya programka
write('s:');
.....
else writeln(simvol ',c, 'ne nayden');
}

write('tecla 1 - prodolzat 0 - vixod ');
readln( c );
end;
writeln('se acabo' );
readln;
end.

ну, здрасти....
вот тебе пример - разберись своей головой. это очень просто.
как дела с блок- схемой?
 
A

Annushka

Гость
#6
Спасибо большое... кажется работает....
Блок-схему кажется сделала.... проверте пожалуйста, а то я с ними не сильно дружу...
 

Вложения

Cambur

Active Member
20.06.2010
27
0
venezuela@mail.ru
#7
привет - я там крассным подрисовал, как по-моему должно быть ...


Добавлено: привет - я там крассным подрисовал, как по-моему должно быть ...
 

Вложения

  • 49.5 КБ Просмотры: 8
A

Annushka

Гость
#8
привет - я там крассным подрисовал, как по-моему должно быть ...


Добавлено: привет - я там крассным подрисовал, как по-моему должно быть ...
Спасибо большое, я учту...))))

Добавлено:
привет - я там крассным подрисовал, как по-моему должно быть ...


Добавлено: привет - я там крассным подрисовал, как по-моему должно быть ...
Спасибо большое, я учту...))))