반응형
하노이의 탑 점화식 유도
하노이의 탑에서 n개의 원판을 옮기는 데 필요한 최소 이동횟수를 a(n)이라 할 때 점화식은 아래와 같다.
점화식
a(n) = 2a(n-1) + 1 (n ≥ 2)
a(1) = 1 (초항)
점화식 유도 과정
n개의 원판을 한 막대에서 다른 막대로 옮기는 과정을 세 단계로 나눌 수 있다.
- 상위 n-1개의 원판을 보조 막대로 옮기기 a(n-1)회
- 가장 큰 원판을 목표 막대로 옮기기 1회
- 보조 막대의 n-1개 원판을 목표 막대로 옮기기 a(n-1)회
총 이동횟수는 아래와 같다.
a(n) = a(n-1) + 1 + a(n-1) = 2a(n-1) + 1
일반항 유도
점화식을 풀면 일반항을 얻을 수 있다.
a(n) = 2ⁿ - 1
수학적으로 증명하는 과정
초항: a(1) = 1 = 2¹ - 1
가정: a(k) = 2ᵏ - 1
증명: a(k+1) = 2a(k) + 1 = 2(2ᵏ - 1) + 1 = 2ᵏ⁺¹ - 2 + 1 = 2ᵏ⁺¹ - 1
수학적 귀납법에 따라 모든 자연수 n에 대해 a(n) = 2ⁿ - 1임을 알 수 있다.
반응형