Вычислительная техника и её применение 1991-2 1991 г.

В.Н. Касаткин - задачник клуба "Терминал". Программа "Слово за-слово".


В.Н.Касаткин

Задачник клуба "Терминал"

Ниже предлагается задача для разработки алгоритма и программы ее
решения на ЭВМ. Можно предлагать только алгоритм или алгоритм и про-
грамму. Одну программу присылать не следует.

Лучшие решения задач будут опубликованы и прокомментированы спе-
циалистами.

Известна задача-шутка "Как из мухи сделать слона? Речь идет о поиске це-
почки из слов (имен существительных, нарицательных, в единственном числе,
именительном падеже), первое из которых МУХА, последнее СЛОН, а все
промежуточные отличаются одной буквой и встречаются в цепочке один раз.

Попробуйте найти такую цепочку из слов.

Рассказанное позволяет сформулировать задачу на программирование:
пусть дан алфавит А из нескольких слов. Считая одно из слов 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 — устройство, удерживаемое одной рукой,
можно перевести иначе — ручной счет, ипи так... Во всяком
случае речь в этом выпуске — о калькуляторе, о его работе и
работе с ним. Все, что останется за рамками этой брошюры,
будет продолжено в специальной рубрике в последующих вы-
пусках.

Материал рассчитан на широкий круг читателей.




  Оставте Ваш отзыв:

  НИК/ИМЯ
  ПОЧТА (шифруется)
  КОД



Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Железо - Сравнение компьютеров Профи и Скорпион.
Опрос - Анкета "Развитие Спектрума".
Исповедь - Rombik: Как я начал курить.
Байки из склепа - О лосенке по прозвищу FREE.
Intro - Привет всем! Таким нестандартным DOS'ом я запуская в прокат новый номер газеты, которую вы не читали уж так давно, WeekEnd номер 4.

В этот день...   29 марта