|
Torre di Hanoi |
   |
|
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 ricorsivaIl problema con un solo disco è banale
Se i dischi sono N e se sono riuscito a risolvere il problema con N-1 dischi, allora
Se spostare N-1 dischi viene interpretato come una chiamata ricorsiva... Codificaprocedure 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
N=2
N=3
... La soluzione è data dalle mosse evidenziate. | |||||||||||||||||||||||||||||||||||||||
|