Paylaşım Yap
Tüm Reklamları Kapat
Tüm Reklamları Kapat

Hanoi Kuleleri ve Çözümü

Hanoi Kuleleri ve Çözümü
4 dakika
12,436
  • Özgün
Tüm Reklamları Kapat
Hanoi kuleleri, 1883 yılında E. Lucas tarafından icat edilmiş bir bulmacadır. Bu bulmacadaki amaç, sol tarafta üst üste duran diskleri, her seferinde bir disk hareket ettirmek kaydıyla, sağ tarafa taşımaktır. Bu sırada hiçbir disk, kendinden küçük olanın üstüne konulamaz. Amaç, mümkün olan en az hamle sayısıyla oyunu tamamlamaktır. Disk sayısı arttıkça, minimum hamle sayısı da değişmektedir.
Hanoi kulelerinin çözümü için en basitten ilerleyelim ve yalnızca bir disk olduğunu düşünelim. Bu durumda yalnızca bir hamlede bu diski sağ tarafa alarak problemi çözebiliyoruz. Peki iki disk olduğu durumda ne oluyor? Amacım, sağ tarafa bu iki diski almak. Eğer küçük olanı sağ tarafa koyarsam, bu durumda büyük olanı ortaya koymak durumunda kalırım, bu da işleri uzatır. Oysa ki ben, en büyük olan diski sağ tarafa koymayı hedefliyorum. Bu durumda küçük diski ortaya koyar, ardından büyük olanı sağa koyar, ardından da ortaya koyduğum küçük diski, sağda bekleyen büyük diskin üstüne koyarım. Böylelikle üç hamlede problem çözülmüş olur. Bir disk için bir hamle, iki disk için üç hamle yeterli oldu.
Hanoi kulelerinde üç disk için, yukarıdaki görselde çözüm gösteriliyor. Fakat bundan önce dikkatinizi çekmek istediğim nokta, çözdüğümüz iki soruda, yaptığımız hamlelerin nasıl olduğu? Bir diskte, ilk hamlemiz sağ sütuna oldu. İki diskte ise ilk hamlemiz orta sütuna oldu. Üç diskte ise ilk hamlemiz sağ sütuna olacak. Dikkat edin, problem aslında kendi içerisinde alt problemlere ayrılmış durumda. Güzel bir dinamik programlama örneği.
İki diskte, iki diski de sağ tarafa almak istiyorum. Öyleyse önce bir disk için problemi çözmeliyim. Bir disk için problemi çözdüğümde, geriye fazladan olan ikinci disk kalacak. Bunu da hedef konum olan, sağ sütuna koyabilirim. Öyleyse bir disk için problemi, ortada çözmeliyim.
Aynı mantığı üç disk için düşünelim. Üç diski sağ tarafa taşımak istiyorum. Öyleyse iki diski ortada toplamalıyım ki, fazladan olan en büyük disk sağ tarafa gelebilsin. İki diski ortada toplayabilmek için ise, bir üstteki adımın geçerli olduğunu göreceksiniz. Küçük olanı en sağa almalıyım ki, ikinci disk ortaya gelebilsin. Bu yüzden, üç diskli problemde, ilk hamle en sağa koyarak başlıyor.
Üç diskli problemin çözümünde, ilk hamlenin, bir diskli problemin çözümü, üçüncü hamlenin de iki diskli problemin çözümü olduğuna dikkat edin. Üç disk problemi, yedi basamakta çözüldüğüne göre, dört disk problemini çözerken, yedinci basamakta üç disk problemini çözmüş olmalıyız.

Hanoi Kuleleri

Dört Diskli Problemin Çözümü

