#1
-
- Presumo que as regras básicas para mover os anéis são bem conhecidas.
- Se o número de anéis for estranho, você só precisa de 1 passo para colocar o anel superior em cima do anel que você deseja.
- Se estiver empatado, há a necessidade de dois passos para fazer a mudança. Vamos supor que os pinos A, B e C da esquerda para a direita. Se, por exemplo, em B temos uma pilha com anéis 1,2,3,4 e queremos colocá-los sobre o anel 5 em C , o primeiro passo será 1 a A e 2 para C, e em seguida, 1 a C.. .e com um total de 15 movimentos teremos os 1,2,3,4 anéis sobre 5 na peg C.
- No layout inicial há anéis maiores em cima de anéis menores (essa é a principal diferença da versão I deste jogo), mas quando você começa a jogar você não pode colocar um anel maior em cima de um menor como em Tower of Hanoi I.
- Acho que a melhor abordagem para resolver o jogo é começar com uma rápida olhada nas posições dos anéis 9, 8 e 7. É importante ver se o anel 9 já está na base de um pino. E se não for, qual é a melhor maneira (menos movimentos) para colocá-lo lá. Neste caso, muitas vezes acontece (especialmente se 7 e 8 estão em pinos diferentes) que é preciso colocar 7 sobre 8 para ter um pino livre para 9. Além disso, podemos ter que colocar 6 em 9, 7 movendo-se para o pino livre depois de mover 6 e depois 6 sobre 7 . O resultado será uma pilha de 1 a 7 e a necessidade de 127 movimentos adicionais para colocar esses 7 anéis em cima de 8,9 (o número mínimo de movimentos para resolver um jogo na Situação da Torre de Hanói I é : movimentos mínimos = 2^n - 1 onde n é o número de anéis assim, 3 anéis precisarão de 7 movimentos, 4 anéis precisarão de 15... 7 anéis precisarão de 127 e assim por diante).
- Seja qual for o caso, o objetivo é, com o número mínimo de movimentos possíveis, mudar o layout inicial para uma situação da Torre de Hanói I. Isso significa que você sempre saberá com antecedência se o jogo pode ser resolvido sem ter que realmente terminá-lo. Quando os anéis estão em uma situação torre de Hanói I (uma pilha em ordem ascendente começando com anéis 1,2... em um pino, um pino livre, e um pino com os anéis restantes, também em ordem ascendente, terminando na base do pino onde 9 está), basta adicionar os movimentos já feitos aos movimentos necessários dados pela equação acima e o resultado deve ser igual aos movimentos mínimos necessários (sempre que eu fizer esse controle basta adicionar o último dígito).
- Três exemplos (todos deste site).
- Layout inicial (145 movimentos mínimos necessários)
Peg A - 1,8,2,9
Peg B - 7,3
Peg C - 6,5,4
Passo 1 - A melhor estratégia é colocar 9 na base do peg C e 6 em cima de 7 na estaca B.
O primeiro movimento é: anel 3 em cima de 9 em A, depois 4 em cima de 7 em B...
Depois de 18 movimentos do layout inicial, recebemos:
Peg A - 1
Peg B - 7,6,5,4,3,2 18 movimentos
Peg C – 9,8
Passo 2 – Se olharmos com cuidado para este layout, notamos que isso equivale a 6 anéis em cima de 7 em B, desde que o próximo passo seja colocar o anel 1 em cima de 8 em C. Estamos falando de 6 anéis (6,5 ... 1 ou seja, mesmo, nas estacas B e 2 etapas são necessárias). Então, para colocar esses seis anéis em A precisamos de um primeiro movimento para colocar 1 no outro pino, neste caso C.
Como já sabemos, para mover 6 anéis para outro pino (peg A) precisamos de 63 movimentos. Depois desses movimentos há um adicional para colocar 7, agora livre, em cima de 9,8.
Então, nesta etapa 2 os movimentos serão 63 + 1= 64 e o layout que o obter é:
A - 6,5,4,3,2,1
B - 63+1 = 64 movimentos
C - 9,8,7
Até agora, temos 18 movimentos no Passo 1 mais 64 no Passo 2
Passo 3 – O layout acima corresponde ao que eu chamo de uma torre de Hanói I situação.
Para terminar o jogo precisamos mover os 6 anéis (6,5,... 1) no pino A até o topo de 9,8,7 na estaca C. Isso exigirá mais 63 movimentos.
Total de movimentos= 18 + 64 + 63 = 145 que são os movimentos mínimos necessários. - Layout inicial (256 movimentos mínimos necessários)
A - 5,3,9
B - 8,1,6,4
C - 2,7
Para colocar 9 na base, como 8 e 7 estão em pinos diferentes, precisamos colocar 7 em cima de 8 em B.
Passo 1 - Nosso objetivo é colocar 9 em C e 7 em cima de 8 em B. Para isso, primeiro precisamos passar 6,4 para o topo de 9 em A para liberar C para receber o 9.
Os cinco primeiros movimentos são 4 em cima de 7,6 em cima de 9 em A , 4 a 6,1 a 4 e 7 a 8 no peg B.
Após 20 movimentos, o layout será
A – 5,3
B – 8,7,6,4,2,1 20 movimentos
C – 9
Passo 2 coloque 6 sobre 9 na estaca C. Para isso, precisamos de 4 em cima de 5 em A terminando este Passo 2 com 5,4,3,2,1 na estaca A . Isso é feito com 13 movimentos e o layout é
A – 5,4,3,2,1
B – 8, 7 13 movimentos
C - 9,6
Passo 3 – Mova 5,4...,1 (5 anéis) para o topo de 6 na estaca C. Isso corresponde a 31 movimentos mais 1 para colocar 7 no pino A. Assim, o número de movimentos na Etapa 3 31+1=32 e o layout será
A – 7
B – 8 32 movimentos
C – 9,6,5,4,3,2,1
Passo 4 - Movendo 6,5,... 1 para o topo de 7 no pino A exigirá (6 anéis) 63 movimentos mais outro para colocar 8 em cima de 9 em C. Total move no Passo 4 63+1=64 e no layout
A – 7,6,5,4,3,2,1
B - 63+1 = 64 movimentos
C - 9,8
Passo 5
Temos uma situação na Torre de Hanói I. O passo final é mover os 7 anéis de peg A
para o topo de 9,8 na peg C. Isso significa 127 movimentos.
Total de movimentos- 20 + 13 + 32 + 64 + 127 = 256 movimentos mínimos necessários. - Layout inicial (303 movimentos mínimos necessários)
A – 4,9,7,5,8
B – 6,2
C – 3,1
Este exemplo é um pouco mais difícil do que os dois anteriores.
Note que 9 está preso em A com três anéis no topo (7,5,8). Além disso, B e C não são pinos livres. É claro a necessidade de colocar o 8,7 em um pino grátis caso contrário não teremos um pino livre para 9.
A melhor maneira de fazer isso é colocar 8,7 na estaca C e passar 6 para o topo de 8,7 em C.
Depois que isso for feito, o Peg B estará livre para receber 9. Nota, porém, antes de liberar 7 precisamos colocar 5 em cima de 6 em B.
Passo 1 - Lugar 8, em C e 6,5,3,2,1 na B
Os primeiros sete movimentos são:
2 em A
1 em A
3 no topo B (em cima de 6)
1 em C
2 em B
1 em B
8 em C
23 movimentos após o início temos o layout
A – 4,9
B – 6,5,3,2,1 23 movimentos
C – 8,7
Passo 2 – Coloque os 6,5,3,2,1 (5 anéis) em C em cima de 8,7 (o pino B estará livre para colocar o 9).
Mover 5 anéis para outro pino requer 31 movimentos mais outro para colocar 9 em B assim, nesta etapa precisamos de 31+1 =32 movimentos .
O layout é
A – 4
B – 9 31+1= 32 movimentos
C – 8,7,6,5,3,2,1
Passo 3 – O objetivo agora é liberar o pino A para receber 7 (caso contrário, não podemos colocar 8 em cima de 9). Para isso, é necessário mover 6,5,3,2,1 para B em cima de 9.
Mas como os movimentos são alternativos para colocar 6 em B, anteriormente precisamos colocar os 5 em A e 4 no B...
Depois de 57 movimentos desde o início no Passo 2 teremos o seguinte layout.
A – 7
B – 9,6,5,4,3,2,1 57 movimentos
C – 8
É óbvio que esses 57 movimentos devem seguir uma lógica. Na verdade, eles podem ser decompostos nas seguintes ações
Ação Número de movimentos 4 em B 1 3,2,1 (3 anéis) no top 4 em B 7 5 a A 1 4,3,2,1 (4 anéis) para A 15 6 a B 1 5,4,3,2,1 (5 anéis) para B em cima de 6 31 7 a A 1 Total 57
Passo 4 - mova 6,5....2,1 (6 anéis) para A em cima de 7. Isso precisa de 63 movimentos. Agora é possível colocar 8 em cima de 9 em B, o que significa um movimento adicional.
Então, neste Passo 4 há um total de 63+1 = 64 movimentos
Depois que isso é feito o layout é
A – 7,6,5,4,3,2,1
B – 9,8, 63+1=64 (Torre de Hanói I)
C –
Passo 5 – O passo final é mover 7,6,... 2,1 para colocar B no topo de 9,8 .
Para mover 7 anéis, 127 movimentos serão necessários.
Assim, os movimentos totais são 23+32+57+64+127= 303 movimentos mínimos necessários
- Layout inicial (145 movimentos mínimos necessários)
2020-02-13 08:10:02
Gosto
Responder
#2
Como é que publicaste listas aninhadas, tabelas e sublinhados nos fóruns?
2026-03-29 15:45:37
Gosto
Responder