Задача
В алфавите языка племени «тумба-юмба» четыре буквы: «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. При этом нужно вывести получившееся слово на экран и выйти из процедуры.
Программа на языке С# будет выглядеть следующим образом.
// w - изменяемый параметр (строка-результат)
// Процедуре TumbaWords передается алфавит в виде символьной строки,
// слово word и число уже установленных символов (в начале – 0)
static void TumbaWords( string A, ref string w, int N )
{
if (N == w.Length) // w.Length - количество символов в строке
{
// если установили в слово уже все символы,
// то необходимо вывести строку и закончить процедуру
Console.WriteLine(w);
return;
}
for ( int i = 0; i < w.Length; i ++ ) // если условие выше ложно (то есть не все символы расставлены,
{
// если условие выше ложно (то есть не все символы расставлены,
// то в цикле перебираем все символы алфавита и
// поочередно ставим символ на первое свободное место
w += A[i];
TumbaWords(A, ref w, N+1);
w = w.Remove(w.Length - 1); // и после удаляем последний добавленный символ,
// чтобы составить новое слово с тем же префиксом
}
}
static void Main()
{
int n = Convert.ToInt32(Console.ReadLine());
string word = "";
TumbaWords("KLMN", ref word, 0);
}
ОБРАТИТЕ ВНИМАНИЕ, что параметр w - изменяемый параметр (строка-результат)!