Torres de Hanói: solução iterativa. Qualquer programa que possa ser implementado recursivamente pode ser implementado iterativamente, embora, às vezes, com muito mais dificuldade e muito menos clareza. Tente escrever uma versão iterativa das Torres de Hanói. Se obtiver sucesso, compare sua versão iterativa com a versão recursiva desenvolvida por você no Exercício 5.36. Investigue as questões de desempenho, clareza e sua capacidade de demonstrar a exatidão dos programas.

Passo 1

Fala Galera!!! Tudo certo? Espero que sim!!! Bora para mais um exercício.

Nesse exercício vamos tentar escrever uma solução interativa para Torre de Hanói. Soluções iterativas são aquelas que resolvem um problema sem usar recursão, usando laços de repetição e em alguns casos, estruturas de dados, como pilha, fila, árvore, etc. No caso da torre de Hanói, a solução recursiva é muito mais intuitiva do que suas soluções iterativas, pois essas últimas necessitam de uma análise especial nas movimentações dos discos. uma solução iterativa que utiliza os bits de um certo número k para gerar as movimentações. 

Passo 2

Vamos usar uma solução iterativa que utiliza os bits de um certo número k para gerar as movimentações.

/* Sendo 3 o número de discos.

*/

#include

#include /* for atoi() */

int main(int argc, char **argv) {

int n = 3 ;

int from, to, k ;

if ( argc > 1 ) n = atoi(argv[1]) ;

for(k=1; k

/* obtem haste origem */

from = (k&(k-1))%3 ;

/* obtem haste destino */

to = ((k|(k-1))+1)%3 ;

/* descreve o movimento */

printf("Mova disco de %d para %d\n", from, to) ;

}

return 0;

}

Considere k como o movimento de algum disco. Sabemos que para n=3 discos, temos no total 7 movimentos e com isso, o k varia de 1 a 7. É fácil notar que para k ímpar o disco número 1 é que se movimenta e esse movimento é descrito pela sequência 0->2->1->0 para n ímpar e por 0->1->2->0 para n par. Em termos de k, o disco 1 se move da haste (k-1)%3 para a haste (k+1)%3, independente do n. Para k par, podemos ter discos ímpares ou pares se movimentando. Para discos ímpares, eles sempre se movem da haste (k+2)%3 para a haste (k+4)%3. Os discos pares se movimentam em ordem inversa, ou seja, da haste (k+4)%3 para a haste (k+2)%3.

Passo 3

No código a mágica toda é feita usando manipulação de bits. A condição do laço for é dada por (1

A forma iterativa possui melhor desempenho por evitar as chamadas recursivas que utilizam a pilha para armazenar os dados da função (parâmetros e variáveis locais). Quanto mais recursão, mais a pilha é consumida e isso prejudica a execução do programa.

Resposta

Desenvolvimento acima.