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

Question

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

А представляет собой строку символов (например, А = «Привет») и обмен, который является абстракция, обменивается к-й с г-го символа А, например, CALL-обмен («привет», 2, 3) изменит «привет» на «hlelo»).

Идея заключается в том, чтобы напечатать все возможные перестановки Версию в 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, который кажется только появиться в Horowitz книге «алгоритмы и структуры данных ". Он поставил вопрос в 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

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

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

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

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

Вот подсказка, без вашей домашней работы для вас. Когда вы идете вниз строку, глядя на го персонажа, вы находитесь в одном из трех возможных состояний:

• я == к
• я == п
• еще

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