Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритм дихотомического поиска





 

Этот алгоритм является более быстрым, чем линейный, но применяетсятолько к упорядоченным массивам. Среднее время дихотомического поиска пропорционально величине log2n, где n — количество элементов таблицы эталонов.

Метод основан на последовательном делении на 2 диапазона поиска. При этом на каждом шаге либо находится элемент, либо происходит переход в одну из половин диапазона. В процессе поиска выполняется не только сравнение на равенство, но и на больше-меньше. Последняя операция позволяет выбрать очередную половину диапазона таблицы. Если массив эталонов не упорядочен, то выбор будет сделан неверно, и результат можно не получить никогда (говорят, что алгоритм расходится).

Общий алгоритм поиска будет таким же, как в п. 18.1, т.е.

1. Ввести два исходных массива слов (таблицу-словарь).

2. Повторять

ввести новое слово и вывести русское

пока не надоест.

3. Закончить.

Для корректности работы алгоритма необходимо упорядочить словарь (массивы слов) по алфавиту. Эта операция выполняется применительно к основному массиву, используемому при поиске — к английским словам.

Уточненный алгоритм можно представить в следующем виде.

1.1. Ввести количество слов в словаре (n).

1.2. Для номера слова (i) от 1 до n выполнить

1.2.1. Ввести Английское_Слово[i].

1.2.2. Ввести Русское_Слово[i].

2. Упорядочить слова по алфивату:

Для номера просмотра (k) от 1 до n - 1 выполнить

Для номера слова (i) от 1 до n - k выполнить

Если Английское_Слово[i] > Английское_Слово[i+1] то

а) поменять местами Английское_Слово[i] и Английское_Слово[i+1];

б) поменять местами Русское _Слово[i] и Русское _Слово[i+1].

3. Повторять

3.2.1. Ввести Слово (для перевода);

3.2.2. Граница_левая (диапазона поиска): = 1;

3.2.3. Граница_правая (диапазона поиска): = n;

3.2.4. Признак: = " Не найдено".

3.2.5. Повторять

а) Номер Русского_Слова (k): = (Граница_левая + Граница_правая)/2;

б) Если Слово = Английское_Слово[i] ТО

Признак: = " Найдено"

Иначе

Если Слово > Английское_Слово[i] ТО

k: = Граница_левая

Иначе

k: = Граница_правая.

Пока не будет " Найдено" Или (Граница_левая = Граница_правая - 1).

3.2.6. Если " Найдено" 0 ТО

вывести Русское_Слово[k]

Иначе

вывести: 'Введенного слова нет в словаре'.

пока не будет Слово = 'End'.

4. Закончить.

Программа дихотомического поиска, соответствующая этому алгоритму, будет иметь вид.

 

Program DixPoisk;

Const

Nmax = 100;

dl = 15; { длина слова }

Var

Rsl, Asl: Array[1..Nmax] of string[dl];

Slovo: String[dl];

i, k, n: Integer;

Lev, Prav: Integer; { границы }

Naideno: Boolean; { признак }

 

Begin

Writeln('Введите количество слов');

ReadLn(n);

Writeln('Введите словарь');

For i: = 1 to n do

Begin

ReadLn(Rsl[i]);

ReadLn(Asl[i]);

End;

{ Упорядочение словаря по английскому алфавиту }

For k: =1 to n-1 do

For i: =1 to n-k do

If Asl[i] > Asl[i+1] then

Begin

Slovo: = Asl[i];

Asl[i]: = Asl[i+1];

Asl[i]: = Slovo;

Slovo: = Rsl[i];

Rsl[i]: = Rsl[i+1];

Rsl[i]: = Slovo;

End;

{ Перевод }

Repeat

WriteLn('Введите слово для перевода');

ReadLn(Slovo);

Lev: = 1;

Prav: = n;

Naideno: = False; { не найдено }

Repeat

k: =Round(Lev + Prav) / 2);

If Slovo = Asl[k] then

Naideno: = True { не найдено }

Else

If Slovo > Asl[k] then

k: =Lev

Else

k: = Prav;

Until Naideno Or (lev=Prav-1);

If Naideno then

Writeln(Rsl[k])

Else

Writeln('Нет такого слова в словаре');

Until Slovo='End';

Writeln('Работа окончена. Нажмите клавишу ENTER');

Readln;

END.

 

 







Дата добавления: 2014-12-06; просмотров: 1331. Нарушение авторских прав; Мы поможем в написании вашей работы!




Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Основные симптомы при заболеваниях органов кровообращения При болезнях органов кровообращения больные могут предъявлять различные жалобы: боли в области сердца и за грудиной, одышка, сердцебиение, перебои в сердце, удушье, отеки, цианоз головная боль, увеличение печени, слабость...

Вопрос 1. Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации К коллективным средствам защиты относятся: вентиляция, отопление, освещение, защита от шума и вибрации...

Задержки и неисправности пистолета Макарова 1.Что может произойти при стрельбе из пистолета, если загрязнятся пазы на рамке...

Виды и жанры театрализованных представлений   Проживание бронируется и оплачивается слушателями самостоятельно...

Что происходит при встрече с близнецовым пламенем   Если встреча с родственной душой может произойти достаточно спокойно – то встреча с близнецовым пламенем всегда подобна вспышке...

Реостаты и резисторы силовой цепи. Реостаты и резисторы силовой цепи. Резисторы и реостаты предназначены для ограничения тока в электрических цепях. В зависимости от назначения различают пусковые...

Studopedia.info - Студопедия - 2014-2025 год . (0.01 сек.) русская версия | украинская версия