Hanoi, padrões e mais padrões...

Para solucionar qualquer problema independentemente da sua escala, o primeiro passo é sem duvida entender a sua génese. Identificar e analisar cada mutação, e se possível definir uma formula cujo resultado será um estado verificado no respectivo estágio do problema.
As torres de Hanoi (clique aqui para ver a definição na wikipedia sobre as torres de Hanoi)é um problema típico em que a solução varia em função dos seus argumentos (discos), mas essa mesma solução obedece a um padrão. A existência de padrões normalmente implica uma fórmula matemática computável.

Dissecação do problema

Para começar, é necessário ter uma noção visual do problema e de que forma ele “cresce” em função dos discos

imagem 1


Analisando a imagem 1 podemos concluir que o numero de iterações (coluna i) para a solução de um determinado numero de discos é de ordem exponencial:
Discos - 1: 1 passo
Discos - 2: 3 passos
Discos - 3: 7 passos
Discos - 4: 15 passos
Discos - 5: 31 passos
A solução neste caso é (2^n + 1). Na abordagem iterativa, esta formula é vital, pq permite-nos estabelecer a condição de paragem para o ciclo.

Ciclos dentro de ciclos.
Outro fenómeno observável é a repetição de sequências de passos nas iterações

imagem 2

Identificamos a partir da imagem 2 outro padrão
Discos - 3: 2x(1,2,1)
Discos - 4: 4x(1,2,1), 2x(3,1,2,1)
Discos - 5: 8x(1,2,1), 4x(3,1,2,1), 2x(4,1,2,1,3,1,2,1)
é de notar que cada solução de (n discos) aparece repetida duas vezes na solução de ([n + 1] discos), e que a ocorrência de uma sequência de iterações numa solução aparece a dobrar na solução seguinte.

Já temos uma noção mental da solução das torres de hanoi para qualquer que seja o seu argumento. É no fundo uma repetição de soluções, em que cada sequência contem uma sub-sequência. Mas este conceito baseia-se numa abordagem recursiva. O próximo passo é identificar o processo iterativo, para isso vamos identificar a frequência com que os discos se movem numa solução

Imagem 3


Basicamente o corpo do nosso ciclo está visível nesta imagem. Temos então os seguintes factos:
- O disco 1 é sempre o primeiro disco a ser movido.
- O disco 1 move-se sempre num intervalo de 2 movimentos (1,x,1), e sp numa iteração ímpar.
- Se argumento do numero de discos for par o disco 1 move-se no primeiro passo para a haste B e move-se da esquerda para a direita, caso contrário move-se no primeiro passo para a haste C e move-se da direita para a esquerda.
- Nas iterações pares, move-se o menor disco livre para uma haste livre para ele e excluindo a haste de origem desse disco(lembre que o disco 1 não se move nas iterações pares).

Em suma, esta análise resulta no seguinte fluxograma que utilizei para a abordagem iterativa para as torres de hanoi(presente em "Hiperligações dos meus trabalhos -> Hanoi Soluçao" ).

Fluxograma