Algoritmo della Torre di Hanoi: Python, C++ Code

⚡ Riepilogo intelligente

L'algoritmo della Torre di Hanoi è un classico rompicapo ricorsivo che consiste nello spostare una pila di dischi tra tre pioli senza mai posizionare un disco più grande sopra uno più piccolo, illustrando chiaramente il principio del "divide et impera".

🗼 Impostazione del puzzle: Tre pioli e n dischi impilati in ordine decrescente di dimensione sul piolo di origine, in attesa di essere spostati sul piolo di destinazione tramite un piolo ausiliario.
📜 Regole: Solo un disco si muove alla volta, solo il disco superiore di ogni piolo può muoversi e un disco più grande non può appoggiarsi su un disco più piccolo.
🔁 Idea ricorsiva: Sposta n-1 dischi sul perno ausiliario, sposta il disco più grande sul perno di destinazione, quindi sposta gli n-1 dischi rimanenti dal perno ausiliario a quello di destinazione.
️ Complessità temporale: Risolvere il problema di n dischi richiede 2^n – 1 mosse, il che comporta una complessità temporale esponenziale O(2^n) che cresce molto rapidamente all'aumentare di n.
🧠 Complessità spaziale: Lo stack di ricorsione può contenere fino a n frame contemporaneamente, quindi la complessità spaziale della soluzione ricorsiva è O(n).
️ applicazioni: Insegnamento della ricorsione, degli schemi di rotazione di backup, del trasferimento dati basato su stack, del sequenziamento nella robotica e della comprensione della progettazione di algoritmi divide et impera.

Scopri di più

Cos'è la Torre di Hanoi?

La Torre di Hanoi è un rompicapo matematico composto da tre aste e una pila di dischi di dimensioni decrescenti sovrapposti. È nota anche come Torre di Brahma o Torre di Lucas, dal nome del matematico francese Édouard Lucas, che la introdusse nel 1883. Il rompicapo si basa su leggende riguardanti dischi d'oro che si muovevano tra le tre aste.

Questo rompicapo è composto da tre aste e un numero variabile di dischi impilati. Le aste sono disposte a formare delle torri cicliche, in modo che i dischi più grandi siano impilati alla base e quelli più piccoli in cima.

Inizialmente, ci vengono forniti tre pioli o aste. Su una di esse (il piolo A nell'esempio) sono impilati tutti i dischi. L'obiettivo è spostare l'intera pila da un'asta (A) a un'altra (C) rispettando alcune regole specifiche.

Ecco la configurazione iniziale del puzzle:

Problema della Torre di Hanoi

E questo è l'obiettivo finale:

Regole della Torre di Hanoi

Ecco le regole essenziali per la Torre di Hanoi:

Nella configurazione iniziale del puzzle, tutti i dischi sono impilati sull'asta numero uno.
Nella configurazione finale, tutti i dischi provenienti dalla prima asta sono impilati sulla seconda o sulla terza asta.
In un dato momento, un solo disco può spostarsi da un'asta all'altra.
Solo il disco più in alto su un'asta può essere spostato.
Non è possibile posizionare un disco sopra un disco 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, esisteva una profezia secondo cui il mondo sarebbe finito se fossero riusciti a completare l'atto. Nella sezione sulla complessità temporale, mostreremo che una configurazione della Torre di Hanoi con n dischi richiede 2^n – 1 mosse.

Quindi, se i sacerdoti avessero impiegato 1 secondo per spostare un disco, il tempo totale per risolvere il puzzle sarebbe stato di 2^64 – 1 secondo, ovvero circa 584,942,417,356 anni, 26 giorni, 7 ore e 15 secondi.

Algoritmo per la Torre di Hanoi

Il metodo più comune per risolvere la Torre di Hanoi è un algoritmo ricorsivo. Innanzitutto, scegliamo due aste come sorgente e destinazione; il piolo di riserva funge da ausiliario o di supporto.

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.
Sposta l'n-esimo disco dal perno di origine al perno di destinazione.
Spostare i restanti n-1 dischi dal perno di supporto al perno di destinazione.

Nota: Se disponiamo di un singolo disco, possiamo spostarlo direttamente dalla sorgente alla destinazione.

Come risolvere il puzzle della Torre di Hanoi

Illustriamo l'algoritmo per tre dischi. Consideriamo il piolo A come sorgente, il piolo B come supporto e il piolo C come destinazione.

Passo 1) Inizialmente, tutti i dischi sono impilati sul perno A.

In questa fase: Sorgente = Picchetto A, Destinazione = Picchetto C, Ausiliario = Picchetto B.

Ora dobbiamo spostare i primi n-1 dischi dall'origine all'helper.

Nota: Sebbene possiamo spostare un solo disco alla volta, questo passaggio riduce il nostro problema a 3 dischi a un problema a 2 dischi, che viene gestito tramite una chiamata ricorsiva.

Passo 2) Poiché effettuiamo una chiamata ricorsiva dal peg A con il peg B come destinazione, utilizziamo il peg C come supporto.

Si noti che siamo tornati alla prima fase dello stesso problema della Torre di Hanoi, ma ora con due dischi. Spostiamo n-1 (ovvero un) disco dalla sorgente all'aiutante, che sposta il disco più piccolo dal piolo A al piolo C.

In questa fase: Sorgente = piolo A, Destinazione = piolo B, Ausiliario = piolo C.

Passo 3) Secondo l'algoritmo, l'n-esimo (2°) disco viene ora trasferito alla destinazione, piolo B.

In questa fase: Sorgente = piolo A, Destinazione = piolo B, Ausiliario = piolo C.

Passo 4) Ora, spostiamo il disco n-1 (disco uno) dal perno ausiliario C al perno di destinazione B, seguendo la terza fase dell'algoritmo.

