Hanoi kuleleri - recursion

[the_joker]

Recursive algoritmaya iyi bir örnek.
Hanoi Kuleleri, birçok proglamlama dilinde öğretici bir algoritmadır. Öncelikle soruyu açıklayayım:

Elimizde üç tan kule var ve kulelerin ilkinde n tane disk var. Diskler, kuleye, en küçük en üstte olmak üzere küçükten büyüğe dizilmiştir. Yapılması gerekense 1. kuledeki tüm diskleri 3. kuleye taşımak (İkinci kule taşırken aracı olarak kullanılacak). Yalnız taşırken dikkat edilmesi gereken iki önemli kural var.

1) Asla büyük disk, küçük diskin üstüne gelmeyecek.
2) Bir seferde yalnızca 1 tane ve en üstte olan disk taşınacaktır.

Bu kurallar doğrultusunda soruyu çözmeye çalışalım. Bu taşıma işlemlerini kalem kağıt ile denerseniz göreceksinizki n - 1 tane diski taşımak için yaptığınız işlem sayısı a ise, n diski taşımak için yapacağınız işlem sayısı 2a + 1 olacaktır. Aslında bunun çıktığı nokta şurasıdır: n - 1 disk önce 1 den 2 ye taşınır (a tane işlem). Daha sonra n. disk 1 den üçe taşınır (1 işlem). Daha sonra 2. kuledeki n - 1 disk 3. kuleye taşınır (a tane işlem daha). Bu şekilde olayı ele alırsak 1 tane diski taşıyabiliyorsak hepsini taşıyabiliriz demektir.


(1 -> 2) 1. kuledeki taşınabilir disk 2. kuleye taşınsın manasında olmak üzere iki diskin taşınmasını

1 -> 2
1 -> 3
2 -> 3

şeklinde ifade edebiliriz. Yani üç işlemde.

Üç disk için:
1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3
şeklindedir. Yani toplam yedi işlem yapılmaktadır. Ayrıca dikkat edersek n tan diski taşıma için 2^n - 1 tane işlem yapmamız gerekiyor.

Algoritmayı anladıktan sonra programlama kısmı oldukça basit. C'ye yakın birçok kişi algoritmayı anlamışsa eğer kodu anlamakta güçlük çekmeyecektir, yeterince sade olduğunu düşünüyorum.

#include <stdio.h>
#include <conio.h>

void disk_mov(int value, int kule1, int kule3, int kule2);

main()
{
int disks;

printf("Tasinacak disk sayisini girin:");
scanf("%d", &disks);

disk_mov(disks, 1, 3, 2);


getch();
return 0;
}  

void disk_mov(int value, int kule1, int kule3, int kule2)
{
if (value == 1) {
printf("%d -> %d\n\
", kule1, kule3);
return;
}

disk_mov(value - 1, kule1, kule2, kule3);
printf("%d -> %d\n\
", kule1, kule3);
disk_mov(value - 1, kule2, kule3, kule1);
}