Tower of Hanoi

Kategori: Popular Algorithms , 17 Kasım 2019 , JanFranco


Problem:

Elimizde 3 çubuk mevcut. Bu çubuklara A, B ve C çubukları diyelim. A çubuğunda n kadar disk mevcut. Her aşamada bir disk hareket edecek şekilde, tüm diskleri C çubuğuna dizmek istiyoruz. Kuralımız ise şu, bir disk kendisinden daha küçük bir diskin üzerine gelemez. Yani diskler her adımda sıralı olmalıdır.

Yaklaşım:

Bu problemi recursive bir şekilde, problemin boyutunu bir azaltarak çözebiliriz. İlk adımda n kadar diskimiz mevcut. n-1 kadar diski alalım ve B çubuğuna yerleştirelim. A çubuğunda kalan büyük diski direk C çubuğuna yerleştirelim. Daha sonra B çubuğunda bulunan diskleri de C çubuğuna yerleştirelim. Tabi ki her adımda yalnızca bir disk hareket ettirebildiğimizen, n-1 kadar diski hareket ettirmek de kendi kendine bir problemdir.

Çözüm:


def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
    if n:
        tower_of_hanoi(n-1, from_rod, aux_rod, to_rod)
        print(from_rod, "->", to_rod)
        tower_of_hanoi(n-1, aux_rod, to_rod, from_rod)


tower_of_hanoi(3, 'A', 'C', 'B')


Sonuç:

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C


n = 3 için yukarıdaki adımlar izlenir.


Sonraki Yazı: Johnson and Trotter
Yorumlar

Henüz bir yorum bulunmuyor.