Torre di hanoi col metodo iterativo

di Anonimizzato21817 il
8 risposte
/
Anonimizzato21817
Utente anonimizzato
Sono curioso di sapere se cosa si basa il metodo iterativo della torre di hanoi, quello ricorsivo l'ho implementato molto facilmente, mentre per quello iterativo non ho la più pallida idea da dove bisogna iniziare. Ho sentito che si basa sulla struttura dati stack, che ancora non ho studiato, ma esistono altri metodi o no?

8 Risposte

  • Super Famoso
    Iscritto da
    nov, 2011
    Messaggi
    21917
    La versione ricorsiva usa lo stack di sistema automaticamente.

    Altrimenti devi implementare una struttura stack tua, che se non conosci ...
  • /
    Anonimizzato21817
    Utente anonimizzato
    Ah quindi tutte e due le versioni hanno in fondo lo stesso funzionamento, solo che nell'iterazione lo dovrei implementare io, giusto? Non esistono altre alternative, per esempio qualche sistema basato sulle operazioni bit a bit?
  • Super Famoso
    Iscritto da
    nov, 2011
    Messaggi
    21917
    Esiste la possibilità ... semplicemente
    
#include <stdio.h>

void torre(int nel) 
{
	int numpassi = 1 << nel;
	int passo, mossaDa, mossaA;

	for (passo=1; passo<numpassi; passo++) 
	{
		mossaDa = (passo & (passo-1)) % 3;
		mossaA = (1 + (passo | (passo-1))) % 3;
		
		printf("Mossa %d: da %d a %d\n", passo, mossaDa + 1, mossaA + 1);
	}
}

int main(int argc, char *argv[])
{
	torre(4);
	
	return 0;
}
  • /
    Anonimizzato21817
    Utente anonimizzato
    Ah perfetto, inizierò a studiare le strutture dati e proverò ad implementare la versione iterativa. Ma questo che hai scritto si basa anch'esso sullo stack di sistema?
  • Super Famoso
    Iscritto da
    nov, 2011
    Messaggi
    21917
    Non é ricorsiva, quindi no
  • /
    Anonimizzato21817
    Utente anonimizzato
    Perfetto, grazie milleper l'aiuto, buona serata!
  • /
    Anonimizzato24046
    Utente anonimizzato

    olegfresi ha scritto:

    Sono curioso di sapere se cosa si basa il metodo iterativo della torre di hanoi
    Senza toglierti il piacere di realizzare il semplice programma di risoluzione iterativa, posso dirti le regole pratiche per risolvere il gioco "a mano".
    Consideriamo i 3 pioli numerati 1, 2 e 3 da sinistra a destra, con i dischi inizialmente nel piolo 1.

    La risoluzione si basa sull'applicazione ripetuta di queste due regole:
    1. spostare il disco più piccolo sul piolo successivo, ritornando al piolo 1 quando è sul piolo 3.
    2. effettuare l'unica altra mossa possibile senza muovere il disco più piccolo.
    Ripetere dal numero 1, fino a completa soluzione.

    E' un metodo molto meccanico, non richiede alcuna riflessione, solo un po' di destrezza; qualche anno fa mi ci ero dedicato per qualche sera, arrivando a risolvere la versione a 8 dischi (255 mosse) in circa 100 secondi (a mano, con dischi e pioli "reali", non con un programma!)
  • /
    Anonimizzato21817
    Utente anonimizzato
    Grazie per questo consiglio,claudio
Devi accedere o registrarti per scrivere nel forum
8 risposte