하노이 탑(tower of hanoi)

수학이야기 2011. 4. 28. 15:56
반응형

하노이 탑(The Tower of Hanoi puzzle)은 1883년 프랑스의 수학자 루카스(Edouard Lucas)에 의해 개발되었다. 하노이(베트남의 도시)탑에 관한 문제의 고안자로 Lucas (프랑스인, 1842년) 라는 수학자가 알려져 있다. 1883년 Claus 라는 이름아래 이 하노이 탑 문제가 처음 나타났다.

가만히 살펴보면, Claus 라는 이름은 Lucas 라는 이름의 철자를 뒤바꿔 놓은 것임을 알 수 있다. 그가 쓴 수학게임에 관한 책 Récréations mathématiques (1882-94) 은 고전이 되어 있다.

베나레스에는 세계의 중심이 있고, 그 곳에는 아주 큰 사원이 있다. 이 사원에는 높이 50cm 정도 되는 다이아몬드 막대 3 개가 있다. 그 중 한 막대에는 천지 창조 때에 신이 구멍이 뚫린 64 장의 순금으로 된 원판을 크기가 큰 것부터 아래에 놓이도록 하면서 차례로 쌓아 놓았다. 그리고 신은 승려들에게 밤낮으로 쉬지 않고 한 장씩 원판을 옮겨 빈 다이아몬드 막대 중 어느 곳으로 모두 옮겨 놓도록 명령하였다.

원판은 한 번에 한 개씩 옮겨야 하고, 절대로 작은 원판 위에 큰 원판을 올려 놓을 수 없다. 64개의 원판이 본래의 자리를 떠나 다른 한 막대로 모두 옮겨졌을 때에는 탑과 사원, 승려들은 모두 먼지가 되어 사라지면서 세상의 종말이 온다.

 

풀이1 ::::::::: 계차수열을 써서 구하기

풀이2 ::::::::: 점화식을 써서 구하기

  • 전설처럼 64개를 옮길 때 한 번 옮기는 시간을 1초 걸린다고 하면 얼마나 걸리나?


반응형