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
|
