하노이 탑의 최단 이동 횟수 알아 보기 제주 북초등학교 6학년 심화반 임 성 찬.

Presentation on theme: "하노이 탑의 최단 이동 횟수 알아 보기 제주 북초등학교 6학년 심화반 임 성 찬."— Presentation transcript:

1 하노이 탑의 최단 이동 횟수 알아 보기 제주 북초등학교 6학년 심화반 임 성 찬

2 목 차 주제 선정 동기 하노이 탑의 전설 하노이 탑의 규칙 하노이 탑 옮겨 보기 기둥이 세 개일 때 최단 횟수로 옮기는 법
기둥이 네 개일 때 최단 횟수로 옮기는 법 하노이 탑의 전설을 푸는 데 걸리는 시간 알아 보기 프로젝트 학습을 마치고 나서

3 1. 주제 선정 동기 내가 하노이 탑을 주제로 삼은 이유는 5학년 때 했던
파스칼의 삼각형과 소마 큐브를 하고 나서 딱딱한 수학 보다는 부드럽고 재미있는 문제 풀이를 해보고 싶었는데, 그 때 마침 하노이 탑의 전설이라는 글을 읽고 하노이 탑을 하기로 결심을 굳혔다.

4 인도의 바라문교라는 종교의 사원에는 다음과 같은 전설이 전해지고 있다고 한다
2. 하노이 탑의 전설 인도의 바라문교라는 종교의 사원에는 다음과 같은 전설이 전해지고 있다고 한다 신이 천지를 창조한 후, 세 개의 기둥을 만들었는데, 한 기둥에는 64개의 원판이 꽂혀 있었고, 모든 원판들이 마지막 기둥으로 옮겨지면 세상의 종말이 온다.

5 3. 하노이 탑의 규칙 이게 바로 하노이 탑! 원판은 한번에 하나만 옮길 수 있다.
작은 원판 위에 큰 원판을 올려 놓을 수 없다. 위에 아무 원판도 없는 원판만 이동 시킬 수 있다. ※ 이러한 조건으로 풀지 않을 경우 하노이 탑을 풀 때 혼란에 걸리게 된다 이게 바로 하노이 탑!

6 4. 하노이 탑 옮겨보기 1. 원판 3개로 해보기 결과 : 7번 하니 세 개 모두 다른 기둥으로 이동 된다.
2. 원판 4개로 해보기 결과 : 여러 번 해본 결과 15번이 가장 최단 횟수다. 3. 원판 5개로 해보기 결과 : 최단 횟수로 31번이 나왔다.

7 5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 ※ 기둥이 세 개이고 원판이 3개 라고 가정했을 때이다. 이게 하노이 탑이라고 하면. 1 2 3 2 3 1

8 5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 1. 1번 원통을 2번 기둥에 놓는다. 1 2 3 2 3 1

9 5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 2. 2번 원통을 3번 기둥에 놓는다 1 2 3 3 1 2

10 5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 3. 1번 원통을 2번 위에 놓는다. 1 2 3 1 3 2

11 5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 4. 3번 원통을 2번 기둥에 놓는다. 1 2 3 1 3 2

12 5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 5. 1번 원통을 1번 기둥에 놓는다. 1 2 3 1 3 2

13 5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 6. 2번 원통을 3번 위에 놓는다. 1 2 3 2 1 3

14 5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 7. 1번 원통을 2번 위에 놓는다. 1 2 3 1 2 3

15 5. 기둥이 세 개일 때 최단 횟수로 옮기는 방법 여기서 알 수 있는 규칙! 홀수는 짝수 위에 놓고 짝수는 홀수 위에 놓는다.
여기서 알 수 있는 규칙! 홀수는 짝수 위에 놓고 짝수는 홀수 위에 놓는다. 1 2 3 1 2 3

16 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 1. 원판이 3개 일 때 결과 : 5번이 최단 횟수로 나왔다. 2. 원판이 4개 일 때 결과 : 9번이 최단 횟수로 나왔다. 3. 원판이 5개 일 때 결과 : 13번이 최단 횟수로 나왔다.

17 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 ※ 아까 보다 기둥이 하나 늘어났다고 가정한 것이다. 기둥이 네 개이고 원통이 4개라고 가정한 것이다. 1 2 3 4 1 2 3 4

18 5. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 1. 1번 원통을 2번 기둥으로 옮긴다. 1 2 3 4 2 3 4 1

