Hanoi Kulesi Algoritması: Python, C++ Kod
Sarah Chen
Hanoi Kulesi nedir?
Hanoi Kulesi, üst üste yerleştirilmiş üç çubuk ve çok sayıda diskten oluşan bir matematik bulmacasıdır. Fransız matematikçi Edouard Lucas'ın 1883'te tanıttığı gibi, Brahma Kulesi veya Lucas kulesi olarak da bilinir. Bu bulmaca, altın disklerin üç çubuk arasında hareket ettirilmesiyle ilgili efsanelere dayanmaktadır.
Bu yapbozun üç çubuğu ve değişken sayıda istiflenmiş diskleri vardır. Bu çubuklar döngüsel kuleler olarak tasarlanmıştır. Böylece çapı büyük olan diskler altta, küçük olanlar ise üstte istiflenir.
Başlangıçta bize üç mandal veya çubuk veriliyor. Ve bunlardan birinde (örnekte gösterilen A) tüm diskler istiflenmiştir. Belirli kurallara uyarak tüm disk yığınını bir çubuktan (A) diğerine (C) taşımayı hedefliyoruz.
İşte bulmacanın ilk kurulumu-
Ve bu son hedef-
Hanoi Kulesi Kuralları
İşte Hanoi Kulesi için bazı temel kurallar:
- Bu bulmacanın başlangıç durumu, tüm disklerin birinci çubukta istiflenmesidir.
- Son durum, birinci çubuktaki tüm disklerin ikinci veya üçüncü çubuk üzerine istiflenmesidir.
- Herhangi bir zamanda diskteki bir çubuğu bir çubuktan diğerine taşıyabiliriz.
- Çubuktan yalnızca en üstteki diski hareket ettirebiliriz.
- Bir disk daha küçük olan başka bir diskin üzerine yerleştirilemez.
Orijinal efsane 64 diski hareket ettirmekle ilgiliydi. Rahipler kurallara göre bir seferde bir diski hareket ettirebiliyorlardı. Efsaneye göre, eğer eylemi 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 ayarının 2^n – 1 hamleye mal olacağını göstereceğiz.
Yani, eğer rahipler diskleri hareket ettirmek için 1 saniyeye ihtiyaç duyabilseydiler, bulmacayı çözmek için ihtiyaç duyacakları toplam Süre 2^64 – 1 saniye veya 584,942,417,356 yıl, 26 gün, 7 saat ve 15 saniye olurdu.
Hanoi Kulesi için Algoritma
Hanoi Kulesi'ni çözmenin genel bir yolu yinelemeli bir algoritmadır. Öncelikle kaynak ve hedef olarak iki çubuk veya çiviye karar vermemiz gerekiyor ve yedek çivi bir yardımcı veya yardımcı olacaktır.
İşte Hanoi Kulesi bulmacasını çözme adımları:
- Üstteki n-1 diskleri kaynak çivisinden yardımcı çiviye taşıyın.
- Daha sonra, n'inci diski kaynak çivisinden hedef çiviye taşıyın.
- Son olarak geri kalan n-1 diski yardımcı çividen hedef çiviye 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ı örnekleyelim ve A çivisini kaynak, B çivisini yardımcı ve C çivisini hedef olarak ele alalım.
) 1 Adım Başlangıçta tüm diskler A çivisine istiflenecektir.
Bu aşamada:
Kaynak = Peg A
Hedef = Peg C
Yardımcı = Mandal B
Şimdi en üstteki n-1 diskleri kaynaktan yardımcıya taşımamız gerekiyor.
Not: Bir seferde yalnızca bir diski hareket ettirebilsek de bu, sorunumuzu 3 diskli bir sorundan 2 diskli bir soruna dönüştürür ki bu yinelemeli bir çağrıdır.
) 2 Adım A ayağından özyinelemeli bir çağrı çağırdığımız ve hedef B ayağı olduğu için, C çivisini yardımcı olarak kullanacağız.
İki disk için aynı Hanoi kulesi probleminde yine birinci aşamada olduğumuza dikkat edin.
Şimdi n-1 veya bir diski kaynaktan yardımcıya, en küçük diski A çivisinden C çivisine taşıyarak taşımamız gerekiyor.
Bu aşamada:
Kaynak = A çivisi
Hedef = B pimi
Yardımcı = C çivisi
) 3 Adım Daha sonra algoritmamıza göre n'inci veya 2'nci disk ihtiyacının hedef veya B sabitleyicisine aktarılması gerekir.
Bu aşamada:
Kaynak = A çivisi
Hedef = B pimi
Yardımcı = C çivisi
) 4 Adım Şimdi, algoritmamızın üçüncü aşamasına göre n-1 diski veya disk XNUMX'i yardımcıdan veya sabit C'den hedef veya sabit B'ye taşıyacağız.
Bu aşamada:
Kaynak = A çivisi
Hedef = B pimi
Yardımcı = C çivisi
) 5 Adım Recursive çağrıyı tamamladıktan sonra algoritmanın ilk aşamasına geldiğimizde önceki ayarımıza döneceğiz.
) 6 Adım Şimdi, ikinci aşamada, kaynağımızı, disk 3'ü A çivisinden C çivisine hareket ettiren hedefimize taşıyacağız.
Bu aşamada:
Kaynak = A çivisi
Hedef = C çivisi
Yardımcı = B mandalı
) 7 Adım Artık bunu görebiliyoruz
d, kalan diskleri yardımcıdan (sabit B) hedefe (sabit C) taşımaktır. Bu durumda yardımcı olarak ilk kaynağı veya A çivisini kullanacağız.
) 8 Adım İki diski aynı anda hareket ettiremeyeceğimiz için, disk 1 için yinelemeli bir çağrı yapacağız. Son adıma ve bizimkine göre algoritma, bu adımdaki hedef A çivisidir.
Bu aşamada:
Kaynak = sabit B
Hedef = A çivisi
Yardımcı = C çivisi
) 9 Adım Özyinelemeli çağrımız artık tamamlandı. Daha sonra disk 2'yi kaynağından hedefine taşıyoruz.
Bu aşamada:
Kaynak = sabit B
Hedef = C çivisi
Yardımcı = A çivisi
) 10 Adım Daha sonra kalan n-1 veya disk 1'i yardımcıdan hedefe taşıyoruz.
Bu aşamada:
Kaynak = A çivisi
Hedef = C çivisi
Yardımcı = B mandalı
Hanoi Kulesi'nin Sahte Kodu
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ığı:
Algoritmamıza dönüp baktığımızda, (n-1) disk için iki kez özyinelemeli çağrı başlattığımızı görebiliriz. (n-1) diskler için yapılan bu özyinelemeli çağrılar, diğer ((n-1)-1) disklere bölünebilir ve bu, yalnızca tek bir diski hareket ettirene kadar devam eder.
Üç disk için-
- Disk 3, disk iki için özyinelemeli bir işlevi iki kez çağırır.
- Disk 2, disk XNUMX için özyinelemeli bir işlevi iki kez çağırır.
- Disk 1, üç diski çözmek için sabit Zaman ve Zaman dahilinde hareket edebilir.
= 2*(İki disk için çözüm süresi) + sabit 3. diski taşıma süresi
= 2*(2*bir disk için çözüm süresi + sabit 2. diski taşıma süresi) + sabit 3. diski taşıma süresi
= (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 şu şekilde yazılabilir:
(2n-1 * disk 1 + 2'yi hareket ettirmek için sabit süren-2 * diski hareket ettirmek için sabit süre 2 +….
Bu geometrik ilerleme O(2) ile sonuçlanacaktır.n-1) Veya Ç(2n), ki bu üsteldir.
2) Uzay karmaşıklığı
Hanoi Kulesi'nin uzay karmaşıklığı 0(n)'dir. Bunun nedeni, plakaların dizisini saklamamız gerektiğidir. Özyinelemeyi kullandığımızda, yığını kullanırız. Ve yığının maksimum boyutu "n" olabilir. Bu nedenle uzay karmaşıklığı O(n) olur.
