Torre de Hanói

A Torre de Hanói é um "quebra-cabeça" que consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo.

O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação. O número de discos pode variar sendo que o mais simples contém apenas três.

A Torre de Hanói tem sido tradicionalmente considerada como um procedimento para avaliação da capacidade de meméria de trabalho, e principalmente de planejamento e solução de problemas.

 Exemplo Com Quatro Discos



Número de movimentos ótimos: 15
Cálculo de movimentos: 2 elevado ao número de discos, menos 1. [(2^n)-1]

 Recursão de Cauda

Diz-se que uma rotina apresenta recursão de cauda, se sua chamada for efetuada no final do seu código, criando a função de looping até que a condição de parada a encerre.
As funções recursivas em cauda formam uma subclasse das funções recursivas, nas quais a chamada recursiva é a última instrução a ser executada.
O algoritmo da Torre de Hanói, é tipicamente uma função recursiva em cauda.

 Código

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void hanoi(int disco, char orig, char dest, char aux) {

if (disco == 1)
printf("Move disco %d de %c para %c\n", disco, orig, dest);

else {
hanoi(disco - 1, orig, aux, dest);
printf("Move disco %d de %c para %c\n", disco, orig, dest);
hanoi(disco - 1, aux, dest, orig);
}

}
int main(void) {
setbuf(stdout, NULL);
printf("** Torre de Hanoi **\n");
int n;
char sair;
do {
do {
printf("\nDigite o numero de discos: ");
fflush(stdin);
scanf("%d", &n);
if (n > 10)
printf("\nLimite de discos excedido!(10)\n");
} while (n > 10);
printf("\n");
hanoi(n, 'A', 'B', 'C');
printf("\nNumero de movimentos otimos: %.0f\n\n", pow(2, n) - 1);
printf("Deseja sair? (s/n): ");
fflush(stdin);
scanf("%c", &sair);
}while (sair == 'n');
printf("\nVoce saiu do programa.");

return 0;
}