19 5. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 2. 2번 원통을 3번 기둥으로 옮긴다. 1 2 3 4 3 4 1 2

20 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 3. 3번 원통을 4번 기둥으로 옮긴다. 1 2 3 4 4 1 2 3

21 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 4. 1번 원통을 2번 원통 위로 옮긴다. 1 2 3 4 1 4 2 3

22 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 5. 4번 원통을 2번 기둥으로 옮긴다. 1 2 3 4 1 4 2 3

23 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 6. 3번 원통을 4번 원통 위로 옮긴다. 1 2 3 4 3 1 4 2

24 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 7. 1번 원통을 4번이나 1번 기둥으로 옮긴다. 1 2 3 4 3 1 4

25 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 8. 2번 원통을 3번 원통 위로 옮긴다. 1 2 3 4 2 3 1 4

26 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 9. 1번 원통을 2번 원통 위로 옮긴다. ※ 그러므로 기둥 네 개는 기둥 3개 보다 빨리 옮길 수 있다. 1 2 3 4 1 2 3 4

27 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 원판의 수를 n이라고 하고 기둥의 개수가 4개일 경우 다음과 같은 패턴이 존재한다는 것을 알아내었다. 원판 수 원판의 이동 (원판의 번호) 원판 이동 횟수 N=1 ① 1번 N=2 1②1 3번 N=3 12③21 5번 N=4 1232④2321 9번 N=5 123214⑤412321 13번 N=6 ⑥ 17번 N=7 ⑦ 25번

28 6. 기둥이 네 개일 때 최단 횟수로 옮기는 방법 결론: 원판의 개수(n) 1 2 3 4 5 6 7 8 9 10 11 12
13 원판 이동 횟수 17 25 33 41 49 65 81 97 이동{n-(n-1)} - 16 원판 이동 횟수의 규칙 n번째와 n-1 번째 원판 이동 횟수의 차는 2의 거듭제곱 꼴이다. 2⁰이 처음 1이고, 2의 제곱이 다음 2번, 2의 2제곱이 그 다음 3번,… 순으로 간다.

29 7. 하노이 탑의 전설을 푸는데 걸리는 시간 알아보기 (응용)
※전설 속에 나오는 하노이 탑의 기둥은 3개 이고 원통이64개 이다. 그러므로 1초에 한 개씩 옮긴다면??? (1)어림잡아 계산 해 보기 ☞ 64개의 원판을 모두 옮기려면 2⁶⁴-1초가 걸리게 된다. 2를 10번 곱한 것이 1024 인데, 이를 약 1000이라고 반올림을 한 후, 2를 60번 곱한 값에 4번 더 곱한(16을 곱한) 값을 구하면 된다. 즉, 2를 60번 곱한 값은 약 1,000,000,000,000,000,000이므로 곱하기 16을 하면 16,000,000,000,000,000,000초 가 된다. 1분은 60초 이고, 1시간은 60분 이므로 3600초, 하루는 24시간 이므로 86400초이다. 또 1년은 365일 이므로 약 3억 초 이다. 그래서 16,000,000,000,000,000,000/300,000,000=5.333×100,000,000,000= 약 5333억 년 이 된다.

30 7. 하노이 탑의 전설을 푸는데 걸리는 시간 알아보기 (응용)
전설 속에 나오는 하노이 탑의 기둥은 3개 이고 원통이64개 이다. 그러므로 1초에 한 개씩 옮긴다면??? (2)계산기를 이용해 보다 정확히 계산하기 ☞2⁶⁴-1=18,446,744,073,709,551,615(초) = 약 584,942,417,355(년) = 약 5849억 (년)이 된다.

31 7. 하노이 탑의 전설을 푸는데 걸리는 시간 알아보기 (응용)
※전설 속에 나오는 하노이 탑의 기둥은 3개 이고 원통이64개 이다. 그러므로 1초에 한 개씩 옮긴다면??? ※ 이 문제를 더 빠르게 해결하는 방법 을 생각해 보기로 하였다. 그 후 나온 생각 3가지가 있다. 0.5초에 원통을 하나씩 옮긴다.(거의 불가능함) 신께서 인간에게 자비를 베풀어 원판의 수를 하나 줄여준다.(시간 ½로 단축됨) 하노이 탑의 기둥을 한 개 늘린다.( 그렇게 되면 5시간 7분 13초면 모든 원통을 다른 곳으로 옮길 수 있다.)