Hanoi Kuleleri Problemi (Towers of Hanoi Problem)

Hanoi Kuleleri Problemi (Towers of Hanoi Problem)

Üç kule (A,B,C) olan bir sistemde yarıçapı birbirinden farklı 4 tane diskin A kulesine yerleştirildiğini düşünün (şekil 3.1).

Kurallar :

Bir diskin altında yarıçapı daha küçük bir disk bulunamaz. Bir diskin üzerine yarıçapı daha büyük bir disk yerleştirilemez.

Bir anda bir kulenin sadece en üstündeki disk diğer bir kuleye yerleştirilebilir. Bir anda bir disk hareket ettirilebilir.


şekil 3.1 Hanoi Kulesinin ilk Yerleştirimi

Problemde istenen : B direğinden de yararlanarak tüm disklerin C’ye yerleştirilmesi.

Hanoi Towers Probleminin Çözümü ve C Programı Haline Getirilmesi:

Önce n disk için düşünelim.

• 1 disk olursa, dorudan A’dan C’ye konulabilir (Dorudan görülüyor).

• (n-1) disk cinsinden çözüm üretebilirsek özyinelemeden yararlanarak n disk için de çözümü bulabiliriz.

• 4 diskli bir sistemde, kurallara göre en üstteki 3 diski B’ye yerleştirebilirsek çözüm kolaylaştırır.

Genelleştirirsek :

1. n==1 => A’dan C’ye diski koy ve bitir.

2. En üstteki n-1 diski A’dan C’den yararlanarak B’ye aktar.

3. Kalan diski A’dan C’ye koy.

4. Kalan n-1 diski A’dan yararlanarak B’den C’ye koy.

Problem deyimi : “Hanoi Probleminin Çözümü”

Problem şu an tam olarak tanımlı değil, problem deyimi yeterli değil. Bir diskin bir kuleden diğerine tanınmasını bilgisayarda nasıl temsil edeceğiz? Programın Girdileri nelerdir? Çıktıları nelerdir? belli değil.

Girdi/Çıktı tasarımı herhangi bir problemin çözümünün programın algoritmasının oluturulmasında önemli yer tutar. Oluturulacak algoritmanın yapısı da büyük ölçüde girdi ve çıktılara balı olacaktır. Uygun girdi ve çıktı tasarımı, algoritmaların gelitirilmesini kolaylatırabilir ve etkinlik salar.

Girdi :

disk sayısı : n kuleler : A, B, C (uygun)

Çıktı :

disk nnn’i, yyy kulesinden alıp zzz kulesine yerleştir.

nnn : disk numarası. En küçük disk 1 numara (en küçük sayı olması doğrudan) yyy ve zzz de kule adı.

Ana programdan towers fonksiyonunun çağrılması :

void main() {

int n; scanf(“%d”,&n);

towers(parameters);

}

şimdi parametreleri belirleme aşamasına gelindi :

#include <stdio.h>

void towers(int, char, char, char);

void main()

{

int n;

scanf(“%d”,&n);

towers(n,’A’,’B’,’C’);

}

void towers(int n, char frompeg, char topeg, char auxpeg)

{

if(n==1) {

printf(“\n%d%s%c%s%c%s”,n,”. diski “,frompeg,” kulesinden alıp “, topeg, ” kulesine yerleştir”); return;

};

towers(n-1, frompeg,auxpeg,topeg); // n-1 diskin yardımcı kuleye konulması printf(“\n%d%s%c%s%c%s”,n,”. diski “,frompeg,” kulesinden alıp “,

topeg, ” kulesine yerleştir”);

towers(n-1, auxpeg,topeg,frompeg); // n-1 diskin hedef kuleye konulması

}

Programın n=3 disk için çalıştırılması sonucu oluşan ekran çıktısı :

1. diski A kulesinden alıp C kulesine yerleştir

2. diski A kulesinden alıp B kulesine yerleştir

1. diski C kulesinden alıp B kulesine yerleştir

3. diski A kulesinden alıp C kulesine yerleştir

1. diski B kulesinden alıp A kulesine yerleştir

2. diski B kulesinden alıp C kulesine yerleştir

1. diski A kulesinden alıp C kulesine yerleştir

 

Hazırlayan: Baran Kısa       

Bir Cevap Yazın

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