情報科学&情報科学演習

2014年度
プログラミングⅡ
~定番プログラム(1) ~
担当教員: 幸山 直人
2014年度 プログラミングⅡ
ハノイの塔(ルール)
一度に1枚の円盤しか動かせない
 小さい円盤の上に大きい円盤を重ねてはなら
ない

2014年度 プログラミングⅡ
ハノイの塔(再帰的解法)レベル0
4枚の場合に帰着
1番下の円盤を動かす
4枚の場合に帰着
2014年度 プログラミングⅡ
ハノイの塔(再帰的解法)レベル1
A
B
C
A
STEP 1
B
STEP 3
A
B
STEP 2
C
C
2014年度 プログラミングⅡ
ハノイの塔(再帰的解法)レベル1
A
B
C
A
C’
A
C
B’
B’
STEP 1
B
C’
2014年度 プログラミングⅡ
ハノイの塔(再帰的手法)レベル1
A
B
C
A
STEP 1
B
STEP 3
A
B
STEP 2
C
C
2014年度 プログラミングⅡ
ハノイの塔(再帰的解法)レベル1
A
B
C
A
STEP 1
B
STEP 3
A
B
STEP 2
C
C
2014年度 プログラミングⅡ
ハノイの塔(再帰的解法)レベル1
A
B
C
B’
A’
C
A‘
B
A
B’
C
STEP 3
2014年度 プログラミングⅡ
ハノイの塔(再帰的解法)レベル5
A’’
B’’
STEP 1
C’’
A’’
A’’
B’’
STEP 2
C’’
B’’
STEP 3
C’’
2014年度 プログラミングⅡ
ハノイの塔(再帰的解法)全体
レベル0
レベル1(n=4)
レベル2(n=3)
レベル3(n=2)
レベル4(n=1)
*4枚の場合(5枚の場合はもう一段増える)