Информатика и технология программирования


Линейный кроссворд


Для заданного набора слов требуется построить линейный кроссворд. Если окончание одного слова совпадает с началом следующего более чем в одной букве (например, МАТРАС-РАСИСТ), то такие слова можно объединить в цепочку. Первоначально ставится задача - получить любую такую цепочку, окончательно - цепочку минимальной длины.

Начало проектирования любой рекурсивной программы заключается в определении шага рекурсивного процесса. Пусть имеется уже составленная цепочка из выбранных слов. Очередной шаг процесса состоит в попытке присоединения к имеющейся цепочке еще одного слова из оставшихся. Если это возможно, то для новой цепочки необходимо выполнить попытку присоединить следующее слово и так далее, то есть выполнить следующий шаг рекурсивного процесса. Таким образом :



- рекурсивная функция выполняет попытку присоединения очередного слова к уже выстроенной цепочке ;



- результатом функции является логическое значение (данную цепочку можно достроить), функция ищет первый подходящий вариант ;



- условием завершения рекурсии является отсутствие еще не присоединенных к цепочке слов (успешное завершение), либо невозможность завершения цепочки ни через одно из оставшихся слов (неудача) .

Множество возможных вариантов строится на основе обычного комбинаторного перебора всех допустимых сочетаний (последовательностей) из элементов множества ( в данном случае - слов). Это множество является глобальной структурой данных, из которой на каждом шаге извлекается очередной элемент, но по завершении просмотра варианта (после рекурсивного вызова) возвращается обратно.

Для представления множества слов будем использовать массив указателей на строки. Исключение строки из множества будет заключаться в установке указателя на строку нулевой длины. Теперь можем " набросать" общий вид рекурсивной функции


char *w[]={"РАСИСТ","МАТРАС","МАСТЕР","СИСТЕМА","СТЕРВА",
NULL}; // Множество слов - глобальные данные



int step(char *lw) // параметр - текущее слово цепочки




Начало  Назад  Вперед



Книжный магазин