Gabarito disponível
A Torre de Hanói consiste de 3 pinos A, B e C, denominados origem, destino e trabalho, respectivamente, e n discos de diâmetros diferentes. Inicialmente, todos os discos encontram-se empilhados no pino-origem, em ordem decrescente de tamanho, de baixo para cima. O objetivo é empilhar todos os discos no pino-destino, conforme as seguintes restrições:
I- apenas um disco pode ser movido de cada vez; e
II- qualquer disco não pode ser jamais colocado sobre outro de tamanho menor.
Com base em Szwarcfiter (2010), considere a solução por recursão do problema da Torre de Hanói apresentada abaixo e assinale a opção que substitui os trechos 1 e 2, respectivamente.
procedimento hanoi(n, A, B, C)
Se n > 0 então
<trecho1>
mover o disco do topo de A para B
<trecho2>
chamada externa: hanoi(n, A, B, C).
I- apenas um disco pode ser movido de cada vez; e
II- qualquer disco não pode ser jamais colocado sobre outro de tamanho menor.
Com base em Szwarcfiter (2010), considere a solução por recursão do problema da Torre de Hanói apresentada abaixo e assinale a opção que substitui os trechos 1 e 2, respectivamente.
procedimento hanoi(n, A, B, C)
Se n > 0 então
<trecho1>
mover o disco do topo de A para B
<trecho2>
chamada externa: hanoi(n, A, B, C).
Resolução comentada
Mover n-1 de A para C, mover o maior para B, mover n-1 de C para B.
Com origem A, destino B e trabalho C, o trecho 1 move n-1 discos de A para C usando B como auxiliar: hanoi(n-1, A, C, B). Depois move-se o maior disco de A para B. O trecho 2 move os n-1 discos de C para B usando A: hanoi(n-1, C, B, A).
Análise das alternativas
B, C, D e E) Usam n+1 ou n (sem reduzir o problema, o que não termina) ou trocam os pinos, o que não leva os discos à configuração correta.
Referência: SZWARCFITER, J. L. Estruturas de Dados e seus Algoritmos (2010), recursão.
Resolução comentada do VaiConcursos.