Алгоритм линейного поиска

В соответствии с этим алгоритмом, как отмечалось выше, эталонный массив просматривается последовательно от первого до последнего элемента. Наиболее сложным является случай, когда слова нет в словаре (не найдено).

Общий алгоритм поиска можно описать так.

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

2. Повторять

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

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

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

Пусть для окончания работы с программой (когда переводить надоело) необходимо ввести слово "End".

Уточненный алгоритм будет таким.

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

2. Повторять

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

2.2.2. Номер Русского_Слова (Num):= 0;

2.2.3. Для номера Английского_Слова (i) от 1 до n выполнить

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

номер Русского_Слова (Num):= i;

2.2.4. Если номер Русского_Слова (Num) = 0 то

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

Иначе

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

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

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

Обозначим:

Rsl - массив русских слов в словаре

Asl - массив английских слов в словаре

Slovo - слово для перевода.

Программа линейного поиска будет иметь вид

Program Poisk;

Const

n = 100;

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

Var

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

Slovo : String[dl];

i, Num : Integer;

BEGIN

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

For i := 1 to n do

Begin

ReadLn(Rsl[i]);

ReadLn(Asl[i]);

End;

{ перевод }

Repeat

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

ReadLn(Slovo);

Num:=0; { номер слова в словаре }

For i := 1 to n do

If Slovo = Asl[i] then

Num := i;

If Num = 0 then

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

Else

Writeln(Rsl[Num]);

Until Slovo='End';

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

Readln;

END.

Основной недостаток алгоритма линейного поиска – большое время. При использовании оператора For для поиска ВСЕГДА выполняется ровно n операций сравнения, не зависимо от того, найдено слово или нет. Поэтому программа, обнаружив слово в начале словаря, продолжает его просмотр до конца, т.е. выполняет бесполезную работу. Время поиска может быть существенно сокращено, если обеспечить его прекращение, когда слово найдено. При равномерном распределении элементов в таблице эталаонов (слов в словаре) среднее время поиска может стать пропорциональным величине n / 2.

Этого можно достичь, изменив пункт 2.2 в рассмотренном выше алгоритме следующим образом.