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

Вот рекурсивный алгоритм, который решает проблему:

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if( nDisks > 0 )
    {
        Hanoi3(nDisks - 1, source, dest, intermed);
        cout << source << " --> " << dest << endl;
        Hanoi3(nDisks - 1, intermed, source, dest);
    }
}


int main()
{
    Hanoi3(3, 'A', 'B', 'C');

    return 0;
}

Теперь представьте себе ту же проблему, только с 4 колышками, поэтому мы добавим еще один промежуточный колышек. Столкнувшись с проблемой необходимости выбора промежуточного колышка в любой точке, мы выберем самый левый, если больше 1 свободно.

У меня есть следующий рекурсивный алгоритм для этой проблемы:

void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
    if ( nDisks == 1 )
        cout << source << " --> " << dest << endl;
    else if ( nDisks == 2 )
    {
        cout << source << " --> " << intermed1 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed1 << " --> " << dest << endl;
    }
    else
    {
        Hanoi4(nDisks - 2, source, intermed2, dest, intermed1);
        cout << source << " --> " << intermed2 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed2 << " --> " << dest << endl;
        Hanoi4(nDisks - 2, intermed1, source, intermed2, dest);
    }
}

int main()
{
    Hanoi4(3, 'A', 'B', 'C', 'D');

    return 0;
}

Теперь мой вопрос: как бы я обобщил этот рекурсивный подход к работе дляK колышки? Рекурсивная функция получитchar[] который будет содержать метки каждого стека, поэтому функция будет выглядеть примерно так:

void HanoiK(int nDisks, int kStacks, char labels[]) { ... }

Я знаю об алгоритме Фрейма-Стюарта, который, скорее всего, оптимален, но не доказан, и который дает вамчисло ходов. Тем не менее, меня интересует строго рекурсивное решение, которое следует шаблону рекурсивных решений для 3 и 4 колышков, то есть оно печатает фактические ходы.

По крайней мере, для меня псевдокод алгоритма Фрейма-Стюарта, представленный в Википедии, довольно абстрактный, и мне не удалось перевести его в код, который печатает ходы. Я бы принял эталонную реализацию этого (для случайногоk) или даже более подробный псевдокод.

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

Обновить:

Кажется, что это намного проще решить на функциональном языке. Вот реализация F #, основанная на решении Haskell от LarsH:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest when rest.IsEmpty        
            ->  HanoiK (n-1) (p1::p3::p2::rest)
                printfn "%A --> %A" p1 p2
                HanoiK (n-1) (p3::p2::p1::rest)    
        | p1::p2::p3::rest when not rest.IsEmpty    
            ->  let k = int(n / 2)
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

let _ =
    HanoiK 6 [1; 2; 3; 4; 5; 6]

И не рассматривая 3 колышка как крайний случай:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest     
            ->  let k = if rest.IsEmpty then n - 1 else int(n / 2) 
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

Обратите внимание, что это не относится к вырожденным случаям, для которых нет решения, таких какHanoiK 2 [1; 2]