LogRitmo navegador / ativofase / 04LR / fase 04 · ativaMova uma torre respeitando uma regra simples e um custo inevitável.
Para mover n discos, mova n−1 para o auxiliar, mova o maior para o destino e repita o processo.
Passo 1 · Antes de mover o disco 3, os menores precisam sair do caminho.
Passo 1: Antes de mover o disco 3, os menores precisam sair do caminho.
Cada chamada recursiva pode gerar novas chamadas. Em Fibonacci ingênuo e Towers of Hanoi, o total de trabalho cresce muito mais rápido que n.
Adicionar uma unidade a n pode quase dobrar o trabalho; memoização em Fibonacci evita recomputações e reduz o tempo para O(n).Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Use este par para contrastar operações locais de extremidade com uma decomposição recursiva cujo número de movimentos cresce exponencialmente. Stacks & Queues tende a crescer mais devagar do que Towers of Hanoi quando aumentam quantidade de itens (n). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
hanoi(n, origem, destino, auxiliar)se n == 0: parehanoi(n - 1, origem, auxiliar, destino)mova o disco n para destinohanoi(n - 1, auxiliar, destino, origem)O destaque acompanha o passo atual; leia a linha destacada antes de avançar.
Torres de Hanoi parece uma sequência de pequenos movimentos, mas sua solução clássica organiza uma prova completa: as regras preservam um invariante, a decomposição alcança o objetivo e a própria necessidade de liberar o maior disco determina o mínimo de passos.
Um movimento retira apenas o topo de um pino e o deposita em um pino vazio ou sobre um disco maior. A meta exige a pilha inteira, ordenada, no destino. Antes do disco n se mover, os n − 1 menores precisam estar juntos no único pino auxiliar; depois, eles precisam voltar sobre ele. Essa necessidade transforma uma sequência válida em uma sequência obrigatória.
Cada pino se comporta como uma pilha: somente o topo fica acessível e os tamanhos descem da base ao topo. Se cada chamada começa com pilhas ordenadas, move discos apenas em destinos permitidos e termina, ela preserva a legalidade de toda a configuração.
Para n = 0, não há movimento. Assumindo que n − 1 discos podem ser transferidos legalmente, o maior fica livre, move uma vez e a mesma hipótese leva a pilha menor para cima dele. A prova cobre corretude, não só um exemplo.
Qualquer solução precisa liberar o maior disco, movê-lo uma vez e restaurar os menores sobre ele. Portanto, M(n) = 2M(n − 1) + 1, com M(0) = 0; assim, M(n) = 2ⁿ − 1 é simultaneamente o custo da solução e um limite inferior.
Uma sequência curta o bastante para observar a decomposição inteira.
A recursão ainda é simples de descrever, mas a animação já requer muitos passos.
Mais de 18 quintilhões de movimentos; trocar a implementação não remove esse limite de saída.
Uma pilha explícita pode simular a recursão, e uma regra baseada no bit menos significativo do passo identifica o disco a mover. Pela leitura de código de Gray, passos consecutivos mudam uma coordenada. Essas formulações evitam a pilha de chamadas, mas continuam emitindo 2ⁿ − 1 movimentos: quando a sequência inteira é necessária, esse custo é inevitável.
Com quatro pinos, uma estratégia pode estacionar uma parte dos discos, resolver o restante e recuperar a primeira parte. A recorrência Frame–Stewart escolhe um ponto de divisão, mas a argumentação elementar que prova a fórmula 2ⁿ − 1 vale especificamente para os três pinos clássicos.
Também é útil olhar o puzzle como um grafo: cada configuração legal é um vértice e cada movimento legal é uma aresta. A solução mínima é um caminho entre os estados inicial e final; essa leitura conecta o exercício a busca em grafos sem confundir uma regra local com progresso global.