문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 하노이의 탑 (문서 편집) [목차] == 전설 == [[1883년]] [[프랑스]]의 [[수학자]] 에두아르드 뤼카(Lucas,E. : 1842~1891)가 처음으로 발표한 게임이다. 이후 여러 사람을 거치면서 다음과 같은 [[전설]]이 덧붙여졌다. >고대 [[인도]] [[바라나시|베나레스]]에 있는 한 사원의 이야기 >여기에는 [[다이아몬드]]로 이루어진 3개의 기둥이 있고, 그 기둥 중 하나에 가운데에 구멍이 나 기둥에 끼울 수 있게 된 64개의 크기가 각각 다른 [[황금]] [[원반]]이 꽂혀 있다고 한다. 황금 원반은 가장 아래쪽에 있는 것이 가장 크고 위로 갈수록 점차 작아져 전체적으로 원추형의 탑을 이루고 있는데, 원반은 한 번에 하나씩만 옮길 수 있으며 작은 원반 위에 그보다 더 큰 원반을 옮길 수 없다. >이 규칙으로 64개의 원반을 처음 놓여 있던 막대에서 다른 막대로 모두 옮기면 탑은 무너지고 [[세계멸망|세상의 종말이 온다]]고 한다. 이 가짜 전설 덕분에 [[인도]]에 있는 [[바라나시|베나레스]][* 현재 이름은 [[바라나시]].]가 [[베트남]]의 [[하노이]]와 같은 곳인 줄 아는 사람들이 꽤 많은 듯하다. 이 규칙들을 이용하여 64개의 원반을 다른 막대로 전부 옮기는 것은 간단해 보이지만 '작은 원반 위에 큰 원반을 올릴 수 없다' 는 규칙은 의외로 크게 작용하는데, 이를 지키면서 n개의 원반을 한쪽 기둥에서 다른 쪽으로 옮기는 데 걸리는 최소 횟수가 [math( 2^n - 1 )]번이기 때문이다. [math(n+1)]번째 원반을 목표로 하는 비어있는 한 기둥으로 옮기려면, 우선 그 위의 1번부터 [math(n)]번째까지의 원반을 목표로 하는 기둥 이외의 비어있는 기둥으로 옮겨야만 한다. 이 사실을 이용해서 다음과 같이 1번부터 [math(n+1)]번째까지의 원반을 목표로 하는 기둥으로 옮기는 데 요구되는 원반이동 횟수를 계산할 수 있다. 1부터 [math( n )]번째까지의 원반을 비어있는 한 기둥으로 옮기는 데 필요한 최소 횟수를 [math( a_n )]라고 하자. 1번부터 [math( (n+1) )]번째까지의 원반을 목표로 하는 비어있는 기둥으로 옮기려면 ([math( a_{n+1} )]을 구하려면) [math( n )]번째까지의 원반을 비어있는 다른 기둥으로 옮기고 ([math( a_n )]를 더하고) [math( (n+1) )]번째 원반을 목표로 하는 기둥으로 옮기고 ([math( 1 )]을 더하고) [math( n )]번째까지의 원반을 [math( (n+1) )]번째 원반 위로 옮기면 ([math( a_n )]를 다시 더하면) 된다. 따라서 [math( a_1 = 1, a_{n+1}=2a_n+1 )]이고 이 [[점화식]] (Recursive relation)에 의한 수열 [math( a_n )]의 일반항을 구해보면 [math( a_n=2^n - 1 )]가 나온다.[* 이 수열의 일반항을 구하는 방법은 다음과 같다.[br]관계식 [math( a_{n+1} = 2 a_n + 1)]을 [math( a_{n+1}+1 = 2(a_n+1) )]로 변형하고, [math( b_n=a_n+1 )]이라고 두면 [math( b_{n+1} = 2b_n )]이 되므로 [math( b_n )]는 첫째항이 [math( b_1 = a_1 + 1 = 2 (\because a_1=1))]이고 공비가 [math( 2 )]인 등비수열이 된다. 따라서 [math( b_n = a_n + 1 = 2^{n} )] 이므로 [math( \therefore a_n = 2^{n} - 1 )]이다.] 따라서 64개의 원반을 완전히 옮기는 데 걸리는 횟수는 [math( 2^{64} - 1 )], 자그마치 1844경 6744조 737억 955만 1615회에 달한다. 판을 한 번 옮기는 데 1초가 걸린다 해도 약 5849억년이 걸리는데[* 이 시간은 [[64비트]] 정수형으로 시간을 표기하는 시스템이 한계에 도달하는 데에 필요한 시간과도 같다. 자세한 내용은 [[2038년 문제]] 문서로.], 이는 [[우주]]의 나이인 130~135억년보다도 훨씬 길며 중소형 [[적색왜성]]의 예상 수명과 맞먹는 시간이다. --세계멸망이 오고도 남을 만큼 길다-- 하지만 만약 막대를 하나 더 추가해서 네 개로 만든다면 최소 18,433번만 옮기면 되는데, 1초에 판을 1개 옮긴다 할 때 5시간 7분 13초면 된다. --여전히 오래 걸린다.--[* 사실 기둥이 4개인 하노이 탑 관련 문제는 정말 골 때리는 문제인데, 최소이동경로를 확정할 수가 없기 때문이다. 이유는? 간단하다. 원반이 3개라고 가정하고 첫 번째 원반을 1기둥 -> 4기둥으로 옮긴다고 가정한다.(아무데나 상관이 없다) 그러면 2번째 기둥은? 2번 기둥이나 3번 기둥으로 옮길 수 있게 된다. 즉, 최소 횟수를 위한 이동경로가 한 개가 아니다. 그러면 내가 최소이동횟수를 구해도 "이게 정말 이렇게 옮겼을 때의 최소 이동횟수가 맞나?"라는 질문에 대답을 할 수가 없다.(심지어 이건 아직 증명되지도 않았다.) 원반이 3개면 그게 뭐가 어렵나고 할 수 있지만 우리가 원하는 것은 3개가 아닌 100개, 1000개, 나아가 n개의 원반에서 이동 횟수, 즉 일반항을 구하는 것이 궁극적 목표인데, 거의 논문 하나가 나올 정도로 어렵기에 그냥 논문을 참조하는 것을 추천한다.(논문에서조차 증명은 없다. 그냥 점화식을 구하고 점화식을 토대로 일반항만 구했지, 이게 정말 최소횟수인지 증명하는 내용은 없다.)] == [[퍼즐]] == [[파일:external/437a6637b1f6834a74146f6e51b7360fa64116c23c3c0c7fd5462db9a8a73ab4.jpg]] 1의 이야기에서 따와 3개의 기둥에 적당한 개수의 원반을 쌓아 놓고 다른 쪽으로 옮기는 게임. 원반 개수가 늘어날수록 이동 횟수가 엄청나게 늘어나기 때문에 많아야 7, 8개 정도만 쓰며 소모 시간으로 승부를 짓는 것이 보통인데, 이 정도면 1초에 원반 하나를 옮긴다 가정할 때 2~4분 정도 걸린다. [[프로그래밍]] 공부를 하는 사람들의 초반의 벽이 이것의 알고리즘을 구현하는 것. 보통 [[재귀함수]]에 대해 공부할 때 예제로 쓰기 좋아 한번쯤은 보고 넘어가는 문제이다. 다음은 다양한 프로그래밍 언어로의 예제 구현이다. n번째 링을 세번째 기둥으로 옮기기 위해선 1부터 n-1까지의 링을 모두 세번째 기둥이 아닌 다른 기둥으로 옮겨야 한다. 그렇다면 1부터 n-1까지의 링을 어떻게 두번째 기둥으로 옮길까? 당연히 1부터 n-2까지의 링을 모두 두번째 링이 아닌 다른 기둥으로 옮겨두는 것이다. 이처럼 큰 문제를 해결하기 위해 작은 문제를 계속 호출하는 것이 하노이의 탑 재귀 구현의 핵심이라고 보면 된다. === [[OCaml]] === let rec move_tower n a b c = match n with | 1 -> [(a,c)] | _ -> (move_tower (n-1) a c b) @ (move_tower 1 a b c) @ (move_tower (n-1) b a c);; === [[리스프|Lisp]] === (defun hanoitowers (disc src aux dst) (cond ((> disc 0) (hanoitowers (- disc 1) src dst aux) (princ (list "Move" disc "from" src "to" dst)) (hanoitowers (- disc 1) aux src dst)))) === [[파스칼(프로그래밍 언어)|Pascal]] === {{{#!syntax Pascal procedure Hanoi(n: integer; from, dest, by: char); Begin if (n=1) then writeln('Move the plate from ', from, ' to ', dest) else begin Hanoi(n-1, from, by, dest); Hanoi(1, from, dest, by); Hanoi(n-1, by, dest, from); end; End; }}} === [[C(프로그래밍 언어)|C]] === {{{#!syntax c #include void HanoiTower(int numOfDisks, char from, char by, char to) { if (numOfDisks == 1) { printf("원판 1을 %c 에서 %c 로 이동\n", from, to); } else { HanoiTower(numOfDisks - 1, from, to, by); printf("원판 %d을(를) %c 에서 %c로 이동", numOfDisks, from, to); HanoiTower(numOfDisks - 1, by, from, to); } } int main() { HanoiTower(3, 'A', 'B', 'C'); } }}} === [[C(프로그래밍 언어)|C++]] === {{{#!syntax cpp #include using namespace std; void move(int from, int to) { cout << from << " -> " << to << '\n'; } void hanoi(int n, int from, int by, int to) { if(n == 0) return; hanoi(n - 1, from, to, by); move(from, to); hanoi(n - 1, by, from, to); } }}} === [[파이썬]] === {{{#!syntax python def hanoi(number_of_disks_to_move, from_, to_, via_): if number_of_disks_to_move == 1: print(from_, "->", to_) else: hanoi(number_of_disks_to_move-1, from_, via_, to_) print(from_, "->", to_) hanoi(number_of_disks_to_move-1, via_, to_, from_) }}} === [[Visual Prolog]] === class hanoi predicates hanoi : (unsigned N). end class hanoi implement hanoi domains pole = string. clauses hanoi(N) :- move(N, "left", "centre", "right"). class predicates move : (unsigned N, pole A, pole B, pole C). clauses move(0, _, _, _) :- !. move(N, A, B, C) :- move(N-1, A, C, B), stdio::writef("move a disc from % pole to the % pole\n", A, C), move(N-1, B, A, C). end implement hanoi goal console::init(), hanoi::hanoi(4). === [[스위프트(프로그래밍 언어)|Swift]] === import Foundation func hanoi(_ n: Int, from a: Int, to b: Int, by c: Int) { if n==1 { print("Move 1 from \(a) to \(b)") } else { hanoi(n-1, from: a, to: b, by: c) print("Move \(n) from\(a) to\(b)") hanoi(n-1, from: c, to: b, by: a) } } [youtube(FYCGV6F1NuY)] 재귀를 사용하지 않는 경우의 알고리즘은 다음과 같다. 원반의 총 개수를 [math(n)]이라 할 때 원반의 이동 회수는 위에서 언급한 대로 [math(2^n-1)]번이 되며, 각 회차를 [math(x)]라 할 때(1부터 [math(2^n-1)]까지) [math(x)]를 2진수로 표현하여 1이 들어가는 최저 자리수에 해당하는 원반을 왼쪽 또는 오른쪽으로 움직이면 된다. 3회차때는 11이므로 맨위의 1번 원반이, 16회차때는 1000의 4번 원반이 이동한다. 예를 들어 원반이 3개라면 1, 2, 3, 4, 5, 6, 7회차에 1번, 2번, 1번, 3번, 1번, 2번, 1번 이동하면 완성된다. 이 때 위에서부터 홀수번째의 원반이 왼쪽으로 이동(시프트, 더이상 왼쪽에 막대가 없다면 맨 오른쪽으로 이동)하면 짝수번째는 오른쪽으로 이동(마찬가지로 오른쪽 끝에서 오른쪽으로 가야 할 경우 왼쪽 끝으로 이동)하면 실수 없이 최소한으로만 움직일 수 있다. 이때 맨 위의 원반이 왼쪽과 오른쪽 가운데 어느 쪽으로 시프트하느냐에 따라 탑이 어느 막대로 움직이는가가 달라진다. 맨 위의 그림처럼 왼쪽 막대의 4개의 원반에 첫 원반이 오른쪽으로 간다면 마지막엔 오른쪽 막대에 정렬되며, 첫 원반이 왼쪽으로 가면 중앙 막대에 정렬된다. 퍼즐을 풀 때, 원반의 개수가 짝수라면 첫째 원반을 이동시킬 막대와는 다른 막대로 이동시켜야 한다. 홀수는 반대. == 기타 == [[혹성탈출: 진화의 시작]] 초반부에서 주인공 [[시저(혹성탈출 시리즈)#s-2|시저]]의 어미 [[밝은 눈]]이 이걸 지능 테스트용으로 하는데, 무척 빨리 완성하는 모습을 볼 수 있다. [[키란디아의 전설]] 2편 마지막에도 이 게임을 응용한 퍼즐이 등장한다. 김정훈이 출연한 일본 수학퀴즈 프로그램에서는 하노이의 탑을 변형한 문제를 냈는데, 왼쪽, 오른쪽에 있는 5개의 원반을 가운데로 모두 옮기는 데 최소 몇 번 움직여야 하느냐하는 문제. 답은 96번. 그 외에도 많은 변형이 고안되어 있다. [[매스 이펙트]]에서도 퍼즐로 등장한다. [[레이튼 시리즈]]에서는 단골로 나오는 문제 유형이다. [[유희왕 VRAINS]]의 악역 조직 [[하노이의 기사]]는 여기에서 이름을 따왔는데, 3화의 수업장면에서 이 퍼즐을 설명하는 것으로 나왔다. 또한 29화에서 [[리볼버(유희왕)]]의 독백으로 다시 언급되며, 작중에서는 방대한 양의 데이터를 원반으로 흡수한 뒤 이를 단번에 출력해 네트워크 전체를 파괴하는 EMP 병기로 등장했다. 이후 2기에서는 무기 대신 스캔 프로그램을 설치하여 라이트닝의 은신처인 미러 링크 브레인즈 서버를 찾아낸다. [[대항해시대 3]]에 나오는 미니게임 중 하나로 등장한다. [[스텔라리스/NPC|스텔라리스의 수호자들]] 중 수수께끼의 요새 이벤트를 시작할 시 볼 수 있는 퍼즐이다. "기둥 세 개가 있고 그 중 하나에는 고리 세 개가 크기 순서대로 쌓여있습니다." 정답은 "다른 기둥에 고리들을 재배열한다"로, 상술한 퍼즐의 규칙과 일치한다. [[원신]]의 [[파루잔]] 캐릭터 초대 이벤트에서 등장. 아이들에게 장치학에 대해 조기 교육을 시킬 수 있는 목적의 장난감을 개발하기 위해 파루잔 본인이 고안한 것으로 나온다. 파루잔이 7개의 원반을 옮기는 데 최소 몇 번 움직여야 하는지도 물어본다. 정답은 [math( 2^7 - 1 = 127)]번. 물론 [[Landmark 72|실제 하노이에 위치한 타워]]와는 관련이 없다. [[분류:장난감]][[분류:퍼즐]]저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기