


"E' il compleanno di Lola e gli amici le stanno preparando una festa a sorpresa con una bella torta. Ma...è un problema spostarla sul tavolino centrale.Muovendo un piano alla volta, qual è il minor numero di spostamenti necessario?"
Questo è il quesito che viene posto da "La Settimana Enigmistica" di questa settimana.
Il problema è quello tipico della 'Torre di Hanoi', solo che in questo caso al posto degli anelli abbiamo i piani della torta e al posto dei pioli i tavolini.
Iniziamo a ragionare.
Il problema ci chiede di spostare tutti i piani sul tavolino centrale che quindi sarà il nostro tavolino finale, immaginiamo quindi di spostare tutti i piani, tranne l'ultimo, dal primo all'ultimo tavolino lasciando così libero il tavolino centrale. A questo punto si può spostare il piano più grande, che si trova sul primo tavolino, sul tavolino finale, cioè quello centrale, quindi, come prima, si può spostare in qualche modo tutti i piani sopra quello più grande.
Per questo il problema può essere risolto attraverso un algoritmo ricorsivo. E' ora che entra in gioco il nostro amico Pascal:
Program Torta;
uses crt;
var
n,t1,t2:integer;
c:integer;
Procedure Spostamento(n,t1,t2:integer);
Begin
if n>0 then
Begin
Spostamento(n-1,t1,6-t1-t2);
inc(c);
Spostamento(n-1,6-t1-t2,t2)
end
end;
Begin
clrscr;
write('Inserisci il numero dei piani della torta:');
readln(n);
t1:=1; (*supponiamo che il tavolino iniz sia sempre 1*)
write('Supponendo che la torta sia sul tavolino 1 e che i tavolini siano disposti 1,2,3 indicare il tavolino finale:');
readln(t2);
Spostamento(n,t1,t2);
writeln;
writeln('Numero spostamenti effettuati:',c);
readln
end.
Spendiamo due parole sulla codifica:
n rappresenta il numero dei piani della torta;
t1 rappresenta il tavolino su cui è posizionata inizialmente la torta;
t2 rappresenta il tavolino su cui la torta deve essere spostata alla fine;
6-t1-t2 rappresenta il tavolino di appoggio (visto che i tavolini sono 3)
In pratica il programma attraverso la procedura Spostamento simulerà ogni volta di spostare il piano più grande da t1 al tavolino di appoggio [Spostamento(n-1,t1,6-t1-t2)], a questo punto incrementerà il contatore che ci serve per contare il numero delle mosse [inc(c)] e infine si preoccuperà di "aggiornare" la procedura portando quello che per noi ora è t1 a 6-p1-p2, cioè al tavolino di appoggio, e quello che per noi era 6-p1-p2 a p2, cioè al tavolino finale [Spostamento(n-1,t1,6-t1-t2)], è in questo passaggio che avremo la ricorsione.
Concludendo facendo girare il nostro programmino con Turbo Pascal scopriremo che Susi dovrà fare minimo 15 mosse per spostare la sul tavolino centrale senza combinare un disastro.