01: // la ricorsione, esempio Torre Hanoi
02: #include<stdio.h>
03: #include<stdlib.h>
04: 
05: 
06: /*
07:    spostare N dischi dal piolo X al piolo Y io lo posso vedere come
08:    se(N>0)
09:     - spostare N-1 dischi dal piolo X al terzo piolo
10:     - spostare 1 disco dal piolo X al piolo Y
11:     - spostare N-1 dischi dal terzo piolo al piolo Y
12:    altrimenti
13:     - esco
14: */
15: 
16: 
17: static unsigned long numeromosse;  
18: 
19: void muovidisco (int, int);
20: void muovitorre (int, int, int);
21: 
22: 
23: int main(int argc, char **argv){
24:   int totale;           /* numero di dischi */
25: 
26:   printf("Torre di Hanoi\n");
27:   printf("Quanti dischi? ");
28:   scanf("%d", &totale);
29: 
30:   numeromosse = 0;
31:   muovitorre (totale, 1, 3);
32: 
33:   printf("\nNumero totale mosse per %d dischi =  %ld\n", totale, numeromosse);
34: 
35:   return 0;
36: }
37: 
38: 
39: // Muove una torre di "altezza" dischi dal disco partenza al disco arrivo
40: void muovitorre (int altezza, int partenza, int arrivo) {
41: 
42:   if(!altezza) return;
43: 
44:   int ausiliario = 6-partenza-arrivo; // a bit of magic! Ok spiegamola. 1+2+3=6 quindi dati i pioli x e y 6-x-y mi fornisce il terzo piolo
45: 
46:   muovitorre (altezza - 1, partenza, ausiliario);
47:   muovidisco (partenza, arrivo);
48:   muovitorre (altezza - 1, ausiliario, arrivo);
49: 
50: }
51: 
52: 
53: // muovo un singolo disco da sorgente a destinazione
54: void muovidisco (int sorgente, int destinazione) {
55: 
56:   numeromosse++; // aggiorno il numero di mosse fatte
57: 
58:   // in assenza di un servomeccanismo robotico che mi sposti i dischi fornisco semplicemente all'utente la mossa da fare...
59:   printf(" %ld: %d -> %d\n", numeromosse, sorgente, destinazione);
60: }
61: 
62: 
63: 
64: 
65: 
66: 
67: