Presentarem en aquesta pràctica l'antic joc de les torres de Hanoi, un dels exemples clàssics d'algoritme recursiu. 

Desenvolupament de la pràctica

El joc parteix de tres bases A, B i C . En aquestes bases es poden posar discos, tots de mida diferent, de forma que mai pot estar un disc a sobre d'un altre disc més petit. Si tots els discos estan inicialment a la base A, el joc consisteix en traslladar-los d'un en un fins posar-los a la base C, mantenint sempre la regla que un disc mai estigui a sobre d'un altre més petit.

El següent programa implementa aquest procés amb la funció recursiva Hanoi():

Creeu un nou arxiu font C anomenat m4p02.c. i escriviu el següent codi:

 

//m4p02.c - Torres de Hanoi  -   #include <stdio.h> #include <stdlib.h>   void hanoi(int,char,char,char);   int main(){     int n;       system("clear");     printf("introduïu el nombre n de discos :");     scanf("%d",&n);     hanoi(n,'A','C','B');     return 0; }       void hanoi(int n, char A, char C, char B){     if (n==1){         printf("%c->%c\t",A,C);         return;     }     hanoi(n-1,A,B,C);     hanoi(1,A,C,B);     hanoi(n-1,B,C,A); } Captura de l'execució del programa.

Explicació del programa

Si hi ha només un disc, el problema és trivial: és suficient moure l'únic disc d'A fins a C. Anomenarem a aquest algorisme Hanoi(1,A,C)

En el cas que hi hagi dos discos, es pot fer amb tres moviments: A->B, A-> C, B-> C, és a dir, tenim un procediment per passar dos discos d'A a C utilitzant B com ajuda. Anomenarem a aquest algoritme Hanoi(2,A,C,B) (passar dos discos d'A a C fent servir B).

En el cas que hi hagi 3, es pot fer l'algoritme Hanoi(2,A,B,C),és a dir, col·locar 2 discos d'A a B fent servir C com ajuda,  Hanoi(1,A,C,B), és a dir, col·locar el disc que hi ha a A en C i, per últim,  Hanoi(2,B,C,A), és a dir, col·locar els dos discos que hi ha en B a C fent servir A com ajuda. A tot aquest procés li direm Hanoi(3,A,C,B).