하노이의_탑,tower_of_Hanoi

Difference between r1.10 and the current

@@ -27,6 +27,7 @@
= 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:하노이의_탑]]
@@ -35,5 +36,4 @@
https://everything2.com/title/Tower+of+Hanoi

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


[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.