Stack (Yığıt) kullanarak Hanoi Kuleleri oyununu gerçekleyeceğiz. Oyunu ve kurallarını öğrenelim öncelikle.
Hanoi kuleleri, bir matematik oyunu veya bulmacadır. Üç direk ve farklı boyutlarda disklerden oluşur. Bu diskleri dilediğiniz direğe aktarabilirsiniz. Bulmaca bir direkte en küçük disk yukarıda olacak şekilde, küçükten büyüğe direk üstünde dizilmiş olarak başlar. Böylece konik bir şekil oluşmuş olur.
Oyunun kuralları
- Her hamlede sadece bir disk taşınabilir.
- Her hamle en üstteki diski direkten alıp diğer bir direğe taşımaktan oluşur. Diğer direkte daha önceden diskler olabilir.
- Hiçbir disk kendisinden küçük bir diskin üzerine koyulamaz.
En kısa ve en hızlı çözümündeki hamle sayısı da 2n-1 ile hesaplanır (n disk sayısı).
4 Diskli bir hanoi oyununun temsili animasyonu şu şekildedir:
Recrusive fonksiyon olarak düşünürsek oyunun ilerleme mantığı şu şekilde olacaktır:
Disk sayısına göre her diske numara verecek olursak ve n diskli oyun için; n-1 olan disk orta kuleye, altındaki disk en uç kuleye, n-1 olan disk sağa taşınır. Artık programımızı gerçekleyebiliriz.
Öncelikle Stack.py ile yığıtımızı gerçekledik.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Stack: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[len(self.items)-1] def size(self): return len(self.items) def show(self): return self.items |
Hanoi classımızda bizim için en önemlisi movement recrusive fonksiyonumuzdur. Algoritmasını belirlediğimiz hareket işlemleri orada işlenmiştir.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
from Stack import * class Hanoi: def __init__(self,n): self.move = n self.tower = [0] [self.tower.append(Stack()) for a in range(1,4)] # 3 Stack kule olustur self.tofh() def tofh(self): #Kuleye diskleri yerlestir for i in range(self.move,0,-1): self.tower[1].push(i) print 'K: Kaynak Kule, Y: Yardimci Kule, H: Hedef Kule' self.display() self.movement(self.move,1,2,3) def movement(self,n,a,b,c): if n > 0: self.movement(n-1,a,c,b) d = self.tower[a].pop() self.tower[c].push(d) self.display() self.movement(n-1,b,a,c) def display(self): print ' K | Y | H ' print '--------------' for i in range(self.move-1,-1,-1): try: source = self.tower[1].show()[i] except IndexError: source = " " try: helper = self.tower[2].show()[i] except IndexError: helper = " " try: target = self.tower[3].show()[i] except IndexError: target = " " print source,' | ', helper,' | ',target print '\n' tofhanoi = int(raw_input('Disk Sayisi Giriniz: ')) test = Hanoi(tofhanoi) |
2 diskli oyunun ekran görüntüsü şu şekildedir:
Bir cevap yazın