中学受験算数に见る动的计画法
?Download as PPTX, PDF?
0 likes?387 views
中学3年生に105分の授業をすることを想定して作成されたスライドです。 アルゴリズム（2020年度）の授業で作成したものです。 https://yatani.jp/teaching/doku.php?id=2020algorithms:start お問い合わせ： https://twitter.com/NaomiatLibrary
 改題)](https://image.slidesharecdn.com/99chugaku-200817132722/85/-76-320.jpg)
中学受験算数に见る动的计画法
- 16. 階段の問題:解法1 ０ ２ ４ ５６ ７ ７ ８ 8 9 10 12段のとき(最初に2段登った場合) 11 11 12 119 12 1210 13 12 13 13 14 13 14 13 14 119 12 1210 13 13 14 ５ ３ 10 11 12 13 13 14
- 17. 階段の問題:解法1 ０ 3 5 67 8 8 9 9 10 11 (とても めんどくさい) 12段のとき(最初に3段登った場合) 12 12 13 1210 13 1311 14 13 14 6 2 1210 13 1311 14 11 12 13 14
- 18. 階段の問題:解法1 ０12段のとき 3 5 7 8 9 10 11 12 12 13 1210 13 1311 14 13 14 66 8 9 1210 13 1311 14 11 12 13 14 ２ ４ ６ ７ 8 9 10 11 11 12 119 12 1210 13 12 13 13 14 13 14 13 14 ５ ７ ８ 119 12 1210 13 13 14 10 11 12 13 13 14 12通り 12 を数えると
- 19. 階段の問題:解法1 ０12段のとき 3 5 7 8 9 10 11 12 12 13 1210 13 1311 14 13 14 66 8 9 1210 13 1311 14 11 12 13 14 ２ ４ ６ ７ 8 9 10 11 11 12 119 12 1210 13 12 13 13 14 13 14 13 14 ５ ７ ８ 119 12 1210 13 13 14 10 11 12 13 13 14 12通り 12 を数えると めんどくさい
- 22. 階段の問題:解法1 何回調べないといけない？ 段数 答え 調べる回数 7 3 17 12 12 73 50 525,456(52万) 3,236,383(323万) 100 670,976,837,021(6709億) 4,132,674,661,507(4兆) 200 1,094,081,998,015,776,5 26,179,329 6,738,660,265,660,308,8 07,737,463 600(東京タワー階段の段 数) 7,734,268,575,229,071,7 58,820,053,174,351,074, 065,809,240,913,542,350 ,861,075,008,313,376,34 1,876 47,636,839,310,365,630, 340,208,491,560,681,036 ,757,140,134,694,391,45 5,799,211,182,744,208,5 99,001 ?
- 23. 階段の問題:解法1 コンピュータは何回調べられる？ コンピュータは一秒に10,000,000(1億回)くらい調べられる 段数 調べる回数 50 3,236,383(323万) 100 4,132,674,661,507(4兆) 200 1,094,081,998,015,776,5 26,179,329 600(東京タワー階段の段 数) 47,636,839,310,365,630, 340,208,491,560,681,036 ,757,140,134,694,391,45 5,799,211,182,744,208,5 99,001 ←これは1秒で調べられる ←これは12時間かかる ←これは21億年かかる ※宇宙が誕生してから 138億年しか経っていない
- 24. 階段の問題:解法1 ０ 3 5 7 8 9 10 11 12 12 13 1210 13 1311 14 13 14 66 8 9 1210 13 1311 14 11 12 13 14 ２ ４ ６ ７ 8 9 10 11 11 12 119 12 1210 13 12 13 13 14 13 14 13 14 ５ ７ ８ 119 12 1210 13 13 14 10 11 12 13 13 14 とか の中身、 全く同じ…？
- 27. 階段の問題:解法2 ←最初は普通に調べていく ０ ２ ４ ６ 8 10 11 12 13 13 14 2本の枝を調べ切った8,10,11段目について、 そこから12段目まで登る登り方の数がわかる 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - - - - - 1 - 1 0 ７ 9５ ３
- 28. 階段の問題:解法2 ０ ２ ４ ６ 8 9 10 11 11 12 13 13 14 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - - - - - 1 - 1 0 先を調べなくても、 この後12段目に登るための 登り方の個数がわかる！ 0通り５ ３ ７
- 29. 階段の問題:解法2 ０ ２ ４ ６ 8 9 10 11 11 12 12 13 13 14 ３ 0通り 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - - - - - 1 1 1 0 ５ ７
- 30. 階段の問題:解法2 ０ ２ ４ ６ 8 10 11 12 13 13 14 ３ ５ 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - - - 2 - 1 1 1 0 9 11 12 0通り ７
- 31. 階段の問題:解法2 ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ ５ 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - - - 2 - 1 1 1 0 9 11 12 0通り 10
- 32. 階段の問題:解法2 ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ ５ 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - - - 2 - 1 1 1 0 9 11 12 0通り 1通り 10 1通り
- 33. 階段の問題:解法2 ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ 9 11 12 0通り 1通り 10 1通り 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - - - 2 2 1 1 1 0 ５
- 34. 階段の問題:解法2 ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ 9 11 12 0通り 1通り 10 1通り 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - 4 - 2 2 1 1 1 0 ５
- 35. 階段の問題:解法2 ５ ７ ８ ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ 9 11 12 0通り 10 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - 4 - 2 2 1 1 1 0 1通り 1通り 1通り 2通り
- 36. 階段の問題:解法2 ５ ７ ８ ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ 9 11 12 0通り 10 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - - - 4 3 2 2 1 1 1 0 1通り 1通り 1通り 2通り
- 37. 階段の問題:解法2 ５ ７ ８ ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ 9 11 12 0通り 10 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - 7 - 4 3 2 2 1 1 1 0 1通り 1通り 1通り 2通り
- 38. 階段の問題:解法2 ５ ７ ８ ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ 9 11 12 0通り 10 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - 7 - 4 3 2 2 1 1 1 0 1通り 1通り 1通り 2通り ０ 3 5 (最初に3段登った場合) 6 2 3通り 2通り
- 39. 階段の問題:解法2 ５ ７ ８ ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ 9 11 12 0通り 10 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 - - 7 5 4 3 3 2 1 1 1 0 1通り 1通り 1通り 2通り ０ 3 5 (最初に3段登った場合) 6 2 3通り 2通り
- 40. 階段の問題:解法2 ５ ７ ８ ０ ２ ４ ６ ７ 8 10 11 9 12 13 13 14 ３ 9 11 12 0通り 10 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 12 - 7 5 4 3 3 2 1 1 1 0 1通り 1通り 1通り 2通り ０ 3 5 6 2 3通り 2通り
- 41. 階段の問題:解法2 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 12 - 7 5 4 3 3 2 1 1 1 0 0段目から12段目までの登り方 →これが答え(12通り)
- 45. 階段の問題:解法2 何回調べないといけない？ 段数 解法1で調べる回数 解法2で調べる回数 7 17 13 12 73 23 50 3,236,383(323万) 99 100 4,132,674,661,507(4兆) 199 200 6,738,660,265,660,308,8 07,737,463 399 600(東京タワー階段の段 数) 47,636,839,310,365,630, 340,208,491,560,681,036 ,757,140,134,694,391,45 5,799,211,182,744,208,5 99,001 1199
- 46. 階段の問題:解法2 何回調べないといけない？ 段数 解法1で調べる回数 解法2で調べる回数 7 17 13 12 73 23 50 3,236,383(323万) 99 100 4,132,674,661,507(4兆) 199 200 6,738,660,265,660,308,8 07,737,463 399 600(東京タワー階段の段 数) 47,636,839,310,365,630, 340,208,491,560,681,036 ,757,140,134,694,391,45 5,799,211,182,744,208,5 99,001 1199 (だいたい)2倍 →段数に比例
- 50. 階段の問題:解法3 解法3:ある段数にいる時… 8段目にいる時、 12段目までの登り方を考える 次に登るのは10段目か11段目 ５ ０ ２ ４ ６ ７ 8 10 11 12 13 13 14 ３ 9 11 12 0通り 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 12 - 7 5 4 3 3 2 1 1 1 0
- 51. 階段の問題:解法3 解法3:ある段数にいる時… 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 12 - 7 5 4 3 3 2 1 1 1 0 ５ ０ ２ ４ ６ ７ 8 10 11 12 13 13 14 ３ 9 11 12 0通り 8段目から12段目に登る登り方 次に11段目に登っ てから12段目まで 登る登り方 次に10段目に登っ てから12段目まで 登る登り方
- 52. 階段の問題:解法3 解法3:ある段数にいる時… 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12段目までの登り方 12 - 7 5 4 3 3 2 1 1 1 0 ５ ０ ２ ４ ６ ７ 8 10 11 12 13 13 14 ３ 9 11 12 0通り 8段目から12段目に登る登り方 次に11段目に登っ てから12段目まで 登る登り方 次に10段目に登っ てから12段目まで 登る登り方
- 53. 階段の問題:解法3 解法3:ある段数にいる時… 現在何段目か … N N+1 N+2 N+3 N+4 N+5 N+6 … 12段目までの登り方 … x+y - x y - - - … N段目から12段目に登る登り方 次にN+3段目に 登ってから12段目 まで登る登り方 次にN+2段目に 登ってから12段目 まで登る登り方 N N+2 N+3 N+4 N+5 N+5 N+6
- 54. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - - - - - - - - - - 1 表を使って考える 12段目から12段目に登る登り方は 「そのまま居る」の1通りとする
- 55. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - - - - - - - - - 0 1 表を使って考える 11段目から12段目に登る登り方は、 次に13段目に登る登り方と次に14段 目に登る登り方になるが、そのよう なものは存在しない。
- 56. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - - - - - - - - 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 57. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - - - - - - - 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 58. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - - - - - - 1 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 59. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - - - - - 2 1 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 60. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - - - - 2 2 1 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 61. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - - - 3 2 2 1 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 62. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - - 4 3 2 2 1 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 63. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - - 5 4 3 2 2 1 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 64. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - - 7 5 4 3 2 2 1 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 65. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 - 9 7 5 4 3 2 2 1 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す
- 66. 階段の問題:解法3 現在何段目か 0 1 2 3 4 5 6 7 8 9 10 11 12 12段目までの登り方 12 9 7 5 4 3 2 2 1 1 1 0 1 表を使って考える N+2段目から12段目までの登り方と N+3段目から12段目までの登り方を 足し合わせて記録することを繰り返す 0段目から12段目までの登り方は 12通り
- 81. ゲームの問題 (1) N=10,M=4の時 0 1 2 3 4 5 6 7 8 9 10 -4 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 試合が行われていないので 「どっちも0勝」の1通りとする
- 82. ゲームの問題 (1) N=10,M=4の時 0 1 2 3 4 5 6 7 8 9 10 -4 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 どちらも勝利していないので、 次の試合が行われるはず Bが勝つ Aが勝つ
- 83. ゲームの問題 (1) N=10,M=4の時 0 1 2 3 4 5 6 7 8 9 10 -4 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 Bが勝つ Aが勝つ
- 84. ゲームの問題 (1) N=10,M=4の時 0 1 2 3 4 5 6 7 8 9 10 -4 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 Bが勝つ Aが勝つ
- 85. ゲームの問題 (1) N=10,M=4の時 0 1 2 3 4 5 6 7 8 9 10 -4 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 -1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 Bが勝つ Aが勝つ
- 86. ゲームの問題 (1) N=10,M=4の時 0 1 2 3 4 5 6 7 8 9 10 -4 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 -1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 (同じように調べる)
- 87. ゲームの問題 (1) N=10,M=4の時 0 1 2 3 4 5 6 7 8 9 10 -4 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 1 0 0 0 0 0 0 0 0 -1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 次の列も同じように進める
- 88. ゲームの問題 (1) N=10,M=4の時 0 1 2 3 4 5 6 7 8 9 10 -4 0 0 0 0 1 0 4 0 14 0 48 -3 0 0 0 1 0 4 0 14 0 48 0 -2 0 0 1 0 4 0 14 0 48 0 164 -1 0 1 0 3 0 10 0 34 0 116 0 0 1 0 2 0 6 0 20 0 68 0 232 1 0 1 0 3 0 10 0 34 0 116 0 2 0 0 1 0 4 0 14 0 48 0 164 3 0 0 0 1 0 4 0 14 0 48 0 4 0 0 0 0 1 0 4 0 14 0 48 全ての列について調べると…
- 89. ゲームの問題 (1) N=10,M=4の時 0 1 2 3 4 5 6 7 8 9 10 -4 0 0 0 0 1 0 4 0 14 0 48 -3 0 0 0 1 0 4 0 14 0 48 0 -2 0 0 1 0 4 0 14 0 48 0 164 -1 0 1 0 3 0 10 0 34 0 116 0 0 1 0 2 0 6 0 20 0 68 0 232 1 0 1 0 3 0 10 0 34 0 116 0 2 0 0 1 0 4 0 14 0 48 0 164 3 0 0 0 1 0 4 0 14 0 48 0 4 0 0 0 0 1 0 4 0 14 0 48 全ての列について調べると… ちょうど10回目にAが勝利する…答え
- 90. ゲームの問題 何回調べないといけない？ ※全部の出し順を調べると、1試合ごとに(Aが勝つ)(Bが勝つ)の 二個の選択肢が分岐するので、調べる数が倍、そのまた倍…に 階段の問題の最初の解法と同じ ?
- 93. おまけ:その他の問題 た し 算は二つの数から一つの数を求める計算で、三つ以上の数をたすときには、二つの数のたし算を くり返していくことになります。例えば 1+2+3や1+2+ 3+4を、カッコを用いて二つの数のたし算で 書き表す方法は、次のようにそれぞれ二通り、五通りあります。 1+(2+3)、(1+2)+3???二通り 1+(2+(3+4))、1+((2+3)+4)、(1+2)+(3+4)、(1+(2+3))+4、((1+2)+3)+4???五通り (注意) 1+(3+2)のように、たす数を並べ替えることは考えません。 このような式を完全式と呼ぶことにします。次のような式は完全式ではありません。 1+2+3、1+(2+3)+4 、(1+2+3)+4 （三つをたしている） 1+2+3+4 (四つをたしている) (1) 1+2+3+4+5 には何通りの完全式がありますか。 (2) 1+2+3+4+5+6には何通りの完全式がありますか。 →1+2+…+Nには何通りの完全式がありますか。 (洛南中学2001年度算数)