Torre di hanoi

di il
8 risposte

Torre di hanoi

Salve a tutti.
Nel preparare un esame universitario , mi sono imbattuto nella Ricorsività multipla.
Il concetto di CHIAMATA RICORSIVA , nel caso di 1 singola funzione mi è chiaro .
Quello che non mi è chiaro è : come si comporta il compilatore passo per passo nel caso in cui nel corpo di una certa funzione ci siano più chiamate a sé stessa.
#include <stdio.h>

#define DISCHI 100

int mossa; //la definisco come variabile globale per usarla anche nella funzione

void hanoi(int n_dischi, char orig, char dest , char aus);
//dove orig è il piolo da dove prendo i dischi, dest dove voglio spostarli, aus come ausilio

int main()
{
	mossa=0; //la inizializzo per il sottoprogramma hanoi
	
	printf("Risoluzione torre di Hanoi\n");
	printf("Numero di dischi inseriti: %d\n\n",DISCHI);
	
	hanoi(DISCHI,'A','C','B');
	/*al sottoprogramma hanoi devo passare:
	 * 1) Il numero di dischi
	 * 2) Il nome del piolo di origine (dove iniziano tutti i dischi)
	 * 3) Il nome del piolo di arrivo (dove arrivano tutti i dischi)
	 * 4) Il nome del piolo di ausilio */
	 
	 //N.B. Non confondere i parametri che stai passando ora, con quelli nel sottoprogramma.
	 //Nel main passi i valori effettivi del problema, mentre nel sottoprogramma passerai
	 //i valori risolutivi della ricorsione. Nel main il campo orig vuole il punto di partenza del problema
	 //il campo dest vuole dove voglio spostare tutti i dischi.
	 //Invece nel sottoprogramma il campo orig cambierà di significato a seconda della risoluzione
	 //della ricorsione
}

void hanoi(int n_dischi, char orig, char dest, char aus)
{
	if (n_dischi==1)
	{
		mossa++;
		printf("%d) Sposta disco da %c a %c\n", mossa, orig, dest);
	}
	else
	{
		hanoi(n_dischi-1,orig,aus,dest);
		//cioè voglio spostare n-1 dischi da Origine a Ausilio usando come intermezzo Destinazione
		
		hanoi(1,orig,dest,aus);
		//cioè voglio spostare 1 disco da Origine a Destinazione
		
		hanoi(n_dischi-1,aus,dest,orig);
		//sposto infine gli n-1 dischi dall'Ausilio in Destinazione usando l'Origine come intermezzo
	}
}
Da un punto di vista teorico mi è chiaro qual è la sequenza di azioni base da compiere per portare ad es. 3 dischi dal piolo origine al piolo destinazione , utilizzando il piolo intermedio.
Il tutto rispettando le condizioni di :
1) spostare 1 solo disco per volta
2)non spostare dischi di diametro maggiore su dischi di diametro minore.


Tuttavia, quando vado a simulare il programma "su carta" passo passo \ Chiamata ricorsiva dopo chiamata ricorsiva arrivo a conclusioni errate.
Nello specifico ho:
1) nel main() la CHIAMATA alla funzione hanoi()
2) a questo punto entro con n=3 nel sottoprogramma , eseguo il Controllo , salto nell'else e faccio la CHIAMATA alla 1° funzione() nell'else
ovvero hanoi(2,orig,aus,dest);
3) A questo punto , l'esecuzione per n=3 si blocca in attesa che sia completata la CHIAMATA RICORSIVA di quella funzione
E si ha che: Chiamare hanoi(2,orig,aus,dest); significa rientrare nello stesso sottoprogramma .
Quindi eseguo il Controllo if(n==1) ? NO perché siamo entrati con n=2 e salto all'else (di questa che in memoria è una replica della funzione precedente).
Ora nell'else mi ritrovo di nuovo ad eseguire la 1° funzione ovvero hanoi(n_dischi-1,orig,aus,dest);
che in questo casos sarò hanoi(1,orig,aus,dest);
4) A questo punto l'esecuzione di quel secondo stage (per n=2) si blocca in attesa che sia terminata la chiamata ad hanoi(1,orig,aus,dest);
--> di nuovo rientro nel sottoprogramma ma questa volta con n=1 quindi questa volta quel 1° check è verificato.

PROBLEMA: avendo fatto giocare il ruolo di "piolo destinazione" al "piolo ausiliario" , quell'istruzione:
printf("%d) Sposta disco da %c a %c\n", mossa, orig, dest);
mi dovrebbe stampare "sposta disco da origine ad ausiliario"//modo simbolico per spostare 1 disco da ... a...

Tuttavia , nella soluzione , mi si dice che la 1° Azione BASE , dev'essere quella di spostare il primo disco da origine a destinazione H_o,d(1)
ed io invece mi trovo H_o,i(1).
Soluzione:

