プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 その1
番兵法
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の5.2 線形探索の項目では、番兵法が取り上げられていました。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (7件) を見る
blog.codebook-10000.com を参照すると良いと思います。
問題
会津大学の競技プログラミングのサイトの問題をこの本は使用しているので、そのサイトでジャッジを受けることが出来ます。
探索 1 | アルゴリズムとデータ構造 | Aizu Online Judge
コード
import java.util.Scanner; public class ALDS1_4_A { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int []S = new int[n + 1]; for(int i = 0; i < n; i++) { S[i] = scan.nextInt(); } int q = scan.nextInt(); int []T = new int[q]; for(int i = 0; i < q; i++) { T[i] = scan.nextInt(); } scan.close(); int sum = 0; for(int i = 0; i < q; i++) { if(search(S, n, T[i]) == 1) { sum ++; } } System.out.println(sum); } public static int search(int A[], int n, int key) { int i = 0; A[n] = key; while(A[i] != key) { i ++; } if(i != n) { return 1; } return 0; } }