Rotinas para Torre de Hanói

Terminada a analise da torre de Hanói, se tem duas funções matemáticas que calculam o numero movimentos necessários para concluir o desafio:

Forma fechada:
Recorrente:

Transpor as expressões para o código requer pouco esforço, as rotinas movesR e movesC que fornecem a solução tanto pela recorrência, como pela forma fechada, seguem abaixo:

#include <stdio.h> #include <math.h> typedef unsigned int    uint; uint movesR(uint n) {       if (n == 0)             return 0;       else             return (2 * movesR(n-1) + 1); } uint movesC(uint n) {       return ((uint) pow(2.0, (double) n)) - 1 ; } void main(void) {       uint n;       for (n = 0; n <= 8; ++n) {             printf("movesR(%u) = %u\n", n, movesR(n));             printf("movesC(%u) = %u\n", n, movesC(n));       } }

                Como a função recorrente para o total de movimentos foi obtida pela simulação de uma torre com 3 disco, está mesma função será usada para percorrer cada movimentos dos discos entre os pinos.

                Quando se criou a rotina recursiva movesR que calculava o numero de movimentos no disco, se adaptou do resultado obtido no exemplo de T(n) =2 * T(n) + 1, entretanto, perceba que estamos multiplicando o resultado como simplificação da expressão T(n) + 1 + T(n), apesar de manter o resultado do total de movimentos, perde-se a sequencia em que os movimentos foram realizados.

                Para corrigir a sequencia de disco, alteramos a rotina movesR, agora nomeada para hanoi, para executar a chamada recursivas duas vezes, indicando a ordem em que os discos foram movimentado:

uint hanoi(uint disk) {       if (disk == 0)             return 0;       else {             uint moves;             moves  = hanoi(disk-1);             moves += 1;       printf("moveu disco %d\n", disk);             moves += hanoi(disk-1);             return moves;       } }

                Próxima informação é indicar os pinos de origem e destino que estão sendo usados, como entrada, incluindo também o pino temporário na chamada:

uint hanoi(uint disk, char src, char dst, char tmp) . . .       moves  = hanoi(disk-1, /* ? */, /* ? */, /* ? */);       moves += 1;       printf("moveu disco %d: ", disk);       printf("pino %c para o pino %c\n", src, dst);       moves += hanoi(disk-1, /* ? */, /* ? */, /* ? */); . . .

                Para definir a seleção de pinos para a rotina, veja a simulação de para hanoi(2, X, Y, Z) e como vão ser executadas as duas chamadas recursiva para o disco 1:

X

Y

Z

1. Movimenta o disco 1 do pino X para o pino Z, faz a primeira chamada recursiva da rotina indicando pino X como origem e o pino Z como destino resultando em hanoi( 1, X, Z, Y ).

X

Y

Z

2. Instante em que imprime o movimento feito em hanoi( 2, X, Y, Z ).

X

Y

Z

3. Chama pela segunda vez a rotina, temos indicado o movimento do disco, desta vez do pino de origem Z para o pino de destino Y com a função carregando os valores hanoi( 1,Z, Y, X ).

X

Y

Z

                Na tabela vemos o processo de substituição das chamadas da simulação pelo nome das variáveis utilizadas na rotina:

hanoi( 2, X, Y, Z )	hanoi( disk, src, dst, tmp)
hanoi( 1, X, Z, Y )	hanoi( disk-1, src, tmp, dst )
hanoi( 1, Z, Y, X )	hanoi( disk-1, tmp, dst, src)

                Com a ordem dos pinos acertada para a primeira e a segunda chamada recursiva dentro da rotina, fica fácil entender a lógica, move-se o disco superior para o pino temporário, move o disco inferior para o destino e retorna novamente para o topo o disco que está no pino temporário.

uint hanoi(uint disk, char src, char dst, char tmp) . . .       moves  = hanoi(disk-1, src, tmp, dst); . . .       moves += hanoi(disk-1, tmp, dst, src); . . .

                A rotina hanoi tem como objetivo gerar o caminho utilizado, podendo assim desprezar o contador de movimentos, simplificando ainda mais o código, o resultante completo fica:

#include <stdio.h> typedef unsigned int    uint; void hanoi(uint disk, char src, char dst, char tmp) {       if (disk != 0)       {             hanoi(disk-1, src, tmp, dst);             printf("moveu disco %d: ", disk);             printf("pino %c para o pino %c\n", src, dst);             hanoi(disk-1, tmp, dst, src);       } } void main(void) {       hanoi(4, 'X', 'Y', 'Z'); }

                Ao rodar o programa a seguinte saída é esperada:

C:\Projects\Hanoi\Debug>hanoi moveu disco 1: pino X para o pino Z moveu disco 2: pino X para o pino Y moveu disco 1: pino Z para o pino Y moveu disco 3: pino X para o pino Z moveu disco 1: pino Y para o pino X moveu disco 2: pino Y para o pino Z moveu disco 1: pino X para o pino Z moveu disco 4: pino X para o pino Y moveu disco 1: pino Z para o pino Y moveu disco 2: pino Z para o pino X moveu disco 1: pino Y para o pino X moveu disco 3: pino Z para o pino Y moveu disco 1: pino X para o pino Z moveu disco 2: pino X para o pino Y moveu disco 1: pino Z para o pino Y