Algoritmo della Torre di Hanoi: Python, C++ Code
Sara Chen
Cos'è la Torre di Hanoi?
La Torre di Hanoi è un puzzle matematico composto da tre aste e numerosi dischi sovrapposti. È conosciuta anche come Torre di Brahma o Torre di Lucas, come la introdusse il matematico francese Edouard Lucas nel 1883. Questo puzzle si basa sulla leggenda dello spostamento dei dischi d'oro tra tre aste.
Questo puzzle ha tre aste e un numero variabile di dischi impilati. Queste aste sono progettate come torri cicliche. Quindi, i dischi di diametro maggiore sono impilati sul fondo e i dischi più piccoli sono impilati sopra.
Inizialmente ci vengono dati tre picchetti o aste. E uno di essi (A, mostrato nell'esempio) ha tutti i dischi impilati. Il nostro obiettivo è spostare un'intera pila di dischi da un'asta (A) a un'altra (C) obbedendo ad alcune regole specifiche.
Ecco la configurazione iniziale del puzzle-
E questo è l'obiettivo finale-
Regole della Torre di Hanoi
Ecco alcune regole essenziali per la Torre di Hanoi:
- Nello stato iniziale di questo puzzle, tutti i dischi saranno impilati nell'asta uno.
- Lo stato finale è che tutti i dischi dell'asta uno verranno impilati sull'asta due o sull'asta tre.
- Possiamo spostare un disco su disco da un'asta all'altra in qualsiasi momento.
- Possiamo spostare solo il disco più in alto dall'asta.
- Un disco non può essere posizionato sopra un altro disco, che è più piccolo.
La leggenda originale riguardava lo spostamento di 64 dischi. I sacerdoti potevano spostare un disco alla volta secondo le regole. Secondo la leggenda, c'era una profezia secondo cui il mondo sarebbe finito se fossero riusciti a completare l'atto. Nella sezione sulla complessità temporale, mostreremo che un'ambientazione della Torre di Hanoi di n dischi costerebbe 2^n – 1 mossa.
Quindi, se i sacerdoti potessero impiegare 1 secondo per spostare i dischi, il tempo totale di cui avrebbero bisogno per risolvere il puzzle sarebbe 2^64 – 1 secondo o 584,942,417,356 anni, 26 giorni, 7 ore e 15 secondi.
Algoritmo per la Torre di Hanoi
Un modo generale per risolvere la Torre di Hanoi è un algoritmo ricorsivo. Innanzitutto, dobbiamo decidere su due aste o picchetti come fonte e destinazione, e il picchetto di riserva sarà un ausiliario o un aiutante.
Ecco i passaggi per risolvere il puzzle della Torre di Hanoi:
- Sposta i primi n-1 dischi dal piolo di origine al piolo di supporto.
- Successivamente, sposta l'ennesimo disco dal picchetto di origine al picchetto di destinazione.
- Infine, sposta i restanti n-1 dischi dal piolo di aiuto al piolo di destinazione.
Note:: Se abbiamo un singolo disco, possiamo spostarlo direttamente dall'origine alla destinazione.
Come risolvere il puzzle della Torre di Hanoi
Illustriamo l'algoritmo per tre dischi e consideriamo il picchetto A come sorgente, il picchetto B come aiutante e il picchetto C come destinazione
Passo 1) Inizialmente, tutti i dischi saranno impilati sul piolo A.
In questa fase:
Fonte = Piolo A
Destinazione = Piolo C
Aiutante = Piolo B
Ora dobbiamo spostare i primi n-1 dischi dall'origine all'helper.
Nota: Anche se possiamo spostare solo un disco alla volta, il nostro problema viene suddiviso da un problema con 3 dischi a un problema con 2 dischi, che è una chiamata ricorsiva.
Passo 2) Poiché chiamiamo una chiamata ricorsiva dal peg A e la destinazione è il peg B, utilizzeremo il peg C come helper.
Notiamo che siamo di nuovo allo stadio uno per lo stesso problema della torre di Hanoi per due dischi.
Ora dobbiamo spostare n-1 o un disco dalla sorgente all'helper, spostando il disco più piccolo dal piolo A al piolo C.
In questa fase:
Fonte = piolo A
Destinazione = picchetto B
Aiutante = piolo C
Passo 3) Quindi, secondo il nostro algoritmo, l'ennesimo o il secondo disco necessario dovrebbero essere trasferiti nella destinazione o nel picchetto B.
In questa fase:
Fonte = piolo A
Destinazione = picchetto B
Aiutante = piolo C
Passo 4) Ora sposteremo i dischi n-1 o il disco uno dall'helper o dal picchetto C alla destinazione o dal picchetto B secondo la terza fase del nostro algoritmo.
In questa fase:
Fonte = piolo A
Destinazione = picchetto B
Aiutante = piolo C
Passo 5) Dopo aver completato la chiamata ricorsiva, torneremo alla nostra impostazione precedente nella prima fase dell'algoritmo.
Passo 6) Ora, nella seconda fase, sposteremo la nostra sorgente verso la nostra destinazione, che consiste nello spostare il disco 3 dal picchetto A al picchetto C.
In questa fase:
Fonte = piolo A
Destinazione = piolo C
Aiutante = piolo B
Passo 7) Ora possiamo vederlo
d consiste nello spostare i dischi rimanenti dall'aiutante (piolo B) alla destinazione (piolo C). In questo caso utilizzeremo la fonte iniziale o il piolo A come aiuto.
Passo 8) Poiché non possiamo spostare due dischi contemporaneamente, chiameremo una chiamata ricorsiva per il disco 1. In base all'ultimo passaggio e al nostro algoritmo, una destinazione in questo passaggio è il picchetto A.
In questa fase:
Fonte = piolo B
Destinazione = picchetto A
Aiutante = piolo C
Passo 9) La nostra chiamata ricorsiva è ora completata. Quindi spostiamo il disco 2 dalla sua origine alla sua destinazione.
In questa fase:
Fonte = piolo B
Destinazione = piolo C
Aiutante = piolo A
Passo 10) Quindi spostiamo il nostro rimanente n-1 o disco 1 dall'helper alla destinazione.
In questa fase:
Fonte = piolo A
Destinazione = piolo C
Aiutante = piolo B
Pseudo codice per la Torre di Hanoi
START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
IF disk == 1, THEN
move disk from source to dest
ELSE
Tower_Of_Hanoi (disk - 1, source, helper, dest)
move disk from source to dest
Tower_Of_Hanoi (disk - 1, helper, dest, source)
END IF
END Procedure
Codice del programma inserito C++
#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
if (num == 1) {
cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
return;
}
tower_of_hanoi(num - 1, source, helper, dest);
cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
int num;
cin >> num;
printf("The sequence of moves :\n");
tower_of_hanoi(num, "I", "III", "II");
return 0;
}
Uscita
3 The sequence of moves : Move disk 1 from tower I to tower III Move disk 2 from tower I to tower II Move disk 1 from tower III to tower II Move disk 3 from tower I to tower III Move disk 1 from tower II to tower I Move disk 2 from tower II to tower III Move disk 1 from tower I to tower III
Codice del programma inserito Python
def tower_of_hanoi(n, source, destination, helper):
if n==1:
print ("Move disk 1 from peg", source," to peg", destination)
return
tower_of_hanoi(n-1, source, helper, destination)
print ("Move disk",n," from peg", source," to peg", destination)
tower_of_hanoi(n-1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')
Produzione:
Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B
Complessità della Torre di Hanoi
Ecco la complessità temporale e spaziale della Torre di Hanoi:
1) Complessità temporale:
Se guardiamo indietro al nostro algoritmo, possiamo vedere che stiamo introducendo due volte una chiamata ricorsiva per (n-1) dischi. Queste chiamate ricorsive per (n-1) dischi possono essere suddivise in altri ((n-1)-1) e così via finché non si ottiene un solo disco da spostare.
Per tre dischi-
- Il disco 3 chiama due volte una funzione ricorsiva per il disco due.
- Il disco 2 chiama due volte una funzione ricorsiva per il disco uno.
- Il disco 1 può muoversi entro un tempo costante e il tempo può risolvere tre dischi.
= 2*(Tempo di soluzione per due dischi) + tempo costante per spostare il disco 3
= 2*(2*tempo per risolvere un disco + tempo costante per spostare il disco 2) + tempo costante per spostare il disco 3
= (2*2) (tempo costante per spostare il disco 1) + 2*tempo costante per spostare il disco 2 + tempo costante per spostare il disco 3
Per n dischi, può essere scritto come –
(2n-1 * tempo costante per spostare il disco 1 + 2n-2 * tempo costante per muovere il disco 2 + ….
Questa progressione geometrica risulterà in O(2n-1) o puoi O(2n), che è esponenziale.
2) Complessità dello spazio
La complessità spaziale della Torre di Hanoi è 0(n). Questo perché dobbiamo memorizzare la sequenza delle piastre. Quando utilizziamo la ricorsione, utilizziamo la pila. E la dimensione massima della pila può essere "n". Ecco perché la complessità spaziale diventa O(n).
