[Aizu Online Judge]全探索 (ALDS1_5_A: Exhausive Search)
全探索
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の6章2節では、全探索のアルゴリズムについてでした。
6章では、再帰・分割統治法を取り扱います。プログラムで再帰といえば、階乗を求めるプログラムが思い浮かびます。
分割統治は、問題の部分問題に分割して解くというものです。例えば、長さnの数値配列が与えられたとき、最大値を見つけよという問題があるとします。このとき、配列を二つに分け、前半の最大値を後半の最大値を比較することで、全体の最大値を求めることが分割統治法に当たります。
ALDS1_5_A: Exhausive Search
pp. 142では全探索についての問題が与えられます。問題は下のサイトから見ることができます。
全探索 | アルゴリズムとデータ構造 | Aizu Online Judge
この問題を解く前に、長さnのビット列を全て列挙することを考えます。長さがnなので、 通りのビット列が存在します。これは、再帰関数を使うことで列挙することができます。
ビット列を列挙するコード
public class Test { public static int []S = new int[3]; public static int n; public static int k; public static void main(String[] args) { n = 3; for(int i = 0; i < n; i++) { S[i] = 0; } rec(0); } public static void rec(int k) { if(k == n) { disp(S); return; } rec(k + 1); S[k] = 1; rec(k + 1); S[k] = 0; } public static void disp(int []A) { for(int i = 0; i < A.length - 1; i++) { System.out.print(A[i] + ", "); } System.out.println(A[A.length -1]); } }
解答
import java.util.Scanner; public class ALDS1_5_A { public static int n; public static int []A = new int[50]; public static void main(String[] args) { Scanner scan = new Scanner(System.in); n = scan.nextInt(); for(int i = 0; i < n; i++) { A[i] = scan.nextInt(); } int q = scan.nextInt(); for(int i = 0; i < q; i++) { int m = scan.nextInt(); if(isSolve(0, m)) { System.out.println("yes"); }else { System.out.println("no"); } } scan.close(); } public static boolean isSolve(int i, int m) { if(m == 0) return true; if(i >= n) return false; boolean res = isSolve(i + 1, m) || isSolve(i + 1, m - A[i]); return res; } }
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/01/30
- メディア: Kindle版
- この商品を含むブログを見る