Hanoi kulelerinde dört diskli problemin çözümü de ele aldıktan sonra, konunun rahatça kavranacağını düşünüyorum. Daha önce bahsettiğimiz gibi, ilk önce yapmamız gereken hamleyi bulmalıyız. Bir diskte sağda, iki diskte ortada, üç diskte sağda başlamıştık. Öyleyse dört diskte ortada başlamalıyız. Çünkü en küçüğü ortaya alırsak, bir büyüğünü en sağa alıp, küçüğü de onun üstüne alarak, üç hamlede Hanoi kulelerinin iki disk problemini çözmüş oluruz. Bundan sonra işlem üç disk problemini çözmek olur.
Orta kısım boş olduğuna göre, üçüncü disk buraya gelir. En sağdaki küçük disk sola geçer, ortanca ortaya gelir ve küçük tekrar ortaya gelir. Böylelikle üç disk problemi çözülmüş olur ve işte işin açıklaması. Üç disk problemini çözdük ve üç disk de ortada. Böylelikle dördüncü ve en büyük olanı sağa koyabilirim. İşte tam bu sebepten ilk hamleyi ortaya yaptık.
Bu noktadan sonrası, sanki en sağda büyük bir disk yokmuş gibi düşünülerek çözülebilir. Amaç, ortadaki üç diski sağa almaktır. Küçük sağa alınır, ortanca sola, ardından küçük sola, büyük sağa. Böylelikle problem iki diske düşer. Küçük ortaya, büyük sağa, küçük sağa ve problem çözülmüştür.
Hamle sayılarına dikkat etmenizi istiyorum. Birinci hamle ile bir disk problemini çözdük, üçüncü hamle ile iki disk, yedinci hamle ile üçüncü disk problemini çözdük. Toplamda 15 hamle ile, dört disk problemini de çözmüş olduk. İşin matematiğine inebiliriz.

Formülasyon

Hanoi kulelerinde dört disk problemininin çözümü 15 hamlede gerçekleşti, üç diskin 7, iki diskin 3, bir diskin 1. Burada yakalayacağımız nokta, aslında yukarıdaki algoritmada geçiyor. Dikkatle inceleyelim.
Üç diski ortada toplamamız 7 hamle almıştır, bundan sonraki 1 hamle, dördüncü diske sağa almaktır. Sonraki hamle ise, 7 hamlede üç diski, bu en büyük diskin üzerine almaktır. Yani yapılan işlem sayısı 7+1+7=15'tir.
Benzeri şekilde üç disk problemini ele alalım. Üç disk probleminde, ilk 3 hamle ile iki disk problemi çözülür, 1 hamle ile büyük disk hedefe konulur, sonraki 3 hamle ile iki disk üstüne eklenir. Yani yapılan işlem sayısı 3+1+3 = 7'dir.
Yani aslında daha alt problemlere ayrılmış şekilde yazacak olursak, dört disk problemi 7+1+7 şeklinden aşağıdaki şekle gelir.
Aslında üç disk probleminin çözümü olan (3+1+3) de (1+(1)+1)+1+(1+(1)+1) şeklindedir. Böylelikle ifade,
halini alır. Problemin nasıl iç içe olduğu, çok daha belirgin bir şekilde ortaya çıktı. Eğer bu sonuçları doğru şekilde formülize etmek istersek, $x$ disk sayısı olmak üzere, minimum hamle sayısı $m$ aşağıdaki şekilde hesaplanabilir.
Böylelikle x=1 için m=1, x=2 için m=3, x=3 için m=7, x=4 için m=15, x=5 için m=31, x=6 için m=63... olarak bulunur. Hanoi kulelerinin mantığını bir kez kavradığınızda, fazla hamle sayısından ötürü sıkılmayacağınız kadar çok diskli problemini, sorunsuz bir şekilde tek seferde tamamlayabilirsiniz.


Hazırlayan:Ögetay Kayalı
Referanslar
1. Mathworld Wolfram, <http://mathworld.wolfram.com/TowerofHanoi.html>
Bu yazı ilk olarak 26 Ağustos 2016 tarihinde yayınlanmıştır.
Bu Makaleyi Alıntıla
Okundu Olarak İşaretle
0
0
  • Paylaş
  • Alıntıla
  • Alıntıları Göster
Paylaş
Sonra Oku
Notlarım
Yazdır / PDF Olarak Kaydet
Bize Ulaş
Yukarı Zıpla

