하노이의_탑,tower_of_Hanoi

[edit]

횟수

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)

[edit]

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)

[edit]

tmp links ko

[edit]

Ref.