Предлагаю коллегам
Что общего между лексической игрой “Отгадай
слово” и двоичным деревом?
И.В. Садовая,
г. Тверь, гимназия № 10
При объяснении нового материала
всегда хочется найти такую задачу, при решении
которой ученик имеет возможность совершить
собственное маленькое открытие. Поиск такой
задачи занимает немало времени. Трудность
заключается еще и в том, чтобы не переборщить со
сложностью, не отбить у ребят охоту искать.
Каждый раз, когда я встречаю подобную задачу, мне
хочется поделиться находкой с коллегами. Об
одной из таких задач рассказано в этой заметке.
Никто не мог предположить, чем
закончится написание программы, реализующей
игру “Отгадай слово”. Эта игра подробно описана
Гиком в книге “Интеллектуальные головоломки и
задачи”.
Играют двое. В игре компьютер
загадывает 5-буквенное слово. Человек вводит
слова любой длины, на которые компьютер отвечает
числом, означающим, сколько есть в тестовом слове
букв, входящих в загаданное.
Приведу пример диалога человека (Ч) и
компьютера (К).
| Ч |
К |
| 1. ПЕРЕВАЛ |
2 |
2. СВАЛКА |
0 |
| 3. ПОП |
0 |
| 4. ФАКУЛЬТАТИВ |
4 |
| 5. БАНАН |
1 |
| 6. БУФЕТ |
Отгадал |
Извлекая на каждом ходу ту или иную
информацию о задуманном слове, игрок делает ход и
т.д., пока не получит ответ “отгадал”.
Как и в большинстве игр в слова, и
задуманное слово, и “ходы” должны быть
существительными, нарицательными, в
единственном числе.
Так как игра наша была учебной, то
компьютер “загадывал” одно из десяти слов, явно
прописанных в программном коде. Игрок вводил
слова с клавиатуры и получал в ответ число
совпавших букв или сообщение об окончании игры
при полном совпадении слов. Но вот именно тут
автора компьютерного варианта игры “заело”: как
же сделать так, чтобы можно было проверять, а
существует ли такое слово на самом деле?
Процесс поиска решения был трудным и
одновременно захватывающим. И вот к чему мы
пришли.
Используется словарь, содержащий
более 43 000 существительных (словарь, правда,
пришлось искать в Интернете). Эти слова хранятся
в текстовом файле. Теперь каждый ход игрока
должен проверяться на наличие такого слова в
словаре, то есть категорически не разрешается
использовать в качестве тестов отдельные буквы.
Простое перечисление букв запрещено.
В программе используется динамическая
структура данных — двоичное дерево. Раздел
программирования “Динамические структуры
данных” достаточно труден для усвоения, но в
данной ситуации был изучен учащимися с огромным
интересом и глубоким пониманием. Сочли, что
применение именно этой структуры значительно
сэкономит объем оперативной памяти и позволит
реализовать более быстрый поиск слова в словаре.
Сам словарь пришлось составить таким образом,
чтобы в начале файла находились слова с такой
буквы, с какой их больше всего в словаре, и,
соответственно, в конце словаря находятся слова,
каких меньше всего. Рекордсменами оказались
слова, начинающиеся на букву “П”, — их более 6000,
затем идут слова с буквы “С” — около 4000, потом
буква “К” — более 3000 и т.д.
При запуске игры формируется двоичное
дерево. Его описание имеет следующий вид:
Type pt = ^node;
node = record
{информационное поле — одна буква}
data : char;
{ссылки на левого и правого потомков}
left, right : pt;
{признак, является ли данная
буква окончанием какого-либо
слова}
fin : boolean;
end;
Логику построения дерева рассмотрим
на примере словаря, содержащего 5 слов:
Пасс
Пассаж
Паста
Пастух
Пар
Корень дерева — вершина первого уровня —
содержит первую букву первого слова — П, далее
размещаем по правым потомкам буквы — а, с, с.
У вершины, содержащей вторую букву “с”, признак
окончания слова должен быть равен “истина” (на
рисунке это знак “#”), правый потомок должен быть
равен nil и левые потомки всех вершин также равны
nil.

Добавляем в дерево слово “Пассаж”.
Так как новое слово совпадает с предыдущим по
первым четырем буквам, то новых вершин добавлено
не будет, а вот последние — “а” и “ж” — должны
получить свои вершины по правой стороне от
последней буквы “с”.
Новое слово “Паста” совпадает с
предыдущими словами по трем буквам,
следовательно, для них будем использовать уже
имеющиеся в наличии вершины, а вот для букв “т” и
“а” необходимо создать новые вершины, ссылка на
которые — левый потомок первой буквы “с”.

Для следующего слова “Пастух” нужно
создать вершину “у”, ссылка на которую является
левым потомком буквы “т”. После добавления в
дерево последнего слова “Пар” у нас должно
получиться:

Хорошо видно, что экономится объем
памяти за счет использования уже имеющихся букв.
Данный способ записи данных используется в
некоторых архиваторах — перед построением
дерева подсчитывается, какие элементы чаще
встречаются, и именно с них начинается
построение дерева.
В нашей ситуации построенное дерево
позволяет, помимо экономии объема памяти,
осуществить быстрый поиск слова. При совпадении
очередной буквы слова с информационным полем
вершины всегда выбираем направление вправо, если
совпадения нет — идем по левой ссылке. Для
примера покажем поиск слова “Паста”.
буква “П” — совпадение — спуск
вправо
буква “а” — совпадение — спуск
вправо
буква “с” — совпадение — спуск
вправо
буква “с” — совпадения нет — спуск
влево от предыдущей вершины
буква “т” — совпадение — спуск
вправо
буква “а” — совпадение — проверка на
признак окончания слова — данное слово в дереве
присутствует
При написании программного кода для
построения дерева используется рекурсия.
Вспомним, алгоритм называется рекурсивным, если
содержит в своей записи вызов самого себя.
Используя псевдокод, покажем, как
производится вставка слова в дерево.
алгоритм вставка(аргументы
адрес : указатель на вершину, слово : строка)
начало
если слово не пустое то
если адрес указывает на пусто то
новый(адрес);
левый и правый потомки := пусто
информационное поле := первая буква
слова
если длина слова = 1 то
признак окончания := истина
иначе признак окончания := ложь;
все
вставка(адрес правого потомка,
слово без 1-й буквы)
иначе
если в имеющейся вершине
информационное поле = 1-й букве слова
то вставка(адрес правого
потомка, слово без 1-й буквы)
иначе вставка(адрес левого
потомка, слово)
все
все
все
Для поиска слова в дереве также
приведем алгоритм на псевдокоде:
алг поиск (арг адрес : указатель
на вершину, слово : строка):
логический {истина — слово в дереве есть, ложь —
нет}
нач цел i
поиск := ложь; i := 1;
нц пока (i <= длины
слова) и (адрес не указывает на пусто)
нц пока (i-я буква
совпадает с буквой на вершине)
если (попали на последнюю букву
и признак окончания слова = истина)
то поиск := истина
иначе i увеличить на 1, адрес :=
адрес правого потомка
все
кц
адрес := адрес левого потомка
кц
кон
В заключение приведем листинг
программы на языке Паскаль, в котором по словам
из текстового файла строится дерево, а на любое
введенное с клавиатуры слово выдается ответ —
есть ли такое в дереве.
program primer;
uses crt;
type
pt = ^node;
node = record
data:char;
left, right:pt;
end;
var s : string; f, f1 : text; root : pt; i : integer;
procedure ins_tree(var t:pt;s:string);
var i: integer; tn:pt;
begin
if length(s) <> 0 then
if t = nil then begin
new(t);
with t^ do begin
left := nil; right := nil; data := s [1];
ins_tree(t^.right,copy(s,2,length(s) – 1))
end;
end
else begin
if t^.data = s[1] then ins_tree(t^.right,copy(s,2,length(s) – 1))
else ins_tree(t^.left,s);
end;
end;
function in_tree(var t:pt; s:string):boolean;
var i:integer; tn:pt;
begin
tn := t; i := 1;
while ((i <= length(s)) and (tn <> nil)) do
begin
while ((s[i] = tn^.data) and (i <= length(s))) do
begin
inc(i); tn := tn^.right;
end;
tn := tn^.left;
end;
if s <> '' then dec(i); in_tree := i = length(s);
end;
begin
clrscr;
assign(f,'d:\tp\words\russian.dic');
reset(f); root := nil;
while not eof(f) do
begin
readln(f, s ); ins_tree(root, s);
end;
close(f);
repeat
readln(s); writeln(in_tree(root,s));
until(s = ' ');
end. |