İçeriklerimizin bilimsel gerçekleri doğru bir şekilde yansıtması için en üst düzey çabayı gösteriyoruz. Gözünüze doğru gelmeyen bir şey varsa, mümkünse güvenilir kaynaklarınızla birlikte bize ulaşın!

Bu içeriğimizle ilgili bir sorunuz mu var? Buraya tıklayarak sorabilirsiniz.

Soru & Cevap Platformuna Git
Bu İçerik Size Ne Hissettirdi?
  • Muhteşem! 0
  • Tebrikler! 0
  • Bilim Budur! 0
  • Mmm... Çok sapyoseksüel! 0
  • Güldürdü 0
  • İnanılmaz 0
  • Umut Verici! 0
  • Merak Uyandırıcı! 0
  • Üzücü! 0
  • Grrr... *@$# 0
  • İğrenç! 0
  • Korkutucu! 0
Tüm Reklamları Kapat

Evrim Ağacı'na her ay sadece 1 kahve ısmarlayarak destek olmak ister misiniz?

Şu iki siteden birini kullanarak şimdi destek olabilirsiniz:

kreosus.com/evrimagaci | patreon.com/evrimagaci

Çıktı Bilgisi: Bu sayfa, Evrim Ağacı yazdırma aracı kullanılarak 19/03/2024 07:52:25 tarihinde oluşturulmuştur. Evrim Ağacı'ndaki içeriklerin tamamı, birden fazla editör tarafından, durmaksızın elden geçirilmekte, güncellenmekte ve geliştirilmektedir. Dolayısıyla bu çıktının alındığı tarihten sonra yapılan güncellemeleri görmek ve bu içeriğin en güncel halini okumak için lütfen şu adrese gidiniz: https://evrimagaci.org/s/12759

İçerik Kullanım İzinleri: Evrim Ağacı'ndaki yazılı içerikler orijinallerine hiçbir şekilde dokunulmadığı müddetçe izin alınmaksızın paylaşılabilir, kopyalanabilir, yapıştırılabilir, çoğaltılabilir, basılabilir, dağıtılabilir, yayılabilir, alıntılanabilir. Ancak bu içeriklerin hiçbiri izin alınmaksızın değiştirilemez ve değiştirilmiş halleri Evrim Ağacı'na aitmiş gibi sunulamaz. Benzer şekilde, içeriklerin hiçbiri, söz konusu içeriğin açıkça belirtilmiş yazarlarından ve Evrim Ağacı'ndan başkasına aitmiş gibi sunulamaz. Bu sayfa izin alınmaksızın düzenlenemez, Evrim Ağacı logosu, yazar/editör bilgileri ve içeriğin diğer kısımları izin alınmaksızın değiştirilemez veya kaldırılamaz.

