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

Question

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

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

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

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

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

1

algorithm c++data-structures non-recursive recursion

Решение

Другие решения

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

я == к
я == н
еще

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

2

Источник

Accepted Answer

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

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

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

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)
}
}

2