Atividade I
Construa um algoritmo, escrito em PHP, tal que resolva o seguinte problema:
Em uma base são postos 3 pinos, A, B e C. Inicialmente, no pino A encontram-se empilhados um total de n discos organizados em ordem crescente de diâmetro de cima para baixo. A Figura 1 ilustra a disposição dos discos e dos três pinos. A partir desta organização, o problema é encontrar quais são as movimentações necessárias para transferir todos os discos do pino A para o pino C.
Para transferir os n discos, as movimentações devem respeitar as seguintes regras:
Não é permitido movimentar mais de 1 disco por vez
Um disco maior nunca pode ficar em cima de outro menor
Não há limites para o número de movimentações de discos entre os pinos.
O algoritmo a ser construído deverá ter como entrada a quantidade de discos empilhados e ter como saída uma lista com toda a sequência de movimentos (ex. 27. A \rightarrow B, 28. C \rightarrow B) para resolver o problema. Deve constar também a exibição de cada elemento desta lista na tela no computador incluindo seu respectivo índice e começando a partir do número 1.
Dicas
Antes de começar a planejar quais comandos utilizar, faça um esboço do mecanismo de solução do problema encontrado por você. Esse esboço pode ser em palavras, em diagrama ou mesmo em desenho. O importante é que sua ideia de estratégia para resolver o problema fique claro. Na sequência, escreva as rotinas e procedimentos que transcreva a lógica desenvolvida no passo anterior. Por fim, passe para a parte de implementação do seu algoritmo.
A pilha de discos de tamanho n é uma réplica de uma pilha de tamanho n+m, em que n,\,m\in\mathbb{N}. Desta forma, não há diferença na estrutura entre as pilhas, apenas no valor de um atributo, mas não em suas naturezas.
Logo, o algoritmo que resolve o problema para uma pilha de n discos deve ter a mesma mecânica para uma pilha de tamanho n+m. A diferença entre ambas deve ser apenas o número de passos executados para equacionar cada uma das pilhas.
Tente montar a estrutura lógica de um algoritmo onde o problema se restringe a apenas 2 discos. Ao terminar de montar, perceba que as configurações exibida na Figura 3 são indiferentes para solucionar a transferência de 2 discos.
