Torre di hanoi col metodo iterativo

di
Booster
il
8 risposte
B
Booster
Utente Attivo
Iscritto da
lug, 2017
Messaggi:
337

Torre di hanoi col metodo iterativo

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

  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21307

    Re: Torre di hanoi col metodo iterativo

    La versione ricorsiva usa lo stack di sistema automaticamente.

    Altrimenti devi implementare una struttura stack tua, che se non conosci ...
  • B
    Booster
    Utente Attivo
    Iscritto da
    lug, 2017
    Messaggi:
    337

    Re: Torre di hanoi col metodo iterativo

    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?
  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21307

    Re: Torre di hanoi col metodo iterativo

    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;
}
  • B
    Booster
    Utente Attivo
    Iscritto da
    lug, 2017
    Messaggi:
    337

    Re: Torre di hanoi col metodo iterativo

    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?
  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21307

    Re: Torre di hanoi col metodo iterativo

    Non é ricorsiva, quindi no
  • B
    Booster
    Utente Attivo
    Iscritto da
    lug, 2017
    Messaggi:
    337

    Re: Torre di hanoi col metodo iterativo

    Perfetto, grazie milleper l'aiuto, buona serata!
  • C
    ClaudioDz
    Pochi posts
    Iscritto da
    giu, 2018
    Messaggi:
    10

    Re: Torre di hanoi col metodo iterativo

    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!)
  • B
    Booster
    Utente Attivo
    Iscritto da
    lug, 2017
    Messaggi:
    337

    Re: Torre di hanoi col metodo iterativo

    Grazie per questo consiglio,claudio
Devi accedere o registrarti per scrivere nel forum
8 risposte