Рекурсивная перестановка, алгоритмы Эллиса Горовица и структура данных Путаница.

Question

Я начинающий программист на первом курсе университета. Мой преподаватель попросил нас провести исследование рекурсивного алгоритма и сделать его не рекурсивным. Нет, как бы я ни старался, это кажется невозможным. Вопрос гласит

A - это строка символов (например, A = "hello"), и interchange, являющийся абстракцией, заменяет k-тый символ i-м символом A, например, CALL interchange("hello", 2, 3) изменится " привет "на" привет ").

Идея состоит в том, чтобы распечатать все возможные перестановки. Версия на C++ читает

void perm(char*a, const int k, const int n)
{
  if(k==n)
  {
    cout << a;
  }
  else
  {
    for (i=k;i<=n;i++)
    {
      interchange(a, k, i);
      perm(a, k+1, n)
    }
  }
 }

Мой репетитор предпочитает использовать язык ADL, который, кажется, появляется только в книге Горовица "Алгоритмы и структуры данных". Он поставил вопрос в ADL, поэтому я добавлю и этот код, его очень легко понять.

proc perm(IN a, IN k, IN n)
  if k=n then
    print(a)
  else
    {
     for i <- k to n do
       call interchange(a,k,i)
       call perm( a, k+1, n)
     end
    }
end

спасибо всем, кто может помочь. Martyn

Answer 1

Рекурсивный алгоритм - это просто алгоритм, использующий стек.

Рекурсия позволяет использовать стек вызовов в качестве стека данных.

Любая рекурсивная функция, принимающая эту форму:

void perm(char*a, const int k, const int n)
{
   // check if your code should return

   // make a recursive call with new data
}

Может быть изменено на это:

void perm(char*a, const int k, const int n)
{
   // Create a stack, push (a,k,n)

   while ( /* stack isn't empty */ )
   {
       // check if stack should be *popped* (instead of returning)

       // Put new data on the stack (instead of recursing)
   }
}

Answer 2

Вот подсказка, не выполняя за вас домашнее задание. Когда вы идете по цепочке, глядя на i-й символ, вы попадаете в одно из трех возможных состояний:

• я == к
• я == н
• еще

Что вы печатаете в каждом из этих трех случаев?