Hanoi Kulesi Algoritması: Python, C++ Code
Sarah Chen
⚡ Akıllı Özet
Hanoi Kulesi algoritması, böl ve yönet prensibini açıkça gösteren, üç çubuk arasında bir disk yığınını hareket ettirirken asla daha büyük bir diski daha küçük bir diskin üzerine koymamayı gerektiren klasik bir özyinelemeli bulmacadır.
Hanoi Kulesi nedir?
Hanoi Kulesi, üç çubuk ve azalan büyüklükte üst üste yerleştirilmiş disklerden oluşan matematiksel bir bulmacadır. Fransız matematikçi Edouard Lucas tarafından 1883'te tanıtıldığı için Brahma Kulesi veya Lucas Kulesi olarak da bilinir. Bulmaca, üç çubuk arasında hareket eden altın disklerle ilgili efsanelere dayanmaktadır.
Bu bulmacada üç çubuk ve değişken sayıda üst üste dizilmiş disk bulunmaktadır. Çubuklar döngüsel kuleler şeklinde düzenlenmiştir, bu nedenle daha büyük diskler altta, daha küçük diskler ise üstte üst üste dizilmiştir.
Başlangıçta bize üç çubuk veya çivi veriliyor. Bunlardan birinde (örnekte A çubuğu) tüm diskler üst üste dizilmiş durumda. Amaç, belirli kurallara uyarak tüm yığını bir çubuktan (A) diğerine (C) taşımaktır.
İşte bulmacanın ilk kurulumu:
Hanoi Kulesi Sorunu
Ve bu da nihai hedefimiz:
Hanoi Kulesi Kuralları
İşte Hanoi Kulesi için temel kurallar:
- Bulmacanın başlangıç durumunda, tüm diskler birinci çubuğun üzerine üst üste dizilmiştir.
- Son aşamada, birinci çubuktaki tüm diskler ikinci veya üçüncü çubuğun üzerine istiflenir.
- Herhangi bir anda yalnızca bir disk bir çubuktan diğerine hareket edebilir.
- Bir çubuk üzerindeki yalnızca en üstteki disk hareket ettirilebilir.
- Bir disk, daha küçük bir diskin üzerine yerleştirilemez.
Orijinal efsane 64 diskin hareket ettirilmesiyle ilgiliydi. Rahipler kurallara göre her seferinde bir diski hareket ettirebiliyorlardı. Efsaneye göre, bu işlemi tamamlayabilirlerse dünyanın sonunun geleceğine dair bir kehanet vardı. Zaman karmaşıklığı bölümünde, n diskten oluşan bir Hanoi Kulesi düzenlemesinin 2^n – 1 hareket gerektirdiğini göstereceğiz.
Dolayısıyla, rahiplerin bir diski hareket ettirmek için 1 saniyeye ihtiyaç duyduklarını varsayarsak, bulmacayı çözmek için gereken toplam süre 2^64 – 1 saniye veya yaklaşık 584,942,417,356 yıl, 26 gün, 7 saat ve 15 saniye olacaktır.
Hanoi Kulesi için Algoritma
Hanoi Kulesi problemini çözmenin en yaygın yolu özyinelemeli bir algoritmadır. İlk olarak, kaynak ve hedef olarak iki çubuk seçeriz; yedek çubuk yardımcı veya destekleyici görevi görür.
İşte Hanoi Kulesi bulmacasını çözme adımları:
- Üstteki n-1 diskleri kaynak çivisinden yardımcı çiviye taşıyın.
- n. diski kaynak çubuktan hedef çubuğa taşıyın.
- Yardımcı çubuktan kalan n-1 diski hedef çubuğa taşıyın.
Not: Tek bir diskimiz varsa, onu doğrudan kaynaktan hedefe taşıyabiliriz.
Hanoi Kulesi Bulmacası nasıl çözülür?
Üç disk için algoritmayı açıklayalım. A çubuğunu kaynak, B çubuğunu yardımcı ve C çubuğunu hedef olarak kabul edelim.
) 1 Adım Başlangıçta tüm diskler A çubuğunun üzerine istiflenmiştir.
Bu aşamada: Kaynak = A mandalı, Hedef = C mandalı, Yardımcı = B mandalı.
Şimdi en üstteki n-1 diskleri kaynaktan yardımcıya taşımamız gerekiyor.
Not: Her seferinde yalnızca bir diski taşıyabilsek de, bu adım 3 diskli problemimizi özyinelemeli bir çağrı ile ele alınan 2 diskli bir probleme indirgiyor.
) 2 Adım A düğümünden B düğümünü hedef alarak özyinelemeli bir çağrı yaptığımızda, C düğümünü yardımcı düğüm olarak kullanırız.
Dikkat ederseniz, aynı Hanoi Kulesi problemi için birinci aşamaya geri döndük, ancak bu sefer iki disk için. n-1 (yani bir) diski kaynaktan yardımcıya taşıyoruz, bu da en küçük diski A çubuğundan C çubuğuna taşıyor.
Bu aşamada: Kaynak = A noktası, Hedef = B noktası, Yardımcı = C noktası.
) 3 Adım Algoritmaya göre, n. (2.) disk şimdi hedef nokta olan B pimine aktarılıyor.
Bu aşamada: Kaynak = A noktası, Hedef = B noktası, Yardımcı = C noktası.
) 4 Adım Şimdi, algoritmanın üçüncü aşamasını takip ederek n-1 numaralı diski (birinci disk) yardımcı pim C'den hedef pim B'ye taşıyoruz.
Bu aşamada: Kaynak = A noktası, Hedef = B noktası, Yardımcı = C noktası.
) 5 Adım Özyinelemeli çağrıyı tamamladıktan sonra, algoritmanın ilk aşamasındaki önceki ayarlarımıza geri dönüyoruz.
) 6 Adım İkinci aşamada, 3 numaralı diski kaynak pimi A'dan hedef pimi C'ye taşıyoruz.
Bu aşamada: Kaynak = A noktası, Hedef = C noktası, Yardımcı = B noktası.
) 7 Adım Bir sonraki görev, kalan diskleri yardımcıdan (B çubuğu) hedef noktaya (C çubuğu) taşımaktır. Bu sefer yardımcı olarak orijinal kaynağı (A çubuğu) kullanacağız.
) 8 Adım İki diski aynı anda taşıyamadığımız için, 1. disk için özyinelemeli bir çağrı yapıyoruz. Bizim bilgimize göre algoritmaBu aşamadaki hedef nokta A kazığıdır.
Bu aşamada: Kaynak = B noktası, Hedef = A noktası, Yardımcı = C noktası.
) 9 Adım Özyinelemeli çağrımız tamamlandı. Şimdi 2 numaralı diski kaynağından hedefine taşıyoruz.
Bu aşamada: Kaynak = B noktası, Hedef = C noktası, Yardımcı = A noktası.
) 10 Adım Son olarak, geriye kalan n-1 diski (disk 1) yardımcı diskten hedef diske taşıyoruz.
Bu aşamada: Kaynak = A noktası, Hedef = C noktası, Yardımcı = B noktası.
Sözde Code Hanoi Kulesi için
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
Program kodu 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; }
Çıktı:
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
Program kodu 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')
Çıktı:
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
Hanoi Kulesi'nin Karmaşıklığı
İşte Hanoi Kulesi'nin zaman ve mekan karmaşıklığı:
1) Zaman karmaşıklığı:
Algoritmaya geri dönersek, her çağrıda iki kez (n-1) disk için özyinelemeli bir çağrı yapıyoruz. Her (n-1) özyineleme, ((n-1)-1) özyinelemeye ayrılıyor ve bu şekilde tek diskli temel duruma ulaşana kadar devam ediyor.
Üç disk için:
- Disk 3, Disk 2 için olan özyinelemeli fonksiyonu iki kez çağırır.
- Disk 2, Disk 1 için olan özyinelemeli fonksiyonu iki kez çağırır.
- Disk 1 sabit bir sürede hareket eder ve bu da üç disk için çözüm bulma süresini verir.
Tekrarlama olarak ifade edilir:
= 2 × (İki disk için çözüm süresi) + 3. diski hareket ettirmek için sabit süre
= 2 × (2 × bir disk için çözüm süresi + 2. diski hareket ettirmek için sabit süre) + 3. diski hareket ettirmek için sabit süre
= (2 × 2) × disk 1'i hareket ettirmek için sabit süre + 2 × disk 2'yi hareket ettirmek için sabit süre + disk 3'ü hareket ettirmek için sabit süre
n disk için bu şu hale gelir:
2n-1 × disk 1 + 2'yi hareket ettirmek için gereken sabit süren-2 × sabit disk hareket süresi 2 + ….
Bu geometrik dizinin toplamı O(2)'dir.n – 1), bu da sadeleştirildiğinde şu hale gelir: Ç(2n)Üstel zaman karmaşıklığına sahiptir.
2) Alan karmaşıklığı:
Hanoi Kulesi algoritmasının alan karmaşıklığı O(n)'dir. Özyineleme çağrı yığınını kullanır ve yığının maksimum derinliği disk sayısı olan n'ye eşittir. Bu nedenle alan karmaşıklığı O(n)'dir.