In questa fase: Sorgente = piolo A, Destinazione = piolo B, Ausiliario = piolo C.

Passo 5) Dopo aver completato la chiamata ricorsiva, torniamo all'impostazione precedente, ovvero alla prima fase dell'algoritmo.

Passo 6) Nella seconda fase, spostiamo il disco 3 dal perno di origine A al perno di destinazione C.

In questa fase: Sorgente = piolo A, Destinazione = piolo C, Ausiliario = piolo B.

Passo 7) Il prossimo compito è spostare i dischi rimanenti dal supporto (perno B) alla destinazione (perno C). Questa volta useremo la sorgente originale (perno A) come supporto.

Passo 8) Poiché non possiamo spostare due dischi contemporaneamente, effettuiamo una chiamata ricorsiva per il disco 1. Secondo il nostro algoritmo, la destinazione in questa fase è il piolo A.

In questa fase: Sorgente = piolo B, Destinazione = piolo A, Ausiliario = piolo C.

Passo 9) La nostra chiamata ricorsiva è completa. Ora spostiamo il disco 2 dalla sua origine alla sua destinazione.

In questa fase: Sorgente = piolo B, Destinazione = piolo C, Ausiliario = piolo A.

Passo 10) Concludiamo spostando il restante n-1 disco (disco 1) dal dispositivo di supporto a quello di destinazione.

In questa fase: Sorgente = piolo A, Destinazione = piolo C, Ausiliario = piolo B.

Soprannome Code 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;
}

Produzione:

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à spazio-temporale della Torre di Hanoi:

1) Complessità temporale:

Riesaminando l'algoritmo, effettuiamo una chiamata ricorsiva per (n-1) dischi due volte per ogni chiamata. Ogni (n-1) ricorsione si scompone in ((n-1)-1) ricorsioni, e così via, fino a raggiungere il caso base a disco singolo.

Per tre dischi:

Il disco 3 richiama due volte la funzione ricorsiva del disco 2.
Il disco 2 richiama due volte la funzione ricorsiva del disco 1.
Il disco 1 si muove in tempo costante, dando il tempo necessario per risolvere il problema dei tre dischi.

Espresso come ricorrenza:

= 2 × (Tempo necessario per risolvere per due dischi) + tempo costante per spostare il disco 3

= 2 × (2 × tempo per risolvere per 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, questo diventa:

2^n-1 × tempo costante per spostare il disco 1 + 2^n-2 × tempo costante per spostare il disco 2 + ….

Questa progressione geometrica si somma a O(2ⁿ – 1), che si semplifica in O(2ⁿ), una complessità temporale esponenziale.

2) Complessità spaziale:

La complessità spaziale della Torre di Hanoi è O(n). La ricorsione utilizza lo stack delle chiamate e la profondità massima dello stack è pari a n, il numero di dischi. Ecco perché la complessità spaziale è O(n).

DOMANDE FREQUENTI

L'algoritmo della Torre di Hanoi è una procedura ricorsiva che sposta n dischi da un piolo di partenza a un piolo di destinazione utilizzando un piolo ausiliario, senza mai posizionare un disco più grande sopra uno più piccolo.

Il numero minimo di mosse per n dischi è 2^n – 1. Tre dischi richiedono 7 mosse, quattro dischi ne richiedono 15 e dieci dischi ne richiedono 1,023.

La complessità temporale è O(2^n) perché ogni disco aggiuntivo raddoppia il lavoro. La relazione di ricorrenza T(n) = 2T(n-1) + 1 si risolve in 2^n – 1, che è esponenziale.

La complessità spaziale è O(n) perché lo stack delle chiamate ricorsive contiene un frame per ogni disco in elaborazione. La profondità massima di ricorsione raggiunge n, quindi la memoria ausiliaria necessaria è lineare rispetto al numero di dischi.

Sì. Una soluzione iterativa utilizza un ciclo con uno schema fisso: nelle mosse dispari si scambia ciclicamente il disco più piccolo tra i pioli, mentre nelle mosse pari si effettua l'unica mossa valida che non sia la più piccola.

L'algoritmo insegna la ricorsione, modella schemi di rotazione di backup per l'archiviazione, guida la sequenza di funzionamento dei bracci robotici e compare nei test neuropsicologici che misurano la capacità di pianificazione.

Gli agenti di apprendimento per rinforzo risolvono la Torre di Hanoi trattando ogni configurazione dei dischi come uno stato e ogni mossa come un'azione. Si tratta di un benchmark comune per la pianificazione e l'apprendimento di politiche gerarchiche.

Sì. GitHub Copilot, ChatGPT e Gemini generare soluzioni ricorsive della Torre di Hanoi in Python, C++e JavaGli sviluppatori dovrebbero comunque verificare i casi base e l'ordine degli argomenti.

Algoritmo della Torre di Hanoi: Python, C++ Code

Cos'è la Torre di Hanoi?

Regole della Torre di Hanoi

Algoritmo per la Torre di Hanoi

Come risolvere il puzzle della Torre di Hanoi

Soprannome Code per la Torre di Hanoi

Codice del programma inserito C++

Codice del programma inserito Python

Complessità della Torre di Hanoi

DOMANDE FREQUENTI

Riassumi questo post con:

Iscriviti alla newsletter

Cos'è la Torre di Hanoi?

Regole della Torre di Hanoi

Algoritmo per la Torre di Hanoi

Come risolvere il puzzle della Torre di Hanoi

ARTICOLI CORRELATI

Soprannome Code per la Torre di Hanoi

Codice del programma inserito C++

Codice del programma inserito Python

Complessità della Torre di Hanoi

DOMANDE FREQUENTI

Riassumi questo post con:

Iscriviti alla newsletter