Методы программирования. Громов Ю.Ю - 105 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

105
Шаг 1. Оставить первую букву фамилии и удалить из неё все буквы
a, e, h, i, o, u, w, y в других позициях;
Шаг 2. Назначить оставшимся буквам (кроме первой) следующие
числовые значения:
b, f, p, v
→
1; l
→
4;
c, g, j, k, q, s, x, z
→
2; m, n
→
5;
d, t
→
3; r
→
6.
Шаг 3. Если в исходном слове до выполнения шага 1 две или более
буквы с одним и тем же кодом стояли рядом, удалить коды всех букв,
кроме первой.
Шаг 4. Преобразовать полученный код в формат «буква, цифра,
цифра, цифра» (приписывая необходимое количество нулей справа, если
в результате получилось меньше трёх цифр, или отбрасывая лишние
цифры, если их больше трёх). ■
Например, фамилии Euler, Gauss, Hilbert, Knuth, Lloyd и Lukasiewicz
имеют коды E460, G200, H413, K530, L300 и L222 соответственно. Есте-
ственно, разные слова могут иметь одинаковые коды. Так, приведённные
выше коды могут быть получены из следующих фамилий: Ellery, Ghosh,
Heilbronn, Kant, Liddy и Lissajous. С другой стороны, такие схожие слова,
как Rogers и Rodgers, или Tchebysheff и Chebyshev, имеют разные коды.
Тем не менее, коды Soundex существенно увеличивают вероятность на-
хождения имени по одному из вариантов написания.
Прежде чем перейти к собственно изучению методов поиска, полез-
но взглянуть на историю данного вопроса. В докомпьютерную эру име-
лось множество книг с таблицами логарифмов, тригонометрическими и
другими таблицами (например «таблицы Брадиса»). И многие математи-
ческие вычисления фактически были сведены к поиску. Однако с появле-
нием компьютеров с хранимыми программами стало иногда проще вы-
числить значение log x или cos x заново, чем найти его в таблице. В неко-
торых других ситуациях более выгодным оказывается предварительное
вычисление таблиц функций, а в процессе работы – осуществление поис-
ка их значений. Заметим, что в процессе поиска можно использовать бо-
лее быструю целочисленную арифметику.
Хотя задача сортировки привлекала большое внимание ещё на заре
компьютерной эры, алгоритмы поиска оставались в забвении достаточно
долгое время. Из-за малой внутренней памяти и наличия для хранения
больших файлов только устройств последовательного доступа (наподо-
бие лент) делали поиск либо тривиальным, либо невозможным. Развитие
и удешевление памяти с произвольным доступом привело к пониманию
того, что проблема поиска важна и интересна.

Страницы