全探索

全探索
説明すること
• 再帰
• スタック（深さ優先）
• キュー（幅優先）
再帰とは
• プログラムが自分自身を呼び出すこと
=> 関数が同じ関数を呼び出す
• プログラムが短くなる
（関数プログラミング）
• 呼び出す回数が多いと．．．
階乗
• ０！＝
１
• １！＝
１
• ２！＝
２＊１
• ３！＝
３＊２＊１
• ４！＝
４＊３＊２＊１
• ５！＝
５＊４＊３＊２＊１
．．．
プログラム１
プログラム２
解説
フィボナッチ数列
• ０、１、１、２、３、５、８、１３、２１．．．
• 最初の二項は0,1と定義され、
以後どの項もその前の2つの項の和となっている。
• Ｘ番目の数列の数値を求める関数を作る
解説（ソース除く）
• 再帰を用いるために式を立てる
• F[0] = 0
• F[1] = 1
• F[n+2] = F[n+1] + F[n] (n >= 0)
解説（ソース除く）
• 呼び出しが多くなると、メモリが足りなくなる。
スタックとは
• FILO（先入れ後出し）のデータ構造
• 再帰はスタックと同じデータ構造
深さ優先探索
• スタックで実現できる。
例題（部分和問題）
• 整数 a(1), a(2), … , a(n) が与えられる
• 上記の整数の中からいくつかを選び、
その和をちょうどｋにすることができるか？
• 制約
o 1 <= n <= 20
o -10^8 <= a(i) <= 10^8
o -10^8 <= k <= 10^8
例
• 入力1
ｎ＝４, a = {1,2,4,7}, k = 13
• 出力1
Yes(13 = 2 + 4 + 7)
• 入力2
ｎ＝４, a = {1,2,4,7}, k = 13
• 出力2
No
キューとは
• FIFO（先入れ先出し）のデータ構造
幅優先探索
• キューで実現できる。
例題（迷路の最短路）
• 大きさ N
＊
M の迷路（N,M >= 100）
• 迷路は通路と壁からできている
• １ターンに隣接する上下左右４マスの通路へ移動可能
• スタートからゴールまでの移動に必要な最小のターン数
を求める
• ただしスタートからゴールまで移動可能と仮定する
例
• 入力
o .txtに記載
• 出力
２２
枝切り
• 探索の必要がない場合は、探索をしない

Download Report