Разберем следующую задачу
В алфавите языка племени «тумба?юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все слова, состоящие из n букв, которые можно построить из букв этого алфавита
Задача представляет собой обычную задачу на перебор, которую можно свести к задаче меньшего размера.
Будем последовательно подставлять буквы к слову.
На первой позиции слова может стоять одна из 4х букв алфавита (K. L, M, N)
Cначала первой поставим букву K'. Тогда для того, чтобы получить все варианты с первой буквой 'K', нужно перебрать все возможные
комбинации букв на оставшихся n-1 позициях.
и .т.д. (см. рисунок)
Таким образом задача сводится к решению четырех задач длины n-1
Рекурсивный перебор n символов
w[0]='K'; // перебор последних L-1 символов
w[0]='L'; // перебор последних L-1 символов
w[0]='M'; // перебор последних L-1 символов
w[0]='N'; // перебор последних L-1 символов
w - символьная строка, в которой хранится рабочее слово
Таким образом мы получили
рекурсию.
Решение задачи мы можем оформить в виде рекурсивной процудуры
Осталось определить когда рекурсия закончится: тогда, когда все символы расставлены, то есть количество установленных символов равно n. При этом нужно вывести получившееся слово на экран и выйти из процедуры.
Программа на языке С++ будет выглядет следующим образом
void TumbaWords( string A, string &w, int N ) //w - изменяемый параметр (строка-результат)
// Процедуре TumbaWords передается алфавит в виде символьной строки,
// слово word и число уже установленных символов (в начале – 0)
{
int i;
if ( N == w.size()) // если установили в слово уже все символы, то необходимо вывести строку и закончить процедуру
{
cout << w << endl;
return;
}
for ( i = 1; i < A.size(); i ++ ) // если условие выше ложно (то есть не все символы расставлены,
{ // //то в цикле перебираем все символы алфавита и поочередно ставим символ на первое свободное место
w[N] = A[i];
TumbaWords ( A, w, N+1 );
}
}
main()
{
int n;
string word;
int n;
cin>>n;
word.resize(n); // увеличиваем строку до размера n
TumbaWords ( "KLMN", word, 0 );
}
ОБРАТИТЕ ВНИМАНИЕ, что параметр w - изменяемый параметр (строка-результат)