Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Torre di Hanoi

Precedente
SUPERIORE
Successiva

Nel tempio di Brahma si trova una piattaforma di ottone con tre perni di diamanti. Sul primo di tali perni sono infilati 64 dischi d'oro, di dimensioni decrescenti, che formano una torre.

Si deve portare la torre sul terzo perno, spostando un solo disco alla volta e in modo che mai un disco di diametro maggiore si trovi sopra un disco di diametro minore. Per risolvere la questione si pu˛ utilizzare il secondo perno come perno di servizio.

Quando i monaci termineranno l'opera il mondo sarÓ finito!

Soluzione ricorsiva

Il problema con un solo disco Ŕ banale

sposto il disco dalla 1░ alla 3░ colonna

Se i dischi sono N e se sono riuscito a risolvere il problema con N-1 dischi, allora

sposto N-1 dischi dalla 1░ alla 2░ colonna
sposto il primo disco dalla 1░ alla 3░ colonna
sposto N-1 dischi dalla 2░ alla 3░ colonna

Se spostare N-1 dischi viene interpretato come una chiamata ricorsiva...

Codifica

procedure Hanoi(N, Origine, Libero, Arrivo: Byte);
begin
   if(N = 1) then
      write(Origine:2, ' --> ', Arrivo:2)
   else
      begin
         Hanoi(N-1, Origine, Arrivo , Libero);
         Hanoi(1  , Origine, Libero , Arrivo);
         Hanoi(N-1, Libero , Origine, Arrivo);
      end;
end;

I parametri Origine, Libero, Arrivo assumono alla chiamata i valori 1, 2, 3 rispettivamente e quindi la chiamata iniziale Ŕ sempre Hanoi(N, 1, 2, 3).

Simuliamo le chiamate ricorsive per N=1

H(1, 1, 2, 3)
1 --> 3

N=2

H(2, 1, 2, 3)

H(1, 1, 3, 2)H(1, 1, 2, 3)H(1, 2, 1, 3)
1 --> 21 --> 32 --> 3

N=3

H(3, 1, 2, 3)

H(2, 1, 3, 2)

H(1, 1, 2, 3)

H(2, 2, 1, 3)

H(1, 1, 2, 3)H(1, 1, 3, 2)H(1, 3, 1, 2)1 --> 3H(1, 2, 3, 1)H(1, 2, 1, 3)H(1, 1, 2, 3)
1 --> 31 --> 23 --> 22 --> 12 --> 31 --> 3

...

La soluzione Ŕ data dalle mosse evidenziate.

ComplessitÓ del problema

Torre di Hanoi - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Precedente
SUPERIORE
Successiva