Hanoi Kulesi Promlemi (Tower Of Hanoi)

**Prof. Dr. Sinsi** · 11-04-2012

Hanoi Kulesi Promlemi (Tower of Hanoi)

Tower of Hanoi

Bu problem, 1883'te Fransız matematikçi Edouard Lucas tarafından bulundu ve oyuncak olarak satılmaya başlandı

Şekilde 8 diskten yapılmış bir kule ve iki boş çubuk görülmektedir

Her keresinde bir diski hareket ettirmek ve bir diski asla kendisinden küçük bir disk üzerine koymamak şartıyla kuledeki diskleri boş iki çubuğa en az kaç hamlede aktarabilirsiniz? Problemi önce 2, 3 ve 4 gibi az sayıda diskle çözmeye çalışıp bir formül geliştirebilir misiniz?

Çözüm

Kulede n sayıda disk varsa, en az 2n-1 hamle gereklidir

Böylece 3 disk 7, 4 disk 15, 5 disk ise 31

hamlede nakledilebilir

8 disk için 255 hamle gereklidir; 28-1=256-1=255

Hindistan'daki Benares kentinde bir tapınakta bulunan "Brahma Kulesi", "Hanoi Kulesi"nin benzeridir

Brahma Kulesi'nde 64 altın disk vardır ve rahipler, nesillerdir bu diskleri boş iki çubuğa aktarmakla meşguldürler

(Bu 64 altın disk için) gerekli hamle sayısı, 264-1'dir

Bu ise 2 x 1018e yakın 20 basamaklı bir sayıdır

(Yaklaşık 1

84467441 × 1019) Rahipler, gece gündüz çalışıp her saniyede bir disk aktarsalar bile; işi bitirmek bile milyarlarca yıl alacaktır

Söz konusu sayı, asal değildir; fakat, n = 89 veya 107 veya 127 olarak alınırsa asal sayılar elde edilebilir

Bunlara "Mersenne sayıları" denmektedir

Lucas, ilk Mersenne sayısı olan 2127-1'i bulmuştu

(170,141,183,460,469,231,731,687,303,715,884,105,7 27) Ondan sonra 12 Mersenne sayısı daha bulundu

Bunların en büyüğü, 1971'de IBM Araştırma merkezi bilgisayarlarınca bulunan Mersenne sayısıdır: 219937-1

(2^19937-1) Bu, 6002 basamaklı bir sayıdır

Üç diskli Hanoi Kulesi'nde disklere A, B ve C dersek, disklerin hareket sırası, ABA CABA, dört diskli (A,B,C,D) Hanoi Kulesi'nde disklerin hareket sırası, ABA CABA DABA CABA (15)'tir

Soldaki küpte küpün koordinatlarını A, B ve C diye aldığımızda, ABA CABA yolu, sağdaki 4 boyutlu küpte (4 boyutlu hiperküp) koordinatları A, B, C ve D olarak ele alındığında ABA CABA DABA CABA yolları, noktalı çizgilerle gösterilmiştir

Bunlara "Hamilton yolları" denmektedir

Ünlü İrlandalı matematikçi Hamilton, 1850'de "İcosa Oyunu" adı altında bir oniki yüzlünün (dodecahedron) bütün köşelerini dolaşıp başlanan noktaya dönmeyi bulmuştu

Bu oyun, bütün Avrupa'ya yayıldı

Hamilton, bu keşfinden yalnızca 25 sterlin kazanmıştı

Oyunu satanlar ise milyonlar kazandı

Görüldüğü gibi küplerde de bütün köşeler dolaşılarak başlangıç noktasına dönülmektedir

Hanoi Kulesi'nde hareket sırasını harflerle bulmak için iki yöntem daha veriyoruz;

SıralamaDCBASonuç 10001A20010B30011A40100C50101A60110B70111A81000D
Alternatif Yöntem 1

1'den 8'e kadar ikili (binary) sayı sistemini yazın ve sağdan sola A, B, C ve D sütunlarını belirleyin

Her yatay sıranın sağına, o sırada en sağda olan 1'in sütun değerini verin; yine ABA, CABA, D elde ettiniz

Alternatif Yöntem 2

Bir cetveldeki bir birimi sırasıyla 2, 4, 8 ve 16'ya bölün

İkiye bölerken D, 4'e bölerken C, 8'e bölerken B ve 16'ya bölerken A harflerini kullanın

Yine ABA CABA DABA CABA sırası elde ettiniz

(Çin Halkaları denen eski mekanik bilmecelerin çözümünde, bu harfli bilmeceler kullanılmaktadır

) [1]

