Hanoi kuleleri, Fransız matematikçi, Edouard Lucas tarafından önerilen bir çözüm yöntemidir. A,B ve C gibi dik konumda yerleştirilmiş üç çubuk ve N kadar disk içermektedir. İşleyiş şöyledir:
Başlangıçta diskler, üstteki her diskin çapı daha büyük olmak şartıyla A çubuğuna yerleştirilir. Her seferinde sadece bir diskin hareketine izin verildiğinde, büyük disk, küçük diskin üzerine yerleştirilmeden, disklerin C çubuğuna taşınması gerekmektedir. Hanoi problemi, problem alt problemlere parçalanarak çözülebilir. Problemde N kadar disk olduğunu varsayarsak recursive şekilde bir çözüm şu şekilde olabilir:
Sadece bir disk direkt olarak 3. çubuğa konulur N kadar disk 3. adıma yerleştirilmeli Bu da şöyle uygulanabilir.
(N-1) olan disk orta çubuğa taşınır. En altta kalan disk direkt sağa konulur. (N-1) olan disk sağa taşınır.
Örneğin 4 diskli bir çözüm uyguladığımızı varsayalım. Bunun çıktısı şöyle olur:
Diski A çubuğundan B çubuğuna koy Diski A çubuğundan C çubuğuna koy Diski B çubuğundan C çubuğuna koy Diski A çubuğundan B çubuğuna koy Diski C çubuğundan A çubuğuna koy Diski C çubuğundan B çubuğuna koy Diski A çubuğundan B çubuğuna koy Diski A çubuğundan C çubuğuna koy Diski B çubuğundan C çubuğuna koy Diski B çubuğundan A çubuğuna koy Diski C çubuğundan A çubuğuna koy Diski B çubuğundan C çubuğuna koy Diski A çubuğundan B çubuğuna koy Diski A çubuğundan C çubuğuna koy Diski B çubuğundan C çubuğuna koy
4 adet disk kullanılan bir durumda n = 1 oluyorsa toplam 3 durum ve çözüm için K1 = 1 olur. Yine disk sayısının n = 2 olduğu durumda toplam 9 durum ve çözüm için K2 = 3 olur. n = 3 disk sayısında 27 durum ve çözüm için K3 = 7 olmakta. Disk sayısı n = 4 olduğunda toplam durum sayısı 81 ve çözüm ise K4 = 15 olur.
Çubuk sayısı 3 olduğunda N adet disk için en düşük geçişler, recursive biçinmde Kn = (2 Kn-1 +1) ya da n’ye bağlı şekilde Kn = 2^n – 1 şeklinde bulunmaktadır.
Bu durumun Python ile çözümlenmiş hali ise şöyledir. Algoritmanın ana işlenilen işlevi hanoitoweralgorithm ile tanımlanıp 4 parametre alır. Bu işlev, parametreleri recursive olarak işler.
def hanoi_tower_algorithm(n, x, y, z):
if n == 1:
print("Diski %s çubuğundan %s çubuğuna koy" % (x,z))
else:
hanoi_tower_algorithm(n-1, x, z, y)
hanoi_tower_algorithm(1, x, y, z)
hanoi_tower_algorithm(n-1, y, x, z)
Disk sayısının belirlenmesi içinse ayrıca bir işlev oluşturulur. Tek parametre alır. Bu parametre çözümdeki N disk sayısını belirtir. N adet disk bu işlevde belirtilir. Buradan alınan parametre bir üstteki ana işlevine yollanılır. Ve diskler de A, B ve C şeklinde parametre olarak yollanılır.
def hanoi_tower_algorithm_main(ndisc):
# ndisc = Number of Disc
hanoi_tower_algorithm(ndisc, "A", "B", "C")
10 adet disk için çıkarılan profile sonucu ise şöyledir:
python -m profile hanoi_tower_algorithm.py
6654 function calls (5121 primitive calls) in 0.078 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
2046 0.000 0.000 0.000 0.000 :0(charmap_encode)
1 0.000 0.000 0.078 0.078 :0(exec)
1023 0.062 0.000 0.078 0.000 :0(print)
1 0.000 0.000 0.000 0.000 :0(setprofile)
2046 0.016 0.000 0.016 0.000 cp857.py:18(encode)
1 0.000 0.000 0.078 0.078 hanoi_tower_algorithm.py:1(<module
>)
1534/1 0.000 0.000 0.078 0.078 hanoi_tower_algorithm.py:1(hanoi_t
ower_algorithm)
1 0.000 0.000 0.078 0.078 hanoi_tower_algorithm.py:44(hanoi_
tower_algorithm_main)
1 0.000 0.000 0.078 0.078 profile:0(<code object <module> at
0x01DCC2A0, file "hanoi_tower_algorithm.py", line 1>)
0 0.000 0.000 profile:0(profiler)