= 횟수 =
n개를 옮기는 횟수를 a(n) 이라 하면,
 a(1) = 1
 a(n) = a(n-1) + 1 + a(n-1) = 2*a(n-1) + 1

n-1개를 옮기고, 밑판 1개를 옮기고, 다시 n-1개를 옮겨야 하기 때문.

위 [[점화식,recurrence_relation]]을 풀면, 일반항은
 $a(n)=2^{n}-1$
이 나온다. ([[메르센_수,Mersenne_number]])

= jeff e. =
{{{
Hanoi(n, src, dst, tmp):
  if n > 0
    Hanoi(n - 1, src, tmp, dst)
    move disk n from src to dst
    Hanoi(n - 1, tmp, dst, src)
}}}
$T(n)$ 을 $n$ 개 디스크를 옮기는 데 필요한 횟수라 하면, (즉 알고리즘의 실행시간)
 $T(0)=0$
 $T(n)=2T(n-1)+1$ for any $n\ge 1$
몇 개 써 보면 다음을 쉽게 예상 가능
 $T(n)=2^n-1$
(Algorithms, Jeff Erickson p26 Fig 1.4)

= tmp links ko =
컴퓨터 개론 https://terms.naver.com/entry.naver?docId=2270443&cid=51173&categoryId=51173
https://terms.naver.com/entry.naver?docId=5570717&cid=60205&categoryId=60205 365일 수학: 하노이의 탑과 시에르핀스키 삼각형
https://johngrib.github.io/wiki/tower-of-hanoi/

= Ref. =
[[WpKo:하노이의_탑]]
[[WpEn:Tower_of_Hanoi]]
http://mathworld.wolfram.com/TowerofHanoi.html
https://everything2.com/title/Tower+of+Hanoi

Up: [[분할정복,divide_and_conquer]]