Hanoi Kuleleri Oyunu C++ ve C# Dilinde Çözümü (Performans Analizinin Gerçekleştirilmesi)

Standard

Hanoi Kuleleri Nedir? Nasıl Oynanır?

Hanoi kuleleri matematik oyunu veya bulmacadır.Bu matematik oyununun oynandığı platform 3 direkten ve farklı boyutlarda disklerden oluşur.Bulmaca en küçük diskin farklı bir çubukta en üste koyulmasıyla biter fakat oyunun bazı kuralları vardır bunlar :

  • Her hamlede sadece bir disk taşınabilir,
  • hiç bir disk kendisinden küçük bir diskin üzerine koyulamaz.

Peki kaç disk için kaç haraket gerçekleştirilir:

3 disk = 7 hareket
4 disk = 15 hareket
5 disk = 31 hareket
6 disk = 63 hareket
7 disk = 127 hareket

hanoi kuleleri

hanoi kuleleri

Bilgisayarınız bu hareketleri ne kadar sürede tamamlar?

Aşağıda c dilinde yazılan kodlar ile hem bilgisayarınızı test etmiş olursunuz hemde bu sorunun yanıtını bulabilirsiniz. bilgisayarımda kuledeki disk sayısına göre harcanan zamana bir göz atalım:

1 diskten 15 disk’e kadar 1 saniyeden az bir zamanda işlem gerçekleşti. Diskler arttıkça işlem karmaşıklaşıyor. Bu yüzden zaman da artmaya başladı.
16>> 2 ms.
17>> 5ms.
18>> 9ms.
19 >>18ms.
20 >>40ms.
21>> 79 ms.
22>> 290ms.

23>> 548ms.
24>> 878ms.
25 >>1746ms.
26 >>3191ms.
27 >>7252ms.
28>> 13265ms.
29>> 26914ms.

Çözüm için ipuçları :

İlk önce Diskler büyükten küçüğe doğru sıralanır.En büyük disk en altta olmak üzere. Oyunun amacı en küçük diskin şekil nereye oynatılacaksa o direğe takılması ve ardından küçük diskten sonraki disklerin farklı direklere geçirilerek aynı kulenin farklı bir direğe kurallara uyulmak şartıyla konulmasıdır.Şekildeki gibi eyer 3 tane disk varsa o zaman 7 hareket yapılması gerekir 7 hareketi geçmemeli.

http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm Bu sayfada basitçe bir similatör var. Buradan kendinizi test edebilirsiniz.

c++ Dilinde Çözüm

aşağıda hanoi kulesi problemi rekürsif fonksiyon ile çözülmüştür.

#include “stdafx.h”

#include <stdio.h>

#include <time.h>

#define MAX_SIZE 5001

#define ITERATIONS 100 //Hanoi kulesinin eleman sayısını buraya yazıyoruz Otomatik artmayı for ile buradan okunan değer ile sağladık.

void hanoi1(int n, char *kaynak, char *ara, char *hedef){  //Hanio Fonksiyonumuz(ozyinelemeli)

if (n != 1) //printf(“%s -> %s\n”, kaynak, hedef);

{

hanoi1(n – 1, kaynak, hedef, ara);

// printf(“%s -> %s\n”, kaynak, hedef); yazdırarak zaman kaybetmemek için kapattım

hanoi1(n – 1, ara, kaynak, hedef);

}

}

int main(void)

{

int i;

clock_t start, stop;

int duration;

printf(” Performans Olcumu (Hanoi Kuleleri)\n ———————————————–\n”);

for (i = 1; i<ITERATIONS; i++){

start = clock();

hanoi1(i, “A”, “B”, “C”);

stop = clock();

duration = (int)(1000 * (stop – start) / CLK_TCK);

printf(“%d elemanli hanoi kulesi %4d milisaniye surdu\n”, i, duration);

printf(“\n”);       }

int m;

scanf_s(“%d”, &m);

return 0;

}

 

c# Dilinde Çözüm

using System;
using System.Collections.Generic;
using System.Text;