11-04-2012	#1
Prof. Dr. Sinsi	Hanoi Kulesi Promlemi (Tower Of Hanoi) Hanoi Kulesi Promlemi (Tower of Hanoi) Tower of Hanoi Bu problem, 1883'te Fransız matematikçi Edouard Lucas tarafından bulundu ve oyuncak olarak satılmaya başlandı Şekilde 8 diskten yapılmış bir kule ve iki boş çubuk görülmektedir Her keresinde bir diski hareket ettirmek ve bir diski asla kendisinden küçük bir disk üzerine koymamak şartıyla kuledeki diskleri boş iki çubuğa en az kaç hamlede aktarabilirsiniz? Problemi önce 2, 3 ve 4 gibi az sayıda diskle çözmeye çalışıp bir formül geliştirebilir misiniz? Çözüm Kulede n sayıda disk varsa, en az 2n-1 hamle gereklidir Böylece 3 disk 7, 4 disk 15, 5 disk ise 31 hamlede nakledilebilir 8 disk için 255 hamle gereklidir; 28-1=256-1=255 Hindistan'daki Benares kentinde bir tapınakta bulunan "Brahma Kulesi", "Hanoi Kulesi"nin benzeridir Brahma Kulesi'nde 64 altın disk vardır ve rahipler, nesillerdir bu diskleri boş iki çubuğa aktarmakla meşguldürler (Bu 64 altın disk için) gerekli hamle sayısı, 264-1'dir Bu ise 2 x 1018e yakın 20 basamaklı bir sayıdır (Yaklaşık 184467441 × 1019) Rahipler, gece gündüz çalışıp her saniyede bir disk aktarsalar bile; işi bitirmek bile milyarlarca yıl alacaktır Söz konusu sayı, asal değildir; fakat, n = 89 veya 107 veya 127 olarak alınırsa asal sayılar elde edilebilir Bunlara "Mersenne sayıları" denmektedir Lucas, ilk Mersenne sayısı olan 2127-1'i bulmuştu (170,141,183,460,469,231,731,687,303,715,884,105,7 27) Ondan sonra 12 Mersenne sayısı daha bulundu Bunların en büyüğü, 1971'de IBM Araştırma merkezi bilgisayarlarınca bulunan Mersenne sayısıdır: 219937-1 (2^19937-1) Bu, 6002 basamaklı bir sayıdır Üç diskli Hanoi Kulesi'nde disklere A, B ve C dersek, disklerin hareket sırası, ABA CABA, dört diskli (A,B,C,D) Hanoi Kulesi'nde disklerin hareket sırası, ABA CABA DABA CABA (15)'tir Soldaki küpte küpün koordinatlarını A, B ve C diye aldığımızda, ABA CABA yolu, sağdaki 4 boyutlu küpte (4 boyutlu hiperküp) koordinatları A, B, C ve D olarak ele alındığında ABA CABA DABA CABA yolları, noktalı çizgilerle gösterilmiştir Bunlara "Hamilton yolları" denmektedir Ünlü İrlandalı matematikçi Hamilton, 1850'de "İcosa Oyunu" adı altında bir oniki yüzlünün (dodecahedron) bütün köşelerini dolaşıp başlanan noktaya dönmeyi bulmuştu Bu oyun, bütün Avrupa'ya yayıldı Hamilton, bu keşfinden yalnızca 25 sterlin kazanmıştı Oyunu satanlar ise milyonlar kazandı Görüldüğü gibi küplerde de bütün köşeler dolaşılarak başlangıç noktasına dönülmektedir Hanoi Kulesi'nde hareket sırasını harflerle bulmak için iki yöntem daha veriyoruz; SıralamaDCBASonuç 10001A20010B30011A40100C50101A60110B70111A81000D Alternatif Yöntem 1 1'den 8'e kadar ikili (binary) sayı sistemini yazın ve sağdan sola A, B, C ve D sütunlarını belirleyin Her yatay sıranın sağına, o sırada en sağda olan 1'in sütun değerini verin; yine ABA, CABA, D elde ettiniz Alternatif Yöntem 2 Bir cetveldeki bir birimi sırasıyla 2, 4, 8 ve 16'ya bölün İkiye bölerken D, 4'e bölerken C, 8'e bölerken B ve 16'ya bölerken A harflerini kullanın Yine ABA CABA DABA CABA sırası elde ettiniz (Çin Halkaları denen eski mekanik bilmecelerin çözümünde, bu harfli bilmeceler kullanılmaktadır) [1]