Задача
В алфавите языка племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все слова, состоящие из n букв, которые можно построить из букв этого алфавита.
Задача представляет собой обычную задачу на перебор, которую можно свести к задаче меньшего размера.
Будем последовательно подставлять буквы к слову.
На первой позиции слова может стоять одна из 4-х букв алфавита (K. L, M, N).
Сначала первой поставим букву 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. При этом нужно вывести получившееся слово на экран и выйти из процедуры.
Программа на языке С++ будет выглядеть следующим образом.
#include<iostream>
using namespace std;
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 - изменяемый параметр (строка-результат)!
|