Подпрограммы. Рекурсивные процедуры и функции


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

Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация