알고리즘을 통해 문제를 해결해 봅시다.

□ 생각열기

인도 바라나시에는 세상의 종말에 관한 전설이 내려옵니다.

바라나시의 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다.

바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워놓았는데 이 원 판을 규칙에 따라 모두 다른 바늘로 옮기면 탑이 무너지고

세상은 종말을 맞이하게 됩니다.

□ 활동1 - 하노이의 탑 규칙 알기

아래 규칙을 잘 읽고, 이해해봅시다.

□활동2 - 하노이의 탑 문제 해결 방법 알기

아래 플레이 버튼을 눌러 하노이의 탑 문제를 해결해봅시다.

※ 가장 큰 원판을 목표 바늘에 놓기 위해서는 다른 모든 원판을 가운데 바늘로 옮겨야 합니다.

이를 위해 가장 작은 원판 - 다음 작은 원판 - 가장 작은 원판 - 다음 작은 원판 - 가장 작은 원판... 순으로 반복해서 옮깁니다.

□활동3

원하는 단계의 하노이의 탑 문제를 해결해봅시다.

(두 번째, 세 번째 바늘 중 어느 곳에 옮겨도 성공입니다.)

□ 정리 활동

하노이의 탑 전설에 따르면 64개의 원판을 모두 옮기면 세상의 종말이 온다고 합니다.

몇 번을 옮겨야 64개의 원판을 모두 옮길 수 있을까요?

※ 도움주신 선생님 : 대구다사초 정현재, 대구유가초 김진수, 전곡초 한의표