© Данная статья была опубликована в № 24/2006 журнала "Информатика" издательского дома "Первое сентября". Все права принадлежат автору и издателю и охраняются.      Главная страница "Первого сентября"
     Главная страница журнала "Информатика"
     Содержание № 24/2006
 Что общего между лексической игрой “Отгадай слово” и двоичным деревом?

 

Предлагаю коллегам

Что общего между лексической игрой “Отгадай слово” и двоичным деревом?

И.В. Садовая,
г. Тверь, гимназия № 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.

30-0.gif (5033 bytes)

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

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

30-1.gif (9765 bytes)

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

30-2.gif (11840 bytes)

Хорошо видно, что экономится объем памяти за счет использования уже имеющихся букв. Данный способ записи данных используется в некоторых архиваторах — перед построением дерева подсчитывается, какие элементы чаще встречаются, и именно с них начинается построение дерева.

В нашей ситуации построенное дерево позволяет, помимо экономии объема памяти, осуществить быстрый поиск слова. При совпадении очередной буквы слова с информационным полем вершины всегда выбираем направление вправо, если совпадения нет — идем по левой ссылке. Для примера покажем поиск слова “Паста”.

буква “П” — совпадение — спуск вправо

буква “а” — совпадение — спуск вправо

буква “с” — совпадение — спуск вправо

буква “с” — совпадения нет — спуск влево от предыдущей вершины

буква “т” — совпадение — спуск вправо

буква “а” — совпадение — проверка на признак окончания слова — данное слово в дереве присутствует


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

Используя псевдокод, покажем, как производится вставка слова в дерево.

алгоритм вставка(аргументы адрес : указатель на вершину, слово : строка)

начало

если слово не пустое то

если адрес указывает на пусто то

новый(адрес);

левый и правый потомки := пусто

информационное поле := первая буква слова

если длина слова = 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.