8 Risposte

  • Re: Torre di hanoi

    Non si è capito molto.

    In ogni caso vale il consiglio che si dà a tutti: non c'è nessuna differenza tra le chiamate ricorsive e le chiamate a funzioni ordinarie. Scrivi su carta le chiamate hanoi_01() hanoi_02() hanoi_03() eccetera, come se fossero realmente funzioni differenti
  • Re: Torre di hanoi

    Premessa: grazie per la risposta

    L'ordine con cui (secondo quel che ho capito) dovrebbero essere eseguite le funzioni non risulta essere quello con cui (ultima immagine) queste vengono eseguite. Non capisco il perché.
    Nello specifico al posto del punto 3 funzione H_o,d(1)[vedi ultima immagine] a me risulta debba essere eseguita la funzione H_o,i(1) perché quando ho fatto la chiamata ricorsiva ad H_o,i(2) [vedi punto2 ultima immagine] sono rientrato nella stessa funzione con n=2 e dunque saltato alla 1°istruzione dell'else.
  • Re: Torre di hanoi

    Se ho capito bene parti da hanoi(3,'A','C','B');

    Quindi avrai:
    
    main chiama hanoi_01(3,'A','C','B')
    	hanoi_01 passa dall'else e chiama hanoi_02(2,'A','B','C')
    		hanoi_02 passa dall'else e chiama hanoi_03(1,'A','C','B')
    			hanoi_03 passa dall'if e termina la sua esecuzione, quindi riprende l'esecuzione hanoi_02(2,'A','B','C')
    		hanoi_02 passa alla riga successiva e chiama hanoi_04(1,'A','B','C')
    
    ... eccetera
  • Re: Torre di hanoi

    e chiama hanoi_03(1,'A','C','B')
    Ecco, qui mi perdo.
    Mi perdo, perché quando Chiamo hanoi_02(2,'A','B','C') (e dunque rientro nel sottoprogramma, eseguo il controllo: 2 uguale1?No, passo all'else)
    nell'else la 1°istruzione è una chiamata del tipo hanoi(n-1,origine,ausiliario,destinazione); . Ciò significa che :
    considerato il Prototipo del sottoprogramma ovvero void hanoi(int n_dischi, char orig, char dest , char aus);
    "in questa Chiamata sto passando come parametri: 'A' come origine e 'B'(o più in generale quello che gioca il ruolo di ausiliario) come destinazione.

    Questo mi porta ad avere \ a CHIAMARE hanoi_03(1,'A','B','C') <---> e NON hanoi_03(1,'A','C','B')
    e cioè mi porta a spostare il 1°disco su quello ausiliario e non sul piolo di destinazione (come dovrebbe essere)
  • Re: Torre di hanoi

    pepp1995 ha scritto:


    Questo mi porta ad avere hanoi_03(1,'A','B','C')
    Ma cosa c'è da perdersi?

    hanoi_02(n_dischi=2, orig='A',dest='B',aus='C') chiama hanoi_03(n_dischi-1,orig,aus,dest) cioè appunto hanoi_03(2-1,'A','C','B') ossia hanoi_03(1,'A','C','B')

    così come pinco(n_dischi=2, orig='A',dest='B',aus='C') chiamerebbe palla(1,'A','C','B')

    Questo fa il compilatore, poi la correttezza dell'algoritmo sta a te valutarla
  • Re: Torre di hanoi

    hanoi_02(n_dischi=2, orig='A',dest='B',aus='C')
    Ma la 1° Chiamata nell'else è hanoi(n-1,orig,aus,dest); perché hai cambiato l'odine dei parametri?

    La logica di esecuzione che seguo è :
    1. vado nel main() : hanoi(n,'A','C','B'); --> 'A' gioca il ruolo di orig, 'C' gioca il ruolo di dest, 'B' gioca il ruolo di aus
    2. vado una 1°volta alla 1° istruzione dell'else : hanoi(n-1,orig,aus,dest); che quindi si traduce nel chiamare hanoi(2,'A','B','C');
    perché alla funzione() nello step precedente ,rispetto al prototipo, ho passato 'B' col ruolo di parametro aus e 'C' col ruolo di parametro dest .
    3.vado una 2°volta alla 1°istruzione dell'else: hanoi(n-1,orig,aus,dest); che quindi si traduce nel chiamare hanoi(1,'A','C','B');
    perché alla funzione() nello step\Chiamata precedente ,rispetto al prototipo,ho passato 'C' col ruolo di parametro aus e 'B' col ruolo di parametro dest.

    Confermi?
  • Re: Torre di hanoi

    pepp1995 ha scritto:


    hanoi_02(n_dischi=2, orig='A',dest='B',aus='C')
    Ma la 1° Chiamata nell'else è hanoi(n-1,orig,aus,dest); perché hai cambiato l'odine dei parametri?
    Lo davo per scontato, ma a quanto pare lo devo spiegare: n_dischi, orig, dest e aus sono variabili differenti

    void hanoi_01(int n_dischi_01, char orig_01, char dest_01, char aus_01);

    void hanoi_02(int n_dischi_02, char orig_02, char dest_02, char aus_02);
  • Re: Torre di hanoi

    n_dischi, orig, dest e aus sono variabili differenti
    Questo mi fregava!

    Grazie mille
    I prossimi 14 cfu saranno merito suo sig. Weierstrass
Devi accedere o registrarti per scrivere nel forum
8 risposte