하노이탑의 숨겨진 비밀
순서
하노이탑이란?
하노이탑의 역사
하노이탑 단계별 해결
수학적 원리 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언어로 하노이탑 만들기
직접 해볼까요?
원반의 개수를 하나씩 늘려가며 시행해 봅시다.
등비수열과 항과 항사이의 관계를 이용해 일반항을 유도해 봅시다.