Homework 5 - Le Torri di Hanoi

Vedi: DomandeHomework5, SoluzioneHomework5, RisultatiHomework5.

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:

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);
     } 
}  

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

hanoi(0,1,2, ndischi)

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

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

Scadenza

L'esercizio dev'essere consegnato entro mercoledì 10 Dicembre alle ore 24 .

Consegna degli esercizi

  • Attenzione: viste numerose richieste, ho deciso di prorogare la scadenza dell'homework 4 a mercoledì 22 dicembre sempre alle 23:59.
  • La scadenza dell'Homework 5 è stata (ri)fissatta per venerdì 14 gennaio 2005 sempre alle 23:59.
  • Dovete essere iscritti a twiki
  • Dovete aver mostrato un documento di identità a Ivano Salvo (oppure mandatemene una scansione per email)
  • Vi devo aver abilitato (controllate in StudentiProg1Group o ArchitettureUnoGroup )
  • Gli esercizi vanno consegnati esclusivamente usando la pagina di consegna: ATTENZIONE in questo momento sono attive due pagine, una per l'homework 4 e una per l'homework 5.
Evitate di fare confusione!

    • Io registro/abilito nuovi iscritti e aggiorno password solo fino al venerdì sera
    • quindi fate una prova durante la settimana per controllare che tutto vi funzioni!
  • Non verranno accettati esercizi consegnati per email
  • Ora sono le 01:53


This topic: Programmazione1/AA0506/PZ > HomeWork5
Topic revision: r25 - 2003-12-14 - AndreaSterbini
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback