본문 바로가기
회원가입 글자크기 화면 확대 화면 축소

체험수학 콘텐츠

하노이탑

작성자 : 융합인재부

등록일 : 2023/11/23

조회수 : 804



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

 

첨부파일 :

자료관리 담당자

  • 담당부서 : 융합인재부
  • 전화번호 : 043-229-1824