Модуль: Подпрограммы. Рекурсия


Задача

11/12

Перебор строк

Теория Нажмите, чтобы прочитать/скрыть

Задача
В алфавите языка племени «тумба-юмба» четыре буквы: «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 - изменяемый параметр (строка-результат)!

Задача

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все слова, состоящие из n букв, которые можно построить из букв этого алфавита.
(c) К.Ю. Поляков