namespace Tower
{
class Program
{
static int movecount = 0;
static public void Solve2DiscsTOH(Stack<int> source, Stack<int> temp, Stack<int> dest)
{
temp.Push(source.Pop());
movecount++;
PrintStacks();
dest.Push(source.Pop());
movecount++;
PrintStacks();
dest.Push(temp.Pop());
movecount++;
PrintStacks();
}

static public bool SolveTOH(int nDiscs, Stack<int> source, Stack<int> temp, Stack<int> dest)
{
if (nDiscs <= 4)
{
if ((nDiscs % 2) == 0)
{
Solve2DiscsTOH(source, temp, dest);
nDiscs = nDiscs – 1;
if (nDiscs == 1)
return true;

temp.Push(source.Pop());
movecount++;
PrintStacks();
//new source is dest, new temp is source, new dest is temp;
Solve2DiscsTOH(dest, source, temp);
dest.Push(source.Pop());
movecount++;
PrintStacks();
//new source is temp, new temp is source, new dest is dest;
SolveTOH(nDiscs, temp, source, dest);
}
else
{
if (nDiscs == 1)
return false;
Solve2DiscsTOH(source, dest, temp);
nDiscs = nDiscs – 1;
dest.Push(source.Pop());
movecount++;
PrintStacks();
Solve2DiscsTOH(temp, source, dest);
}
return true;
}
else if (nDiscs >= 5)
{
SolveTOH(nDiscs – 2, source, temp, dest);
temp.Push(source.Pop());
movecount++;
PrintStacks();
SolveTOH(nDiscs – 2, dest, source, temp);
dest.Push(source.Pop());
movecount++;
PrintStacks();
SolveTOH(nDiscs – 1, temp, source, dest);
}
/***
// For your understanding purpose
if (nDiscs == 5)
{
SolveTOH(3, source, temp, dest);
temp.Push(source.Pop());
SolveTOH(3, dest, source, temp);
dest.Push(source.Pop());
SolveTOH(4, temp, source, dest);
}
else if(nDiscs == 6)
{
SolveTOH(4, source, temp, dest);
temp.Push(source.Pop());
SolveTOH(4, dest, source, temp);
dest.Push(source.Pop());
SolveTOH(5, temp, source, dest);
}
else if (nDiscs == 7)
{
SolveTOH(5, source, temp, dest);
temp.Push(source.Pop());
SolveTOH(5, dest, source, temp);
dest.Push(source.Pop());
SolveTOH(6, temp, source, dest);
}
***/
return true;
}

static public Stack<int> A = new Stack<int>();
static public Stack<int> B = new Stack<int>();
static public Stack<int> C = new Stack<int>();

static public void PrintStacks()
{
if (countA != A.Count ||
countB != B.Count ||
countC != C.Count)
{
int diffA = A.Count – countA;
int diffB = B.Count – countB;
int diffC = C.Count – countC;
if (diffA == 1)
{
if (diffB == -1)
Console.Write(“Move Disc ” + A.Peek() + ” From B To A”);
else
Console.Write(“Move Disc ” + A.Peek() + ” From C To A”);
}
else if (diffB == 1)
{
if (diffA == -1)
Console.Write(“Move Disc ” + B.Peek() + ” From A To B”);
else
Console.Write(“Move Disc ” + B.Peek() + ” From C To B”);
}
else //if (diffC == 1)
{
if (diffA == -1)
Console.Write(“Move Disc ” + C.Peek() + ” From A To C”);
else
Console.Write(“Move Disc ” + C.Peek() + ” From B To C”);
}
countA = A.Count;
countB = B.Count;
countC = C.Count;
Console.WriteLine();
}

PrintStack(A);
Console.Write(” , “);
PrintStack(B);
Console.Write(” , “);
PrintStack(C);
Console.Write(” , “);
}
static int countA = 0;
static int countB = 0;
static int countC = 0;

static public void PrintStack(Stack<int> s)
{
Stack<int>.Enumerator et = s.GetEnumerator();
Console.Write(“[“);
string str = “”;
while(true)
{
if(et.MoveNext() == false)
break;
str += et.Current.ToString();
}
for (int i = str.Length – 1; i >= 0; i–)
Console.Write(str[i]);
Console.Write(“]”);
}

static void Main(string[] args)
{
while (true)
{
Console.Write(“\nEnter the number of discs (-1 to exit): “);
string s = Console.ReadLine();
movecount = 0;
int maxdisc = Convert.ToInt32(s);
if (maxdisc == -1)
{
Console.WriteLine(“Good Bye!”);
return;
}
if (maxdisc <= 1 || maxdisc >= 10)
{
Console.WriteLine(“Enter between 2 – 9”);
continue;
}
for (int i = maxdisc; i >= 1; i–)
A.Push(i);
countA = A.Count;
countB = B.Count;
countC = C.Count;
PrintStacks();
SolveTOH(maxdisc, A, B, C);
Console.WriteLine(“Total Moves = ” + movecount);
while (C.Count > 0)

C.Pop();

}
}
}
}


Ekran Çıktısı:

hanoi Kulesi nasıl çözülür c

Kaynaklar:

http://www.csharpnedir.com/forum2/forum_posts.asp?TID=22806

http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm

http://www.onurmihci.com/wp-content/uploads/2010/05/HANO%C4%B0-KULELER%C4%B0.ppt