Hanoi Kuleleri Problemine Özyinelemeli Çözüm

Hanoi Kuleleri probleminde, elimizde 3 tane çubuk ve çubuklardan birbirine geçirilmiş halde duran, büyüklüğü aşağıdan yukarıya doğru azalan n tane disk vardır.

n = 4 için Hanoi kuleleri

Problemde amaç, diskleri en soldaki çubuktan en sağdakine taşımaktır. Bir çubukta duran en tepedeki çubuk, herhangi başka bir çubuğa yerleştirilebilir ama bir çubukdaki diskler her zaman aşağıdan yukarıya büyüklükleri azalacak şekilde yerleştirilmelidir.

n = 4 için Hanoi kulelerine çözüm

Görülebileceği üzere, n diski A çubuğundan C çubuğuna taşımak için, ilk olarak (n-1) diski A’dan B’ye, ardından son kalan en büyük diski A’dan C’ye, ardından da B’deki (n-1) diski B’den C’ye taşımalıyız. Yani :

Hanoi(n, A, C) = Hanoi(n-1, A, B), Hanoi(1, A, C), Hanoi(n-1, B, C) 

Bu durumun özyinelemeli bir fonksiyon yaratacağı barizdir.

Özyinelemeli fonksiyonun görselleştirilmesi
#include <bits/stdc++.h>
using namespace std;

// Fonksiyondaki disk parametresi taşınacak disk sayısını,
// ilk parametresi ilk durumda disklerin bulunduğu çubuğu,
// son parametresi disklerin taşınacağı çubuğu,
// ara parametresi de boş çubuğu göstermektedir
void hanoi(int disk, char ilk, char ara, char son){

    // Bu if ifadesi fonksiyonumuzun sunsuz döngüye girmesini
    // veya disk parametresinin eksili değerlere düşmesini
    // engeller
    if(disk == 1){

        // disk sayısının bir olduğu durumlarda disk başka 
        // bir işlem yapılmadan taşınır.    
        cout << ilk << "'den " << son << "'a bir disk taşı\n";
        return;
    }
    
    // Üstteki n-1 disk aradaki çubuğa taşınır.
    hanoi(disk-1, ilk, son, ara);

    // En altta kalan disk hedefe taşınır.
    hanoi(1, ilk, ara, son);

    // Aradaki çubuktaki n-1 disk hedefe taşınır.
    hanoi(disk-1, ara, ilk, son);
}

int main(){
    hanoi(4, 'A', 'B', 'C');
}

Programın çıktıları aşağıdaki gibi olur:

A'den B'a bir disk taşı
A'den C'a bir disk taşı
B'den C'a bir disk taşı
A'den B'a bir disk taşı
C'den A'a bir disk taşı
C'den B'a bir disk taşı
A'den B'a bir disk taşı
A'den C'a bir disk taşı
B'den C'a bir disk taşı
B'den A'a bir disk taşı
C'den A'a bir disk taşı
B'den C'a bir disk taşı
A'den B'a bir disk taşı
A'den C'a bir disk taşı
B'den C'a bir disk taşı
2 Comments

Add a Comment

Your email address will not be published. Required fields are marked *