HomeWork5 < Programmazione1/AA0506/PZ

---++ Homework 5 - Le Torri di Hanoi
Vedi: DomandeHomework5, SoluzioneHomework5, RisultatiHomework5.
---
%TOC%
---
Il problema delle Torri di Hanoi deriva da una antica leggenda indiana che recita così: _«nel grande tempio di Brahma a Benares, su di un piatto di ottone, sotto la cupola che segna il centro del mondo, si trovano 64 dischi d'oro puro che i monaci spostano uno alla volta infilandoli in un ago di diamanti, seguendo l'immutabile legge di Brahma: nessun disco può essere posato su un altro più piccolo. All'inizio del mondo tutti i 64 dischi erano infilati in un ago e formavano la Torre di Brahma. Il processo di spostamento dei dischi da un ago all'altro è tuttora in corso. Quando l'ultimo disco sarà finalmente piazzato a formare di nuovo la Torre di Brahma in un ago diverso, allora arriverà la fine del mondo e tutto si trasformerà in polvere»_.

(Nella leggenda i monaci spostano un disco al giorno, ma anche spostando 1 disco al secondo l'universo
durerebbe 585 miliardi di anni... non c'e' di che preoccuparsi!)

Quindi: ci sono _n_ dischi inizialmente infilati in un piolo che chiameremo _sorgente_ (il più grande è sotto e via via decrescendo fino al più piccolo che è in cima). Lo scopo del gioco è portare i dischi nel piolo che chiameremo _destinazione_, aiutandosi con un terzo piolo che chiameremo _ausiliario_, muovendoli _uno alla volta_ e rispettando l'immutabile legge di Brahama: _nessun disco può essere posato sopra un altro di diametro più piccolo_.

Esiste una elegante soluzione ricorsiva a questo problema, che si basa sul seguente ragionamento induttivo:
   * risolvere il problema con un solo disco è banale
   * per spostare _n---+1_ dischi, si spostano _n_ dischi sul piolo ausiliario (usando il piolo destinazione come appoggio), poi si sposta il disco grande sul piolo destinazione e infine si spostano gli _n_ dischi dal piolo ausiliario sopra a quello grande sul piolo destinazione usando il piolo sorgente come appoggio.
  
Possiamo facilmente codificare questa strategia in C, per ottenere una procedura che ricevuto in input il numero di dischi, produce in output _le mosse_ necessarie a risolvere il problema della torre di hanoi:
<pre style="background:lightblue">
<verbatim>
void hanoi(int sorg, int aux, int dest, int n)
/* sposta n dischi dal piolo sorg al piolo dest, 
 * usando il piolo aux come appoggio
 */
{ if (n==1)
     { printf ("muovi dal piolo %d  al piolo %d \n",sorg,dest);}
  else 
     {hanoi(sorg, dest, aux, n-1);
      printf("muovi dal piolo %d  al piolo %d \n",sorg,dest);
      hanoi(aux, sorg, dest, n-1);
     } 
}  
</verbatim>
</pre> 

I pioli sono rappresentati da numeri interi, ad esempio, 0, 1, 2, per cui la chiamata iniziale potrebbe essere: 

<pre style="background:lightblue">
<verbatim>
hanoi(0,1,2, ndischi)
</verbatim>
</pre>

Lo scopo dell'esercitazione sarà quello di modificare opportunamente il programma precedente, in modo
da mostrare tutti gli stati attraversati durante la soluzione del gioco, ossia il contenuto dei pioli
ad ogni mossa.
Rappresentate i dischi con numeri interi da 1 a _n_ (l'intero rappresenta il diametro).
Rappresentate il contenuto di ciascun piolo con una lista di interi.

Il programma accetterà in input il numero dei dischi e produrrà in output gli stati del gioco,
come segue (sotto c'è un esempio di output con 4 dischi). 
Per motivi pratici, formattate l'output scrivendo il numero del disco
a destra di uno spazio di 3 caratteri (suggerisco di non fare test con più di 15 dischi!).
Il piolo vuoto viene rappresentato in output con una lineeta orizzontale.
I pioli sono numerati da 0 a 2.
Osservate nell'esempio qual'è la situazione iniziale.
Buon Lavoro!

Il caso limite di n=0 non va gestito (oppure stampate solo i pioli vuoti e uscite).

---+++ Esempio di output

<pre style="background:lightblue">
<verbatim>
0 :  4  3  2  1
1 :  -
2 :  -

0 :  4  3  2
1 :  1
2 :  -

0 :  4  3
1 :  1
2 :  2

0 :  4  3
1 :  -
2 :  2  1

0 :  4
1 :  3
2 :  2  1

0 :  4  1
1 :  3
2 :  2

0 :  4  1
1 :  3  2
2 :  -

0 :  4
1 :  3  2  1
2 :  -

0 :  -
1 :  3  2  1
2 :  4

0 :  -
1 :  3  2
2 :  4  1

0 :  2
1 :  3
2 :  4  1

0 :  2  1
1 :  3
2 :  4

0 :  2  1
1 :  -
2 :  4  3

0 :  2
1 :  1
2 :  4  3

0 :  -
1 :  1
2 :  4  3  2

0 :  -
1 :  -
2 :  4  3  2  1
</verbatim>
</pre>

---+++ Scadenza
L'esercizio dev'essere consegnato entro *mercoledì 10 Dicembre alle ore 24* .

%INCLUDE{"WebHome"}%

<!--
   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group
-->
This topic: Programmazione1/AA0506/PZ > HomeWork5
Topic revision: r25 - 2003-12-14 - AndreaSterbini