[C언어][C프로그래밍] 하노이의 탑 - 역사, 수학적 원리, 프로그램 소스

소개글

하노이의 탑의 역사와 수학적 원리에 대해 조사하고, 프로그래밍 코드를 수록하였습니다.

목차

1. 하노이의 탑에 대해
1) 역사
2) 하노이의 탑의 규칙
3) 하노이의 탑의 수학적 풀이

2. C 언어 소스

본문내용

1. 하노이의 탑에 대해
역사
하노이의 탑은 1883년 프랑스 수학자 뤼카(Édouard Lucas)가 1883년 클라우스 교수(professeur N. Claus)라는 필명으로 발표한 퍼즐이다. 1년 후인 1884년, 드 파르빌(Henri de Parville)이 Claus가 Lucas의 애너그램(음절의 순서를 뒤섞어놓은 것)임을 밝히면서 전설의 형태로 하노이의 탑 문제를 소개하였다.
전설: 인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 됩니다.
위의 이야기는 전설일 뿐이지만, 실제로 베트남 하노이에 있는 한 사원 터에서는, ‘하노이의 탑’이라는 유물이 발굴되었다.

하노이의 탑의 규칙
하노이의 탑
하노이의 탑은 기둥 3개와 각각 크기가 다른 원판 n개로 이루어져 있다. 맨 처음에 원판은 모두 탑의 왼쪽 기둥에 있으며, 작은 원판이 큰 원판 위쪽에 있다.(사진) 이제 이 n개의 원판을 모두 다른 기둥(가운데 기둥 또는 오른쪽 기둥)에 옮기는데, 다음과 같은 규칙으로 옮긴다.
➀ 한 번에 한 개의 원판만을 움직일 수 있다.
➁ 큰 원판이 작은 원판 위에 올라가면 안 된다.

<중 략>

참고로, 위의 점화식과 일반항에 관한 논문은 1884년 앨러디스(R. E. Allardice)와 프레이저(A. Y. Fraser)에 의해 발표되었다. 그러나 위 점화식에서는 그것이 정말 최소횟수인가는 알 수 없다. 따라서 이것이 최적해인 것에 관한 논문은 오랜 연구 끝에 1981년에 발표되었다.

참고 자료

없음