Tüm Reklamları Kapat
Keşfet
Akış
İçerikler
Gündem
Bellek
Genel Görelilik
Maske Takmak
İklim Değişikliği
Bilim İnsanları
Kök Hücre
Antibiyotik
Mers
Araştırmacılar
Nükleer Enerji
Evrim Ağacı
Böcek Bilimi
Çekirdek
Siyah
Avcı
Temel
Gıda Güvenliği
Uterus
Çevre
Amerika Birleşik Devletleri
Çiçek
Film
Karar Verme
Kuş
Demir
Aklımdan Geçen
Komünite Seç
Aklımdan Geçen
Fark Ettim ki...
Bugün Öğrendim ki...
İşe Yarar İpucu
Bilim Haberleri
Hikaye Fikri
Video Konu Önerisi
Başlık
Gündem
Bugün bilimseverlerle ne paylaşmak istersin?
Bağlantı
Kurallar
Komünite Kuralları
Bu komünite, aklınızdan geçen düşünceleri Evrim Ağacı ailesiyle paylaşabilmeniz içindir. Yapacağınız paylaşımlar Evrim Ağacı'nın kurallarına tabidir. Ayrıca bu komünitenin ek kurallarına da uymanız gerekmektedir.
1
Bilim kimliğinizi önceleyin.
Evrim Ağacı bir bilim platformudur. Dolayısıyla aklınızdan geçen her şeyden ziyade, bilim veya yaşamla ilgili olabilecek düşüncelerinizle ilgileniyoruz.
2
Propaganda ve baskı amaçlı kullanmayın.
Herkesin aklından her şey geçebilir; fakat bu platformun amacı, insanların belli ideolojiler için propaganda yapmaları veya başkaları üzerinde baskı kurma amacıyla geliştirilmemiştir. Paylaştığınız fikirlerin değer kattığından emin olun.
3
Gerilim yaratmayın.
Gerilim, tersleme, tahrik, taciz, alay, dedikodu, trollük, vurdumduymazlık, duyarsızlık, ırkçılık, bağnazlık, nefret söylemi, azınlıklara saldırı, fanatizm, holiganlık, sloganlar yasaktır.
4
Değer katın; hassas konulardan ve öznel yoruma açık alanlardan uzak durun.
Bu komünitenin amacı okurlara hayatla ilgili keyifli farkındalıklar yaşatabilmektir. Din, politika, spor, aktüel konular gibi anlık tepkilere neden olabilecek konulardaki tespitlerden kaçının. Ayrıca aklınızdan geçenlerin Türkiye’deki bilim komünitesine değer katması beklenmektedir.
5
Cevap hakkı doğurmayın.
Bu platformda cevap veya yorum sistemi bulunmamaktadır. Dolayısıyla aklınızdan geçenlerin, tespit edilebilir kişilere cevap hakkı doğurmadığından emin olun.
Ekle
Soru Sor
Sosyal
Yeniler
Daha Fazla İçerik Göster
Popüler Yazılar
30 gün
90 gün
1 yıl
Evrim Ağacı'na Destek Ol

Evrim Ağacı'nın %100 okur destekli bir bilim platformu olduğunu biliyor muydunuz? Evrim Ağacı'nın maddi destekçileri arasına katılarak Türkiye'de bilimin yayılmasına güç katın.

Evrim Ağacı'nı Takip Et!
Yazı Geçmişi
Okuma Geçmişi
Notlarım
İlerleme Durumunu Güncelle
Okudum
Sonra Oku
Not Ekle
Kaldığım Yeri İşaretle
Göz Attım

Evrim Ağacı tarafından otomatik olarak takip edilen işlemleri istediğin zaman durdurabilirsin.
[Site ayalarına git...]

Filtrele
Listele
Bu yazıdaki hareketlerin
Devamını Göster
Filtrele
Listele
Tüm Okuma Geçmişin
Devamını Göster
0/10000
Bu Makaleyi Alıntıla
Evrim Ağacı Formatı
APA7
MLA9
Chicago
Ö. Kayalı. Hanoi Kuleleri ve Çözümü. (23 Ağustos 2020). Alındığı Tarih: 19 Mart 2024. Alındığı Yer: https://evrimagaci.org/s/12759
Kayalı, Ö. (2020, August 23). Hanoi Kuleleri ve Çözümü. Evrim Ağacı. Retrieved March 19, 2024. from https://evrimagaci.org/s/12759
Ö. Kayalı. “Hanoi Kuleleri ve Çözümü.” Edited by Ögetay Kayalı. Evrim Ağacı, 23 Aug. 2020, https://evrimagaci.org/s/12759.
Kayalı, Ögetay. “Hanoi Kuleleri ve Çözümü.” Edited by Ögetay Kayalı. Evrim Ağacı, August 23, 2020. https://evrimagaci.org/s/12759.
ve seni takip ediyor

Göster

Şifrenizi mi unuttunuz? Lütfen e-posta adresinizi giriniz. E-posta adresinize şifrenizi sıfırlamak için bir bağlantı gönderilecektir.

Geri dön

Eğer aktivasyon kodunu almadıysanız lütfen e-posta adresinizi giriniz. Üyeliğinizi aktive etmek için e-posta adresinize bir bağlantı gönderilecektir.

Geri dön

Close