Hanoi kuleleri problemi çözümü java

Hanoi kuleleri nedir?

Bir rivayete göre; Tibet’te yaşayan bir grup papaz küçükten büyüğe doğru üst üste bir kazık (A isimli) üzerine yerleştirilmiş, farklı çaplı, ortası delik silindir biçimindeki taşlar, bir başka kazığa (B isimli) taşınmak isteniyor. Fakat bazı kurallar var. Kurallar şu şekilde:
Taşlar birer birer taşınacak. Büyük taş hiçbir zaman kendisinden küçük bir taşın üzerine konulamaz.
Taşımada yardımcı olmak için sadece bir kazık (C isimli) kullanılacak.

Problem 3 veya 4 taş için kolay gözükse bile taş sayısı arttıkça çözüm zorlaşmaktadır.

Aslında 3 tane taş için yapılan hamleler, taş sayısı arttıkça sürekli tekrarlanmaktadır. Bu problemin çözümünde özyineleme mantığı kullanılır.

3 taş için en az 2 üzeri 3 eksi 1′den 7 hamle,
4 taş için en az 2 üzeri 4 eksi 1′den 15 hamle gereklidir. Taş sayısı artıkça yapılması gereken hamle sayısı büyük bir şekilde artmaktadır.

Oyunu denemek için alttaki link kullanılabilir.

http://comp.eng.ankara.edu.tr/tower_%20of_hanoi_DHTML%20game.htm

3 taş için hamleler en az şu şekilde olabilir.
3 tas hanoi

Çözümün kaba kodu şu şekilde:
Algoritma hanoiKuleleri(n, A, B, C)
1. Taş sayısı değerini gir(n)
2. Önce en üstdeki taşı c ye taşı
hanoiKuleleri(n, A, C, B)
3. Kalan n-1 taşı A’dan B’ye taşı
hanoiKuleleri(n-1, A, B, C)
4. C’deki taşı bu kez de B’ye taşı
hanoiKuleleri(n-1, A, C, B)

 

 

 

 

 

 

 

 

 

 

Java kodlarıyla örneği

package hanoikuleleri;
import java.util.*;

public class Hanoikuleleri {

    public static void main(String[] args) 
    {
        System.out.print("n değerini giriniz : ");
        Scanner klavye = new Scanner(System.in);
        int n = klavye.nextInt();
        tasi(n, 'A', 'B', 'C');
    }

    public static void tasi(int n, char A, char B, char C)
    {
        if(n==1)
            System.out.println(A + " --> " + B);
        else
        {
            tasi(n-1, A, C, B);
            tasi(1, A, B, C);
            tasi(n-1, C, B, A);
        }
        return;
    }
}

örneğin 4 taş için; çözüm çıktısı. en az 15 hamle
n değerini giriniz : 4
A –> C
A –> B
C –> B
A –> C
B –> A
B –> C
A –> C
A –> B
C –> B
C –> A
B –> A
C –> B
A –> C
A –> B
C –> B

Bu yazı Java Programlama kategorisine gönderilmiş ve , , , ile etiketlenmiş. Kalıcı bağlantıyı yer imlerinize ekleyin.

  1. kerim der ki:

    Hocam programınız yanlış çalışıyor halkalar C kulesine yerleştirilmeli B kulesine değil

    • blogsahin der ki:

      bazı uygulamalar sadece C kazığına taşımaya izin verirken bazıları da C veya B kazığına gibi ayrım yapmıyor, yukardaki örnekte hedef B fakat C için ise şu yapılabilir,
      kodlarda B yerine C, C yerine B değişiklikleri yapılırsa taşları C’ye taşımak için minumum hareket bulunmuş olur

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

*

Şu HTML etiketlerini ve özelliklerini kullanabilirsiniz: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>