하노이의 탑 c 예제

안녕하세요. 이번에는 c를 공부하다보면 대부분 마주치는 하노이의 탑에대해서 올려 보겠습니다.

 

어린 얘들의 사고력?을 키워주기 위해 장난감으로도 있는데요.

이 문제의 기본적 조건이 있습니다.

1. 큰 원판은 작은 원판에 올라가지 못한다.

2. 한번에 한개씩만 움직일 수 있다.

3. 3개의 움직일 수 있는 칸?이 있다.

 

위키백과 가기

위키백과에 애니메이션까지 설명이 아주 잘 나와 있어요.

아래 있는 소스 또한 위키백과에 있는 소스를 가지고 만든 소스입니다.

거기에 시간을 재는 clock() 함수를 이용해서 시작 끝시간을 확인해 원판에 개수에 따라 걸리는 시간을 체크 했습니다.

 

전 항상 소스를 올리도록 노력합고있어요!

아래 캡쳐된 그림의 Count : 는 원판의 갯수고 뒤는 시간이에요! 대략 두배씩 시간이 오르네요!

조금이라도 정확한 시간을 보려고 printf문은 뻇습니다.)

 

반응형

#include <stdio.h>

#include<time.h>

int Cnt;

void hanoi(int n, int a, int b)

{

 int temp;

 if(n==1)

 {

 //printf("Move %d, move from Fall : %d, to Fall : %d\n", n, a, b);

 }

 else

 {

 temp=6-a-b;

 hanoi(n-1, a, temp);

 //printf("Move %d, move from Fall : %d, to Fall : %d\n", n, a, b);

 hanoi(n-1, temp, b);

 }

        Cnt++;

}

int main()

{

 int n = 2;

 while(true)

 {

 n++;

 printf_s("Count: %d", n);

 //scanf_s("%d", &n);



 clock_t st, et; //각각 start time, end time을 의미(이름 상관 없음)

 st = clock();



 hanoi(n, 1, 2);

     //printf("Count : %d\n",Cnt);

 et = clock();

 double Colcok = double((et - st) / 1000.0);

 printf("\t%f s\n", Colcok);

 }

 return 0;



}