Struttura dei dati e algoritmi - Torre di Hanoi

Torre di Hanoi, è un puzzle matematico che consiste di tre torri (pioli) e più di un anello è come raffigurato -

Questi anelli sono di diverse dimensioni e impilati in ordine crescente, cioè quello più piccolo si trova sopra quello più grande. Ci sono altre varianti del puzzle in cui il numero di dischi aumenta, ma il numero di torri rimane lo stesso.

Regole

La missione è spostare tutti i dischi in un'altra torre senza violare la sequenza di disposizione. Alcune regole da seguire per la Torre di Hanoi sono:

  • Solo un disco può essere spostato tra le torri in un dato momento.
  • È possibile rimuovere solo il disco "superiore".
  • Nessun disco di grandi dimensioni può sedersi su un disco di piccole dimensioni.

Di seguito è riportata una rappresentazione animata della risoluzione di un puzzle della Torre di Hanoi con tre dischi.

Il puzzle della Torre di Hanoi con n dischi può essere risolto al minimo 2n−1passi. Questa presentazione mostra che un puzzle con 3 dischi ha preso23 - 1 = 7 passi.

Algoritmo

Per scrivere un algoritmo per la Torre di Hanoi, prima dobbiamo imparare come risolvere questo problema con una quantità minore di dischi, diciamo → 1 o 2. Contrassegniamo tre torri con il nome, source, destination e aux(solo per aiutare a spostare i dischi). Se disponiamo di un solo disco, può essere facilmente spostato dal piolo di origine a quello di destinazione.

Se abbiamo 2 dischi -

  • Per prima cosa, spostiamo il disco più piccolo (in alto) su aux peg.
  • Quindi, spostiamo il disco più grande (inferiore) nel piolo di destinazione.
  • Infine, spostiamo il disco più piccolo da aux a piolo di destinazione.

Quindi ora siamo in grado di progettare un algoritmo per la Torre di Hanoi con più di due dischi. Dividiamo la pila di dischi in due parti. Il disco più grande (n- esimo disco) è in una parte e tutti gli altri (n-1) dischi sono nella seconda parte.

Il nostro obiettivo finale è spostare il disco ndall'origine alla destinazione e quindi inserire tutti gli altri (n1) dischi su di esso. Possiamo immaginare di applicare lo stesso in modo ricorsivo a tutti i set di dischi dati.

I passaggi da seguire sono:

Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Un algoritmo ricorsivo per la Torre di Hanoi può essere guidato come segue:

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Per verificare l'implementazione nella programmazione C, fare clic qui .