Линейный кроссворд
Для заданного набора слов требуется построить линейный кроссворд. Если окончание одного слова совпадает с началом следующего более чем в одной букве (например, МАТРАС-РАСИСТ), то такие слова можно объединить в цепочку. Первоначально ставится задача - получить любую такую цепочку, окончательно - цепочку минимальной длины.
Начало проектирования любой рекурсивной программы заключается в определении шага рекурсивного процесса. Пусть имеется уже составленная цепочка из выбранных слов. Очередной шаг процесса состоит в попытке присоединения к имеющейся цепочке еще одного слова из оставшихся. Если это возможно, то для новой цепочки необходимо выполнить попытку присоединить следующее слово и так далее, то есть выполнить следующий шаг рекурсивного процесса. Таким образом :
- рекурсивная функция выполняет попытку присоединения очередного слова к уже выстроенной цепочке ;
- результатом функции является логическое значение (данную цепочку можно достроить), функция ищет первый подходящий вариант ;
- условием завершения рекурсии является отсутствие еще не присоединенных к цепочке слов (успешное завершение), либо невозможность завершения цепочки ни через одно из оставшихся слов (неудача) .
Множество возможных вариантов строится на основе обычного комбинаторного перебора всех допустимых сочетаний (последовательностей) из элементов множества ( в данном случае - слов). Это множество является глобальной структурой данных, из которой на каждом шаге извлекается очередной элемент, но по завершении просмотра варианта (после рекурсивного вызова) возвращается обратно.
Для представления множества слов будем использовать массив указателей на строки. Исключение строки из множества будет заключаться в установке указателя на строку нулевой длины. Теперь можем " набросать" общий вид рекурсивной функции
char *w[]={"РАСИСТ","МАТРАС","МАСТЕР","СИСТЕМА","СТЕРВА",
NULL}; // Множество слов - глобальные данные
int step(char *lw) // параметр - текущее слово цепочки
{ int n; // результат - можно присоединить
// оставшиеся
// проверка условия завершения рекурсии
// - все слов из w[] присоединены
for (n=0; w[n]!=NULL;n++)
{ // проверка на присоединение
char *pw; // очередного слова
if (*w[n]==0) continue;
pw=w[n]; // пустое слово - пропустить
w[n]=""; // исключить проверяемое слово из
// множества
{ // попытка присоединить слово
if (step(pw)) // - рекурсивный вызов
{ ...
return 1; // удача - завершить успешно
}
}
w[n]=pw; // возвратить исключенное слово
} // неудача - нельзя присоединить
return 0; // ни одного слова
}
Данный " набросок" не содержит некоторых частностей, которые не меняют общей картины :
проверка условия завершения рекурсии - если массив указателей содержит только пустые строки, то рекурсивная последовательность шагов завершена успешно (все слова выбраны на предыдущих шагах) ;
проверка совпадения " хвоста" очередного слова и начала выбираемого на текущем шаге - делается отдельной функцией ;
сама цепочка выбранных слов выводится в процессе " ретрансляции" положительного результата непосредственно на экран в обратном порядке (что не совсем " красиво" ). В принципе она может быть сформирована и в глобальных данных.
//------------------------------------------------------bk54-03.cpp
#include <iostream.h>
#include <string.h>
char *w[]={"РАСИСТ","МАТРАС","МАСТЕР","СИСТЕМА","СТЕРВА",
NULL};
int step(char *lw) // параметр - текущее слово цепочки
{ int n;
for (n=0; w[n]!=NULL;n++)
if (*w[n]!=0) break;
if (w[n]==NULL) // цепочка выстроена, все слова
return 1; // из w[] присоединены
for (n=0; w[n]!=NULL;n++)
{ // проверка на присоединение
char *pw; // очередного слова
if (*w[n]==0) continue;
pw=w[n]; // пустое слово - пропустить
w[n]=""; // исключить проверяемое слово из
if (TEST(lw,pw)) // множества
{ // попытка присоединить слово
if (step(pw)) // присоединено - попытка вывести
{ // цепочку из нового слова,
cout << pw << "\n";
return 1; // удача - вывести слово и выйти
}
}
w[n]=pw; // возвратить исключенное слово
}
return 0;
}
Чисто технические детали : функция TEST проверяет, не совпадает ли окончание первой строки с началом второй путем обычного сравнения строк при заданной длине " хвоста" первой строки.
int TEST(char *s, char *r)
{ int n,k;
n=strlen(s);
if (n==0) return 1;
for (;*s!=0 && n> 1; s++,n--)
if (strncmp(s,r,n)==0) return 1;
return 0; }
Другая техническая проблема - удобство первоначального запуска рекурсии. Функция TEST при первом параметре - пустой строке возвращает ИСТИНУ при любом виде второй строки. Этого достаточно, чтобы запустить первый шаг рекурсии. При наличии пустой строки в качестве параметра функции step на первом шаге рекурсии будет производиться безусловная проверка каждого слова на предмет создания цепочки.
void main() { step(""); }
