oTorres de Hanói O problema é um problema clássico de recursão. Você recebe três pinos com discos em um deles e deve mover todos os discos de um pinos para outro, seguindo as regras fornecidas. Você também deve fazer isso com o número mínimo de movimentos.

Aqui está um algoritmo recursivo que resolve o problema:

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

Agora, imagine o mesmo problema, apenas com 4 pinos, por isso adicionamos outro pinos intermediário. Quando nos deparamos com o problema de ter que escolher qual peg intermediário escolher em qualquer ponto, escolheremos o mais à esquerda, caso mais de 1 seja gratuito.

Eu tenho o seguinte algoritmo recursivo para esse problema:

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

Agora, minha pergunta é como generalizaria essa abordagem recursiva para trabalhar paraK estacas? A função recursiva receberia umchar[] que conteria os rótulos de cada pilha, então a função seria algo como isto:

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

Conheço o algoritmo Frame-Stewart, que provavelmente é ideal, mas não comprovado, e que oferece a vocênúmero de movimentos. No entanto, estou interessado em uma solução estritamente recursiva que segue o padrão das soluções recursivas para 3 e 4 pinos, o que significa que imprime os movimentos reais.

Para mim, pelo menos, o pseudocódigo do algoritmo Frame-Stewart apresentado na Wikipedia é bastante abstrato, e não consegui convertê-lo em código que imprima as jogadas. Eu aceitaria uma implementação de referência disso (por acasok) ou pseudocódigo ainda mais detalhado.

Tentei criar algum tipo de algoritmo que permita a matriz de rótulos de acordo, mas não tive sorte em fazê-lo funcionar. Todas as sugestões são apreciadas.

Atualizar:

Isso parece ser muito mais fácil de resolver em uma linguagem funcional. Aqui está uma implementação de F # baseada na solução Haskell de 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]

E sem tratar três pinos como um caso de borda:

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)

Observe que isso não lida com casos degenerados para os quais não há solução, comoHanoiK 2 [1; 2]