하노이탑 공식 정리

1)하노이탑 퍼즐의 게임 규칙

 

목표: 한 기둥에 있는 원판들을 다른 기둥 두개 중 한 쪽으로 옮기는 것

규칙: 원판은 한번에 한개만 옮길 수 있다.

      작은 원판 위에 그 원판보다 큰 원판이 있으면 안된다

 2)원판의 이동횟수 : 규칙알아보기

 -원판의 개수에 따른 이동 횟수알아보기

             1개 : 1번
             2개 : 3번
             3개 : 7번
             4개 : 15개
                    .
                    .
                    .

 일열로 나열해보면  1, 3, 7, 15...

 

>  첫번 째 규칙! 

 1.대 충 보면, 원판이 한개가 더 적을 때의 이동회수에 2를 곱하고 1을 더했다는 것을 알 수 있죠?
 이 것을 보기 좋게 표현 하는 방법이 있답니다.

 

 => 바로,    P(n-1)x2 +1

Pn의 의미는 무엇일까요?

P1은 1을 뜻하고, P2는 3을 뜻한답니다. P3는 7을 뜻하고, P4는 15를 의미한답니다~

즉, n은 원판은 개수이고, Pn은 n개의 원판의 개수에 따른 이동 횟수 이지요.

그리고, 1은 n에서 빼주는 것입니다. Pn을 하고 1을 빼주는 걸로 착각하지 마시길..!

 

 2.그래도 이해가 안 가는 분들을 위해 그림으로 설명을 다시 드리지요!

 1)  자 이상태는 아무 일도 일어나지 않은 보통 하노이탑입니다.

 

 

 

 2) 이렇게 가장 아래의 원판만 제외하고 위의 원판들을 모두 다른 기둥으로 옮겼습니다.

그럼 이 때의 이동횟수가+ P(n-1)이 되는 겁니다

 

 

 

 

 3)가장 큰 원판을 다른 원판으로 옮기면? 이동횟수가 1이 증가 하겠지요

 즉, 이 때 이동횟수가 +1이 되는 거예요

 

 

 

 

4)나머지 원판들을 큰 원판 위로 옮기면 이동횟수는 어떻게 될까요? 이동횟수는P(n-1)이 됩니다 ㅎㅎ

지금까지 거쳤던 3가지 과정의 이동회수를 더해서 정리해주면

 

2xP(n-1)+1 이 됩니다.

말로 생각하면, 원판의 개수가 지금보다 하나 더 적었을 때의 이동횟수에 2를 곱하고 1을 더했다는 것이지요.

 

 

 >  두번 째 규칙! 

   1,    3,    7,    15,    31 ...   이 수열의 이름은? 바로 계차 수열이랍니다.

      +2   +4   +8     +16


 P(n) = 2 P(n-1) + 1
 

 을 추측할 수 있다.  위와 같은 인접한 항과의 관계식을 우리는 점화식

(recurrence formula) 라고 한다.  [이에 관하여 우리는 다음에

자세히 학습하도록 한다.

그러면 위 점화식에 차례로 대입하여 알아보면

P(1) = 1 P(2) = 2 P(1) + 1 = 2 + 1 = 3 P(3) = 2 P(2) + 1 = 2 x 3 + 1 = 4 + 2 + 1 = 7 P(4) = 2 P(3) + 1 = 2 x 7 + 1 = 8 + 4 + 2 + 1        = 15 ..........

 

등비수열의 합 공식을 이용하면, 일반적으로

 

출저:http://blog.naver.com/earth_lover?Redirect=Log&logNo=150093975692