情報科学序論

2013年度
プログラミングⅠ
~ アルゴリズム ~
担当教員: 幸山 直人
2013年度 プログラミングⅠ
ハノイの塔(ルール)
一度に1枚の円盤しか動かせない
 小さい円盤の上に大きい円盤を重ねてはなら
ない

2013年度 プログラミングⅠ
ハノイの塔(再帰的解法)レベル2
A
B
C
A
STEP 1
B
STEP 3
A
B
STEP 2
C
C
2013年度 プログラミングⅠ
ハノイの塔(再帰的解法)レベル2
A
B
C
A
C’
A
C
B’
B’
STEP 1
B
C’
2013年度 プログラミングⅠ
ハノイの塔(再帰的手法)レベル2
A
B
C
A
STEP 1
B
STEP 3
A
B
STEP 2
C
C
2013年度 プログラミングⅠ
ハノイの塔(再帰的解法)レベル2
A
B
C
A
STEP 1
B
STEP 3
A
B
STEP 2
C
C
2013年度 プログラミングⅠ
ハノイの塔(再帰的解法)レベル2
A
B
C
B’
A’
C
A‘
B
A
B’
C
STEP 3
2013年度 プログラミングⅠ
ハノイの塔(再帰的解法)レベル5
A’’
B’’
STEP 1
C’’
A’’
A’’
B’’
STEP 2
C’’
B’’
STEP 3
C’’
2013年度 プログラミングⅠ
ハノイの塔(再帰的解法)全体
レベル1(n=5)
レベル2(n=4)
レベル3(n=3)
レベル4(n=2)
レベル5(n=1)
2013年度 プログラミングⅠ
参考:ハノイの塔(直接的解法)
A
偶数の円盤
B
C
奇数の円盤