新らしくなった基本情報 科目 B 20問バージョン アルゴリズムとプログラミング サンプル問題13をJavaにしてみました

2023年4月1日 最終更新日時 : 2024年6月25日 山崎講師山崎講師

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;
    }
}

投稿者プロフィール

山崎講師
山崎講師代表取締役
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。
対象読者
新入社員
前の記事
新らしくなった基本情報 科目 B 20問バージョン アルゴリズムとプログラミング サンプル問題12をJavaにしてみました
2023年4月1日
次の記事
新らしくなった基本情報 科目 B 20問バージョン アルゴリズムとプログラミング サンプル問題14をJavaにしてみました
2023年4月1日