Hanoi Tower
PC를 이용한 Hanoi Tower 시간 측정
목차………………………
1.Hanoi_Tower란..?…
2.Hanoi_Tower.cpp…
3.시간_측정………………
4.느낀_점…………………
1.Hanoi Tower란..?
(1). 하노이 타워의 원리
하노이 타워의 조건
1. 원반은 한번에 하나씩만 옮길 수 있다.
2. 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.
하노이 타워는 원반의 수가 늘어나도 해결방법에는 차이가 없다. 다만 원반의 수가 늘어날수록 일련의 과정을 더 많이 반복해야 할 뿐이다.
그래서 그 일련의 과정을 파악하면 해결할 수 있게 된다.
원반 n개를 옮기는 과정
1. 작은 원반 n-1개를 A에서 B로 이동
2. 큰 원반 1개를 A에서 C로 이동
3. 작은 원반 n-1개를 B에서 C로 이동
이렇게 원반 n개를 이동하는 문제는 원반 n-1개를 이동하는 문제로 세분화되고, 또 원반 n-1개를 이동하는 문제는 원반 n-2개를 이동하는 문제로 세분화 된다.
즉, 원반 n개를 이동하는 문제는 결국 원반 1개를 이동하는 매우 쉬운 문제로 세분화되는 것이다.
재귀 함수에서 가장 중요한 것은 제귀의 탈출 조건이다.
탈출조건은 “이동해야 할 원반의 수가 1개인 경우(n == 1)” 일 때 재귀에서 나오면 된다.
위 그림은, 하노이 타워에 원반이 3개일 때 7번에 경우를 그림으로 표현한 것으로 쉽게 이해를 할 수 있을 것이다.
(2)하노이타워의 역사
세 개의 말뚝(L, R, C)과 지름이 서로 다른 임의의 개수의 원판이 주어진다. 지름이 큰 원판은 항상 작은 원판보다 아래에 오도록 하며, 말뚝의 상위에 있는 한 개의 원판만을 이동시킬 수 있다. 이와 같은 조건하에서 말뚝 L에서 말뚝 C를 이용하여 말뚝 R로 원판을 이동시키는 문제로, 문제 해결에서 수단 목표 분석의 한 예가 된다.
[네이버 지식백과] 하노이 탑 [Hanoi tower] (실험심리학용어사전, 2008, 시그마프레스㈜)
오늘(20140311) 강의 중에 교수님께서 말하시길 3기둥과 64개의 원판이 있는데 이것을 다 옮기면 지구가 멸망하다는 소리가 있다고 하셨다.. 근데 64개 옮기는데 걸리는 시간지 약 2000억년이라고 하셨다..;;ㄷㄷ하네
2.Hanoi_Tower.cpp
Hanoi_Tower.cpp에서 timeMeasure()함수를 구현하여 표현 할려고 했지만, 시작시간은 start변수에 받을 수 있지만 stop변수에 값을 어떻게 얻어야 할지 햇갈려 아래와 같이 구현하였으며, 구지 구현을 한다면
#include <time.h>
timeMeasure()
{
{
clock_t start, end; double diff;
start = clock();
funcToBeTested();
end = clock();
diff = (double)(end - start) / CLOCKS_PER_SEC;
}
와 같이 구현하면 되나 funcToBeTested()함수에 대해 찾지 못해서 main내부에 시간을 계산하는 소스를 넣었다.
#include <stdio.h>
#include <time.h>
int count = 0; //Hanoi_tower의 이동 횟수를 위한 변수.
void hanoitower(char from, char temp, char to, int n); //hanoitower를 해결하기 위한 함수
int main(){
//hanoitower의 경우를 해결하는데 걸리는 시간을 계산하기 위한 변수
clock_t start,stop; //시작시간, 정지시간
double result; //계산한 결과 시간
start = clock(); //clock()함수로 시작 시간을 기록
//hanoitower 함수 실행
int n; //원반의 갯수를 기록
//원반의 갯수를 입력받음
printf("원반의 수를 입력 하시오 : ");
scanf("%d",&n);
//함수 실행 , 1,2,3은 기둥의 위치
hanoitower('1','2','3',n);
stop = clock(); //함수가 종료된 시간을 계산
result = ((double)(stop-start)) / CLOCKS_PER_SEC;
//횟수 출력
printf("number of disc movements: %d\n",count);
//걸린 시간 출력
printf("걸린 시간은 %f 입니다.\n", result);
return 0;
}
void hanoitower(char from, char temp, char to, int n){
//이동할 원반의 갯수가 1개일 경우
if(n == 1){
count ++;
printf("Disc%d Pole%c -> Pole%c\n", n , from, to);
}
//그렇지 않을 경우 재귀가 일어나며,
else{
hanoitower(from, to, temp, n-1);
count++; //count횟수를 증가시킴
printf("Disc%d Pole%c -> Pole%c\n", n ,from,to);
hanoitower(temp,from,to,n-1);
}
}
/******수정한 소스 _********/
#include <stdio.h>
#include <time.h>
int count = 0; //Hanoi_tower의 이동 횟수를 위한 변수.
void timeMeasure(int
n); //시간측정을 위한 함수.
void hanoitower(char
from, char temp, char
to, int n); //hanoitower를 해결하기 위한 함수
int main(){
int n; //원반의 갯수를 기록
//원반의 갯수를 입력받음
printf("원반의 수를 입력 하시오 : ");
scanf("%d",&n);
timeMeasure(n);
return 0;
}
//원반갯수를 받음
void timeMeasure(int
n){
//시작시간,정지시간, 결과
clock_t start,stop;
double
result;
//시작시간
start = clock();
//함수실행
hanoitower('1','2','3',n);
//함수종료 후 시간
stop = clock();
//결과 계산
result = ((double)(stop-start))
/ CLOCKS_PER_SEC;
//횟수 출력
printf("number of disc movements: %d\n",count);
//걸린 시간 출력
printf("걸린 시간은
%f 입니다.\n", result);
}
void hanoitower(char
from, char temp, char
to, int n){
//이동할 원반의 갯수가 1개일 경우
if(n == 1){
count
++;
printf("Disc%d Pole%c -> Pole%c\n", n ,
from, to);
}
//그렇지 않을 경우 재귀가 일어나며,
else{
hanoitower(from, to, temp, n-1);
count++; //count횟수를 증가시킴
printf("Disc%d Pole%c ->
Pole%c\n", n ,from,to);
hanoitower(temp,from,to,n-1);
}
}
3.시간 측정
다음은 hanoi_Tower.cpp를 실행하며 원하는 답을 출력하는데 걸린 시간을 측정한 내용이다.
하...원반에 갯수가 20개 부터는 시간이 걸린다는게 확연히 느껴지면서...26개 이후는 할 자신이 안 생겼다...
'이런걸 과제가 아니면 언제 해보겠는가...?'
라는 생각으로 오기로 과제 제출전까지 생각날때마다 해볼까 한다.. 하지만 교수님께서는 이정도만 하기를 원하실거라는 생각에 정리는 26개까지한다..
(무슨말..?)
여튼 대략 2배씩 증가하는게 보인다..전에 선형대수를 배울 때 Hanoi Tower문제를 풀었던게 생각난다...하...
- 다음 두 그래프는 아래 표를 나타낸 것이다.
4. 느낀 점
블로그에 내가 느낀점까지 쓸건 없는듯 헤헤
댓글 없음:
댓글 쓰기