新らしくなった基本情報 科目 B 20問バージョン アルゴリズムとプログラミング サンプル問題13をJavaにしてみました
山崎講師2023 年 4 月からIPA （独立行政法人情報処理推進機構）の基本情報技術者試験の制度が変更されました。
ここでは、「基本情報技術者試験 科目 B のサンプル問題20問バージョン」の中から、アルゴリズムとプログラミングの問題を取り上げ、Javaのソースコードを示します。
新人エンジニア研修に参加されている皆様の参考になれば幸いです。
【Javaプログラム】
import java.util.Arrays;
public class Q14 {
static double findRank(double[] sortedData, double p) {
int i = (int) Math.ceil(p * (sortedData.length - 1));
return sortedData[i];
}
static double[] summarize(double[] sortedData) {
double[] rankData = new double[5];
double[] p = { 0, 0.25, 0.5, 0.75, 1 };
for (int i = 0; i < p.length; i++) {
rankData[i] = findRank(sortedData, p[i]);
}
return rankData;
}
//以下はテスト
public static void main(String[] args) {
double[] data = { 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1 };
double[] summary = summarize(data);
System.out.println(Arrays.toString(summary));
}
}【結果】
| （無限ループになります） |
【プログラムの解説】
このJavaプログラムは、バイナリサーチ（二分探索）アルゴリズムを実装しています。ただし、プログラムにはバグがあります。バグの原因は、以下の通りです。
バグの原因：
配列 data の最後の要素が探索対象の値 target と一致しない場合、正しい結果が得られない可能性があるため、検索範囲の下限を middle + 1 にする必要があります。
しかし、現在のプログラムでは、検索範囲の下限が middle になっています。
これにより、探索対象の値が最後の要素にある場合、middle の値が返されないため、不正確な結果が返されます。
正しい修正方法：
if (data[middle] < target) のブロック内の low の値を middle + 1 に、if (data[middle] > target) のブロック内の high の値を middle + 1修正します。
これにより、検索範囲の下限を正しく設定し、正しい結果が得られるようになります。
以下は修正後のプログラムです。
public class Q13_2 {
public static void main(String[] args) {
int[] data = { 0, 30, 60 };
System.out.println(search(data, 60));
}
public static int search(int[] data, int target) {
int low = 0;
int high = data.length - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (data[middle] < target) {
low = middle + 1;//修正箇所①
} else if (data[middle] > target) {
high = middle - 1;//修正箇所②
} else {
return middle;
}
}
return -1;
}
}