Document

1
アルゴリズムとデータ
構造
第４回演習問題解答
2015/11/04実施
アルゴリズムとデータ構造 2015
問題３の解答
2
問題３３本のくいA,B,Cとn枚の大きさの異なる円盤がある。円盤の中心には穴が
あり、すべてくいAに、最も大きい円盤を底にして大きさの順に積まれている。問題
はすべての円盤をくいBに大きさの順に積み上げるというものである。ただし、円盤
羽一度に一枚ずつしか動かせず、どの円盤もそれより小さい円盤の上に載せては
いけない。次の問いに答えよ。
(a) くいAの一番上の円盤をくいBの一番上
に移動する操作を、A→Bで表すものと
するn=3の場合に関して、上記の問題
の解をこの基本操作を使って表せ。
A
A→B
A
B
C
A→C
A
B
C
B→C
A
B
C
B
C
A→B
A
B
C
C→A
A→B
A
B
C
（解）A→B, A→C, B→C, A→B, C→A, C→B, A→B
2015/11/04実施
A
B
C
C→B
A
B
C
アルゴリズムとデータ構造 2015
問題３の解答(続き)
3
(b)次のようなことを行う手続きをmove(X,Y,Z,k)とする：くいXにある上からk個の
円盤を、くいZを作業領域として使って、くいYに移動する。ただし、move(X,Y,Z,k)
を行う直前の状態では、Xにある上からk個の円盤は、YとZにあるどの円盤よりも
小さいものとする。move(X,Y,Z,k)を実現する再帰的アルゴリズムを示せ。ただし、
k=0のときまで再帰呼び出しされるように設計せよ。
Y
X
..
..
Z
Y
Z
..
..
..
..
move(X,Y,Z,k)
k枚
..
..
X
move(X,Y,Z,k) {
if(k>0) {
move(X,Z,Y,k-1)
X→Y
move(Z,Y,X,k-1)
}
}
2015/11/04実施
X
..
Y
k-1枚
Z
X
Y
Z
move(X,Y,Z,k-1)
..
X
Y
k-1枚
Z
X→Y
..
X
move(Z,Y,X,k-1)
Y
Z
..
アルゴリズムとデータ構造 2015
問題３の解答(続き)
4
(c)入力パラメータをスタックで保持することにより、再帰呼び出しが実現される
とする。move(A,B,C,3)を実行する際に、k=0でmoveが最初に呼び出されたと
きの（入力パラメータの）スタックの状態はどうなっているか答えよ。
スタックの状態
move(X,Y,Z,k) {
if(k>0) {
move(X,Z,Y,k-1)
X→Y
move(Z,Y,X,k-1)
}
}
A,B,C,3
A,C,B,2
A,B,C,3
move(A,B,C,3)
move(A,C,B,2)
move(A,B,C,1)
(答)
A,B,C,1
A,C,B,2
A,B,C,3
move(A,C,B,0)
（補足）実際には局所変数をスタック領域に確保するという実装が効率的である
ため、現在使用中の局所変数もスタックに積まれていると考えることもできる。
よって、以下も正解とする。
A,C,B,0
A,B,C,1
A,C,B,2
A,B,C,3
2015/11/04実施
アルゴリズムとデータ構造 2015
問題３の解答(続き)
5
(d)円盤の枚数nに対し、設問2で設計したアルゴリズムにおける円盤の
移動回数を求めよ。
move(X,Y,Z,k)で実行される円盤の移動の回数をakとおけば、
ak=2ak-1+1
a0=0
が成り立つ。この漸化式より、
an=2an-1+1=22an-1+2+1=・・・=2na0+2n-1+2n-2+・・・+1=2n-1
したがってn枚のとき移動回数は2n-1回。
（補足）高校で習ったように
an+1=2(an-1+1)
と変形し、
an+1=2(an-1+1)=22(an-2+1)=・・・=2n(a0+1)=2n
と計算することもできる。
2015/11/04実施
アルゴリズムとデータ構造 2015
余談
6
１つ増えると手間が約２倍になる他のパズル
チャイニーズリング（九連環）
変形バージョン多数（テンヨーのエレクトロパズルなど）
2015/11/04実施
アルゴリズムとデータ構造 2015

Download Report