В.Н.Касаткин
Задачник клуба "Терминал"
Ниже предлагается задача для разработки алгоритма и программы ее
решения на ЭВМ. Можно предлагать только алгоритм или алгоритм и про-
грамму. Одну программу присылать не следует.
Лучшие решения задач будут опубликованы и прокомментированы спе-
циалистами.
Известна задача-шутка "Как из мухи сделать слона? Речь идет о поиске це-
почки из слов (имен существительных, нарицательных, в единственном числе,
именительном падеже), первое из которых МУХА, последнее СЛОН, а все
промежуточные отличаются одной буквой и встречаются в цепочке один раз.
Попробуйте найти такую цепочку из слов.
Рассказанное позволяет сформулировать задачу на программирование:
пусть дан алфавит А из нескольких слов. Считая одно из слов Aj начальным, а
другое Ак конечным, построить цепочку слов от начального к конечному. В
цепочку могут входить только слова из данного алфавита А, не более, чем по
одному разу. Слова-соседи по цепочке должны отличаться только одной бук-
вой.
Прилагаем далее одно из возможных решений этой задачи.
В.Касаткин
Алексей Юшин
(МАН "Искатель", г.Симферополь)
Программа "Слово за-слово"
Известна задача-игра, в которой из заданного слова требуется вывести
другое. При этом разрешается использовать только существительные и на
каждом шаге менять лишь одну букву текущего слова.
Назовем два слова равной длины соседями, если они отличаются только
одной буквой. Тогда задачу можно сформулировать так.
Дан словарь V и слова s и t, принадлежащие V.
Получить последовательность
R = (s, rlf r2, ... , rn , t),
все смежные элементы которой соседи, Г| R.
Запишем на ПАСКАЛЕ функцию булевского типа Neighbour (а,Ь), где а и b
слова, принадлежащие V. Значение функции равно TRUE, если а и b соседи, и
FALSE в противном случае.
FUNCTION Neighbour (arb : string): Boolean;
Var
i : Range ;
Y : Boolean ;
crd : String ;
begin
Y: = (Length(a) = Length(b)) and (a< > b) ;
if Y
then
begin
i : = 1 ;
REPEAT
с : = a ;
d := b ;
c[i] : = "*";
d[i] : = "*";
Y:= (c = d);
i : = i + 1 ;
UNTIL Y or (i > Length(a)) ;
end ;
Neighbour : = Y;
end;
Алгоритм построения цепочки R можно сформулировать так:
1. Включить слово — источник S в R;
2. ЕСЛИ последующее слово в R есть цель t, то напечатать цепочку R и
цель t ;
ИНАЧЕ найти список Q, всех соседей последнего слова из R, вычеркнуть их
из словаря V ;
3. ЕСЛИ список Q соседей последнего слова пуст, то удалить из R послед-
нее слово и восстановить его в V ;
ИНАЧЕ взять первое слово из списка Q, вычеркнуть его из Q и включить в
качестве последующего слова R;
4. Завершить алгоритм, если исчерпаны все списки соседей.
Таким образом, в ходе алгоритма изменяется состояние словаря V за счет
удаления и восстановления в нем слов. Каждому слову цепочки ставится в со-
ответствие список Q его соседей. Каждый такой список в ходе алгоритма ис-
черпывается удалением его начальных элементов
Этот алгоритм реализуем в виде рекурсивной процедуры, с помощью ко-
торой можно получить все цепочки выводящие t из V.
Ниже приведен текст рекурсивной процедуры Resol. Перед обращением к
ней следует исключить исходное слово из словаря V, чтобы предотвратить за-
цикливание. Для исключения слов из V используется булев вектор Vec. Если
требуется исключить слово с номером i из V, то Vec[i] присваивается значе-
ние FALSE, при необходимости восстановления слова — значение TRUE. В
процедуре Resol используется процедура Write__Path, которая осуществляет
вывод на экран полученных цепочек слов.
PROCEDURE Resol (Word : string ;
Vec : BoolArray ;
Ind : NatArray ;
Numb : Natural ;
Path : StringArray) ;
Var
cnt,i : Natural ;
begin
if Word = Target
then Write__Path(Numb, Path)
else
begin
Numb : = Numb + 1;
Path[Numb] : = Word ;
cnt : = 0 ;
for i : = 1 to NVoc do
If Vec[i] and Neighbour (Word,V[i])
then
Begin
Vec [i] : = False;
Cnt : Cnt + 1;
Ind [cnt] : = i;
End;
for i : = 1 to Cnt do
Resol (V[ind[i]]rVec,lnd,NumbfPath);
end;
end;{Resol}
Комментарий специалиста
Рассмотренный алгоритм и программа могут служить элементарным вве-
дением в программирование логического вывода на основе знаний, заданных
с помощью отношений между объектами некоторой предметной области. В
задаче "Слово За-Слово" предметная область — это просто словарь (мно-
жество слов-существительных русского или английского языков)
Над множеством слов словаря задано отношение соседства, а логический
вывод есть такая последовательность слов, в которой каждые два подряд за-
писанных слова находятся в отношении соседства.
По мере того как строится логический вывод, словарь V усекается — в
нем отмечаются как несуществующие те слова, включение которых в остав-
шуюся часть цепочки вывода запрещается.
Какие же элементы запрещается включать в логический вывод в процессе
его построения?
Во-первых, это те слова, которые уже включены в цепочку.
Во-вторых, и это очень важно, в цепочку слов запрещается включать так
называемых "ближайших соседей" только что внесенного слова. Ближайшие
соседи — это слова, отличающиеся одной буквой в одной и той же позиции.
Иными словами, процедура RESOL не включает в вывод подцепочки вида:
... ноль —> соль —> роль —>моль —>...
не приближающие нас к цели.
В то же время слова ноль, соль, роль и моль будут рассматриваться про-
цедурой RESOL как альтернативные при построении различных цепочек. Это
достигается тем, что в качестве недоступных отмечаются все соседи слова,
только что включенного в цепочку вывода.
Таким образом, если
Ri
R i+ 1 соседи
Rj + 2 соседи
три последовательных слова в цепочке вывода, то Rj + 2 не может быть ни со-
седом Rj, ни ближайшим соседом Rj+j- В то же время Rj+j сосед Rj ; Rj + 2
сосед Rj+ 1
Процедура RESOL находит все цепочки вывода. Этому процессу соответст-
вует дерево, в котором слово, приписанное каждой вершине (кроме корня)
связано с потомками отношением соседства, но не ближайшего соседства.
Все потомки одного предка связаны отношением соседства, в том числе и
ближайшего соседства.
Если в дереве вывода существуют концевые вершины, помеченные целе-
вым словом t, то выводы — это последовательности слов, встречающихся на
каждом пути от корня к таким концевым вершинам.
Дерево вывода является динамическим. Если процесс построения цепочки
вывода (1) достиг цели или (2) зашел в тупик (текущее слово не имеет сосе-
дей), то осуществляется возврат на более высокий уровень. При этом конце-
вые вершины удаляются из дерева, а из цепочки вывода возвращаются в сло-
варь V, т.е. снова становятся доступными, слова, соответствующие этим кон-
цевым вершинам.
Этот достаточно сложный процесс с использованием рекурсии программи-
руется очень лаконично.
Без сомнения, это главное достоинство предлагаемой программы.
Теперь вообразите, что слова в V — это формулы или операторы какого-
либо языка программирования, а логические выводы — формульные вычис-
ления или программы. Представьте себе также, что слова перед включением
их в словарь V преобразуются по некоторым правилам. Вы окажетесь в увле-
кательном мире логических преобразований с помощью ЭВМ.
Задачи
1. Напишите булеву функцию, распознающую отношение ближайшего соседства.
2. Измените процедуру Resol на Opt_Resol, которая находит кратчайшую цепочку вывода.
3 Напишите программу визуализации дерева, соответствующего процессу логического вы-
вода.
И А.Переход
X 11 Hand held (О самых малых). — М.: Знание,
1991. — 48 с. — (Новое в жизни, науке, технике.
Сер. "Вычислительная техника и ее применение";
№ 2).
ISBN 5-07-001715-2
35 к.
Hand Held — устройство, удерживаемое одной рукой,
можно перевести иначе — ручной счет, ипи так... Во всяком
случае речь в этом выпуске — о калькуляторе, о его работе и
работе с ним. Все, что останется за рамками этой брошюры,
будет продолжено в специальной рубрике в последующих вы-
пусках.
Материал рассчитан на широкий круг читателей.
