Veri Yapısı ve Algoritmalar - Hanoi Kulesi

Hanoi Kulesi, gösterildiği gibi üç kuleden (mandal) ve birden fazla halkadan oluşan matematiksel bir bilmecedir -

Bu halkalar farklı boyutlardadır ve artan sırada istiflenir, yani küçük olan büyük olanın üzerine oturur. Bulmacanın disk sayısının arttığı ancak kule sayısının aynı kaldığı başka varyasyonları da var.

Kurallar

Görev, düzenleme sırasını bozmadan tüm diskleri başka bir kuleye taşımaktır. Tower of Hanoi için uyulması gereken birkaç kural:

Kuleler arasında herhangi bir zamanda yalnızca bir disk hareket ettirilebilir.
Yalnızca "en üst" disk kaldırılabilir.
Hiçbir büyük disk, küçük bir diskin üzerine oturamaz.

Aşağıda, Hanoi Kulesi bulmacasını üç diskle çözmenin animasyonlu bir temsili bulunmaktadır.

Tower of Hanoi bulmacası n diskli minimumda çözülebilir 2ⁿ−1adımlar. Bu sunum, 3 diskli bir bulmacanın2³ - 1 = 7 adımlar.

Algoritma

Tower of Hanoi için bir algoritma yazmak için, önce bu problemi daha az sayıda diskle nasıl çözeceğimizi öğrenmemiz gerekir, örneğin → 1 veya 2. Üç kuleyi ismiyle işaretleriz, source, destination ve aux(yalnızca disklerin taşınmasına yardımcı olmak için). Tek bir diskimiz varsa, kaynaktan hedef peg'e kolayca taşınabilir.

2 diskimiz varsa -

İlk olarak, daha küçük (üst) diski aux peg'e hareket ettiriyoruz.
Ardından, daha büyük (alt) diski hedef peg'e taşırız.
Ve son olarak, küçük diski aux'dan hedef peg'e taşıyoruz.

Şimdi, Tower of Hanoi için ikiden fazla diske sahip bir algoritma tasarlayacak konumdayız. Disk yığınını iki bölüme ayırıyoruz. En büyük disk ( ^n'inci disk) bir kısımdadır ve diğer tüm (n-1) diskler ikinci kısımdadır.

Nihai amacımız diski taşımaktır nkaynaktan hedefe ve sonra diğer tüm (n1) diskleri üzerine yerleştirin. Verilen tüm diskler için aynısını yinelemeli bir şekilde uygulamayı hayal edebiliriz.

İzlenecek adımlar -

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

Tower of Hanoi için yinelemeli bir algoritma aşağıdaki gibi çalıştırılabilir -

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

C programlamada uygulamayı kontrol etmek için buraya tıklayın .