[알고리즘 과목] - 레포트 :: 하노이타워

소개글

[알고리즘 과목] - 레포트 :: 하노이타워에 대한 보고서 자료입니다.

본문내용

&& to==3) || (from==3 && to==1)) passPole=2;
else passPole=1;
if(N>1) { //disc 수가 2이상 일때
move(from,passPole,N-1); //passPole 로 N-1 개를 옮기고,
disc=pole[from].pop(); //맨밑의 disc를 옮긴다.
pole[to].push(disc);
cout << "Disc"< Pole"< count++;
move(passPole,to,N-1); //passPole로 옮겼던 N-1개의 디스크를
//다시 옮기고자하는 Pole로 옮긴다.
}
else if(N==1) { //disc 수가 1개일때,
disc=pole[from].pop(); //그냥 옮긴다.
pole[to].push(disc);
cout << "Disc"< Pole"< count++;
return ;
}
return ;
}
int main() {
//disc 는 int형 data이고 큰숫자의 disc 일수록 큰디스크입니다.
for(int disc=INPUT_DISC_NUM;disc>=1;disc--) {
pole[POLE_START].push(disc);
}
cout <<"==============================="< cout <<" POLE이 세개인 하노이 타워 "< cout <<"==============================="< move(POLE_START,POLE_END,INPUT_DISC_NUM);
cout << endl << "Number of Input Disc : " << INPUT_DISC_NUM < cout << "Number of Disc Movements: " < cout <<"POLE"<< POLE_END <<" 의 DISC 내용 " << endl;
pole[POLE_END].print();
return 0;
}
2. Pole 이 4개일때의 효율적인 처리방안
막대를 늘린 하노이(Multi-peg Hanoi)아마 지금까지 나온 하노이의 탑 관련 문제 중 최대 난제는 막대 수를 늘린 것에서 나올 것이다. 듀드니(Henry E. Dudeney: 수학 퍼즐이나 게임 연구로 유명한 미국 수학자)는 막대가 4개인 경우를 제시하고 '레브의 퍼즐'(The Reve's Puzzle)이라고 불렀다. 물론 듀드니 자신은 막대가 4개인 경우의 답을 알고 있었고, 그 이후 다른 학자들도 퍼즐의 '풀이', 또는 퍼즐을 '푸는' 알고리듬을 발표했다. 그러나 아직 이러한 풀이가 최소임을 증명한 사람은 없었고 아직도 대단히 어려운 문제로 남아 있다.막대를 1개만 늘려도 기본 하노이의 탑 퍼즐이나 다른 변형 퍼즐처럼 지수함수적 증가 관계가 얼른 눈에 띄지 않아서, 원반 n개짜리 탑을 옮기는 시행 횟수 공식을 구하는 것부터가 그렇게 쉬운 문제가 아니다.

키워드

수학,   하노이타워,   알고리즘