하노이탑의 숨겨진 비밀 순서 하노이탑이란? 하노이탑의 역사 하노이탑 단계별 해결 수학적 원리 I (등비수열) 수학적 원리 II (귀납적 추론)코딩(재귀 알고리즘) 하노이탑이란? 수학적 게임 혹은 퍼즐의 일종 브라흐마의 탑(Tower of Brahma) 또는 루카스 타워(Lucas’ Tower)라고 불림 세 개의 막대와 크기가 다른 원반으로 구성 규칙 - 처음에는 모든 원반이 왼쪽 막대 기둥에 작은 것이 위로 향하도록 순차적으로 쌓여 있다. - 원반을 한 번에 한 장씩 다른 기둥으로 이동시킬 수 있지만, 작은 원반 위에 큰 원반을 올릴 수는 없다. 원판의 개수는 게임의 난이도에 따라 조절가능하다. 원판을 옮길 때 시행하는 횟수를 측정해보자. 하노이탑의 역사 하노이탑의 전설-고대 인도 베나레스에 있는 한 사원의 이야기 여기에는 다이아몬드로 이루어진 3개의 기둥이 있고, 그 기둥 중 하나에 가운데에 구멍이 나 기둥에 끼울 수 있게 된 64개의 크기가 각각 다른 황금 원반이 꽂혀 있었다. 황금 원반은 가장 아래쪽에 있는 것이 가장 크고 위로 갈수록 점차 작아져 전체적으로 원추형의 탑을 이루고 있는데, 원반은 한 번에 하나씩만 옮길 수 있으며 작은 원반 위에 그보다 더 큰 원반을 옮길 수 없다. 이 규칙으로 64개의 원반을 처음 놓여 있던 막대에서 다른 막대로 모두 옮기면 탑은 무너지고 세상의 종말이 온다는 전설이 있다. 게임의역사 프랑스 수학자 에두아르 뤼카(Edouard Lucas)가 1883년에 발매한 게임 하노이가 기반 현재 이 문제는 컴퓨터 프로그래밍에서 재귀 알고리즘을 사용하는 문제로 유명하며 재귀 호출의 예제로도 자주 이용 하노이탑 단계별 해결방법 Q: 원반이 1개일 때 다른 막대로 이동할 수 있는 최소 시행횟수는? A: 1회이다. 현재 위치한 막대 이외의다른 막대로 1회만에 이동가능 Q:원반이 2개일 때 다른 막대로 이동할 수 있는 최소 시행횟수는? A: 3회이다. 원반이 3개일 때 다른 막대로 이동할 수 있는 최소 시행횟수는? 7회이다. 원반이 4개일 때 다른 막대로 이동할 수 있는 최소 시행횟수는? 15회이다. 원반이 5개일 때 다른 막대로 이동할 수 있는 최소 시행횟수는? 31회이다. 원반이 6개일 때 다른 막대로 이동할 수 있는 최소 시행횟수는? 63회이다. 하노이탑 속 수학적 원리 I 원반개수와 시행횟수 사이의 관계 등비수열 연속한 두 항사이의 관계가 일정한 비(r)를 이루는 수열 원반의 개수가 n개일 때 등비수열을 활용하여 시행횟수를 수열로 만들었을 때의 일반항은 (n은 자연수)이다. 하노이탑 속 수학적 원리 II 귀납적 추론-현재 위치한 막대 이외의다른 막대로 작은 원반을 먼저 옮기고 더 큰 원반을나머지 한 막대로 옮긴후 다시 작은 원반을 그위에놓는 것을 반복하면 최소회 만에 이동가능 n+1번째 시행과 n번째 시행사이의 관계를 식으로 만들어 보면라 할 수 있고 양변에 1을 더해 다음과 같이 묶을 수 있다. 여기서라 치환하면이며이므로은 첫항이 2이고 공비가 2인 등비수열이다. 따라서 이다. 이다. 파이썬으로 하노이탑 만들기 파이썬으로 코딩하기 I 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_)
C언어로 하노이탑 만들기 직접 해볼까요? 원반의 개수를 하나씩 늘려가며 시행해 봅시다. 등비수열과 항과 항사이의 관계를 이용해 일반항을 유도해 봅시다.