PowerPoint プレゼンテーション

1
模擬授業
• ハノイの塔と漸化式
• 橋渡しパズルとグラフ
ハノイの塔（問題定義）
2
64枚の純金の盤を3本のダイヤモンドの柱のうちの1本に立てら
れた．盤は大きいものが一番下にあり，上にいくにしたがって
小さくたっていた．
定めによって，昼夜を問わず，盤を別の柱に移し変えている．
僧侶たちは1度に1枚の盤を動かすことができ，また動かした盤
の下に，それよりも小さいものがあってはならない．
3
ハノイの塔
（盤が２枚の場合の移動）
4
ハノイの塔
（盤が２枚の場合の移動）
5
ハノイの塔
（盤が２枚の場合の移動）
6
ハノイの塔
（盤が２枚の場合の移動）
３回で移動終了
7
本当に3回が最小か？
=> 移動を表すグラフ
グラフＧ＝（Ｖ，E）
２
４
１
６
３
５
V: 点(vertex)の集合 V={1,2,3,4,5,6}
E: 枝(edge)の集合 E={(1,2),(1,3),(2,3),(2,4),
(3,4),(3,5),(4,6),(5,6)}
9
ハノイの塔
（盤が3枚の場合の移動）
10
ハノイの塔
（盤が3枚の場合の移動）
11
ハノイの塔
（盤が3枚の場合の移動）
ハノイの塔
（盤が3枚の場合の移動）
12
13
ハノイの塔
（盤が3枚の場合の移動）
14
ハノイの塔
（盤が3枚の場合の移動）
15
ハノイの塔
（盤が3枚の場合の移動）
ハノイの塔
（盤が3枚の場合の移動）
移動回数7回で完了
16
17
本当に7回が最小か？
この部分は
板が２枚の
場合に相当
18
推測しよう！
•
•
•
•
•
0枚の場合は？
1枚の場合は？
2枚の場合は3回
3枚の場合は7回
4枚の場合は？．．．．
• n枚の場合は？
19
2枚移動と3枚移動の関係を考えよう！
２枚移動
1枚移動
２枚移動
20
2枚移動と3枚移動の関係（漸化式）
An :
n 枚のときの移動回数
A3  A2  1  A2  2 A2  1
21
1枚移動と2枚移動の関係を考えよう！
A2  A1  1  A1  2 A1  1
22
漸化式
An : n 枚のときの移動回数
A2  2 A1  1
( n - 1 )枚移動
A3  2 A2  1
・
・
・
An  2 An1  1
1枚移動
( n - 1 )枚移動
23
漸化式から一般項を推測
A1  1
初期条件
A2  2 A1  1
A3  2 A2  1
もしくは
A0  0
A2  3
A3  7
・
・
・
An  2 An1  1
一般項
An  ____
24
一般項の証明（数学的帰納法）
An  2  1を帰納法で証明
n
n  1 のとき A1  2  1  1
1
A1  2  1, A2  2  1,..., An1  2
1
2
n 1
 1 を使って
 An  2  1を示す
n
An  2 An1  1  2  (2
n 1
 1)  1  2  1
n
25
一般項の導出（１）
漸化式 An  2 An1  1
An    2( An1   )
An  2 An1      1
An  1  2( An1  1)
特性方程式   2  1　を解いても良い
26
一般項の導出（2）
Bn  An  1とおく
Bn  2Bn1 , B1  A1  1  ____
Bn  2
An  Bn  1
n
An  2  1
n
A64  2  1  18446744073709551615
64
27
新ルール
3本の柱に順に番号をつけ１,２,３
としたとき，盤の移動を
「柱１と柱３のあいだ」と
「柱２と柱３のあいだ」
に制限する（つまり柱１と柱３へジャンプし
てはいけない）．
さて，柱１から柱３への移動は，何回で終了
するか？
28
推測しよう！
•
•
•
•
0枚の場合は０回
1枚の場合は２回
2枚の場合は？
3枚の場合は？．．．．
• n枚の場合は？
29
ハノイの塔（柱１，３間の移動を禁止した場合のグラフ）
1 2 3
30
川渡りパズル
虎と兎と人参を川の片側から，向こう岸に渡したい．ただし，船は小さいので，一
度に１つのものしか運べない．虎と兎を川の片側に置き去りにすると兎が食べら
れ，兎と人参を川の片側に置き去りにすると人参が食べられてしまうとき，最短
の手数で虎と兎と人参を運ぶにはどのようにしたら良いか？
31
グラフの描画
• 状態：虎，兎，人参が川のどちら側にいる
かを表す．(川を渡ったとき1，それ以外の
とき0のベクトルで表す．）
• 何通りあるか？
• 移動可能な点間に枝を引く．
• 船の移動は無関係とし，状態間の移動を１
回とする．
32
川渡りパズルのグラフ（前半）
(0,0,0)
(0,1,0)
(0,1,1)
(1,1,0)
33
川渡りパズルのグラフ（後半）
34
問題１，２
1. 新ルールにおける漸化式を示し，一般項を求め
よ．
2.
以下は，数学的帰納法によって，すべての猫が同じ色であることを証
明した文章である．どこに間違いがあるのかを説明せよ．
与えられた猫の数に関する数学的帰納法で証明する．もしも猫が1
匹しかいなかった場合，それは自分自身と同色である．次に，全部で
n 匹の猫がいるとして，それらに番号1 からn-1 をつけておく．帰納法
の仮定によって番号1 からn-1の猫は同色であり，同様に番号2 からn
の猫も同色である．しかし2からn-1 の番号の猫たちは，この議論の
途中で色を変えることはできない．したがって，1からn までの猫はす
べて同色でなければならない．こうして頭の猫すべてが同色であるこ
とを証明できた．
35
問題3
• 恐竜と虎と兎と人参を川の片側から，向こう岸に渡したい．
恐竜と虎を川の片側に置き去りにすると虎が食べられ，
虎と兎を川の片側に置き去りにすると兎が食べられ，兎
と人参を川の片側に置き去りにすると人参が食べられて
しまう．ただし，恐竜は人参のにおいが嫌いなので，人参
があると虎を食べない．最短の手数で虎と兎と人参を運
ぶにはどのようにしたら良いか？
• 川のどちら側に恐竜，虎，兎，人参があるかを表した状
態を点とし，状態間が移動可能なとき枝をひくグラフを描
け．
• また，最短手数を答えよ．ただし，手数とは船の移動回
数ではなく，状態間の移動を1手と数えた回数である．

Download Report