김경환 [회의주의] 04-09-01 13:29

 

  일반항이 2^(n-1) 인 수열의 합인듯 합니다.

제 풀이는 아래와 같습니다.

가장 작은 그릇부터 1번, 2번, 3번,...으로 번호를 매긴다면,

(1) 1개를 옮기는데는 1번을 c에 놓으면 되므로 1회

(2) 2개를 옮기는 데는 1번을 b에 놓고 2번을 c에 놓은후, 1번을 c에 놓으면 되므로 3회,

(3) 3개를 옮기려면 일단 3번이 c에 와야하므로,
    {1번 2번을 b로 옮기는데는 위 (2)에 의해서 3회} + {3번을 c 로 옮기는데 1회} +
    {b에 놓여진 1번 2번을 c로 옮기는데도 역시 3회} = 7회
  ==>b에 놓여진 1번 2번을 c로 옮기는것은 a와c의 위치에 2번 보다 큰 그릇이 있으므로
      옮기는데 아무런 제약이 없는 것으로, 즉 빈 공간으로 생각할 수 있기 때문입니다.

(4) 이러한 방식으로 생각하면
4개를 옮기기 위해서는 일단 3개를 b에 옮기고 4번 그릇을 c에 놓은 다음, b에 있는 3개를 c로 옮기는 것이므로,  7+1+7=15 회 입니다

- 회의주의 -

장원두 [cross] 04-09-01 13:52

 

  네... 동의합니다~ ^^ 따라서 그릇의 개수가 n일 때, 이동횟수는,
2^n-1 이 되겠네요....
2^64-1 = 18446744073709551616 - 1 = 18446744073709551615 회
18446744073709551615 / (60(초) *60(분) *24(시간)*365(일))
 = 584942417355.07203247082699137494 (년)
 =(약) 584,942,417,355 년 정도가 걸리겠네요

김경환 [회의주의] 04-09-01 14:07

 

  장원두님..수열의 합인듯 한데요..
즉, 1+ 2 + 4+ 8+16+ ...+2^63

김경환 [회의주의] 04-09-01 14:17

 

  아..지금 보니 계산은 합으로 하셧네요..죄송합니다..제가 착각을...

장기곤 [kigon72] 04-09-01 15:28

 

  ^^; 넌센스로
가장 큰그릇에 담아서 큰그룻 하나만 옮기세요....금방이네요...

정재현 [b0jjang] 04-09-16 08:04

 

  하노이의 탑 문제랑 비슷하네요 -_-;;

김진수 [stvalentine] 04-10-12 16:41

 

  같은것같은데요-_-