목차
1. 퀵정렬 c소스
2. 하노이탑 알고리즘 (말로 설명)
2. 하노이탑 알고리즘 (말로 설명)
본문내용
판을 이동하는 방법 (기둥의 순서를 A, B, C라 한다.)
① n=1, A→C로 이동 (T1=1번)
② n=2, A→B로 1개이동, 남은 한개를 A→C로 이동, B→C로 1개 이동 (T2=3번)
③ n=3, A→B로 n-1개 이동, A→C로 1개 이동, B→C로 (n-1)개 이동
↓ ↓
(2개를 이동하는방법은 ②번 방법이용 ) (T3=3+1+3=7번)
④ n=4, A→B로 n-1 개이동, A→C로 1개 이동, B→C로 (n-1)개 이동
↓ ↓
(3개를 이동하는방법은 ③번 방법이용 재귀적) (T4 =7+1+7=15번)
.
.
따라서..
① {A→B로 (n-1)개 이동} ② {A→C로 1개 이동} ③ {B→C로 (n-1)개 이동}
Tn+1 = ① Tn + ② 1번 + ③ Tn
= 2Tn + 1 = - 1
① n=1, A→C로 이동 (T1=1번)
② n=2, A→B로 1개이동, 남은 한개를 A→C로 이동, B→C로 1개 이동 (T2=3번)
③ n=3, A→B로 n-1개 이동, A→C로 1개 이동, B→C로 (n-1)개 이동
↓ ↓
(2개를 이동하는방법은 ②번 방법이용 ) (T3=3+1+3=7번)
④ n=4, A→B로 n-1 개이동, A→C로 1개 이동, B→C로 (n-1)개 이동
↓ ↓
(3개를 이동하는방법은 ③번 방법이용 재귀적) (T4 =7+1+7=15번)
.
.
따라서..
① {A→B로 (n-1)개 이동} ② {A→C로 1개 이동} ③ {B→C로 (n-1)개 이동}
Tn+1 = ① Tn + ② 1번 + ③ Tn
= 2Tn + 1 = - 1