線形探索法の練習

やったこと概要

基本情報処理技術者試験のアルゴリズムを自己流で練習として書いてみました。

他のアルゴリズムでも使う用の共通部品

2分探索法などの練習でも流用できるように作ったクラス。

探索結果をプリントするクラス。

MessagePrinter.java

/**
 * 探索結果のメッセージをプリントするクラス
 * 
 * @author hatena
 *
 */
import java.util.List;

public class MessagePrinter {

    public void printFoundMessages(int targetNumber, List<Integer> targetList) {
        System.out.println("リストの中に探索対象の数" + targetNumber + "が存在しました。");
        System.out.println("探索対象リストは" + targetList + "でした。");
        System.out.println("探索対象の数のインデックスは" + targetList.indexOf(targetNumber) + "です。");
    }

    public void printNotFoundMessages(int targetNumber, List<Integer> targetList) {
        System.out.println("リストの中に探索対象の数" + targetNumber + "は存在しませんでした。");
        System.out.println("探索対象のリストは" + targetList + "でした。");
    }

}

ランダムな整数のリストを作るクラス。

java.util.Randomクラスに指定範囲のIntStreamを返すints()メソッドがありました。
乱数に偏りがあるような気がする。。。

RandomListCreator.java

import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import lombok.AllArgsConstructor;
/**
 * ランダムな正の整数のリストを作成するクラス。
 *
 * @author hatena
 *
 */
@AllArgsConstructor
public class RandomListCreator {

    public int lengthOfList;
    public int maximumNumber;//ex:50を指定したら生成されるリストは50も含む。

    /**
     * 並び替えされていない指定長さの整数リストを返すメソッド。
     *
     *
     */
    public List<Integer> createRandUnorderdList() {

        // 乱数生成用クラス
        Random rand = new Random();

      //@formatter:off
        List<Integer> unorderdRandlist =
                rand
                .ints(this.lengthOfList, 0, this.maximumNumber + 1)
                .boxed()
                .collect(Collectors.toList());
      //@formatter:on

        return unorderdRandlist;
    }

}

線形探索法メイン部分

単純に先頭から合致する数字がないか見ていく。

線形探索法機能を備えたクラス

SeqSearch.java

import java.util.List;
import lombok.AllArgsConstructor;
import lombok.Data;

/**
 * 線形探索法を行うクラス（拡張for文なので番兵の出番なし。）
 *
 * @author hatena
 */
@Data
@AllArgsConstructor
public class SeqSearch {

    private List<Integer> targetList;

    /**
     * 線形探索法本体のメソッド。先頭から順番に探索。
     *
     * @return 一致したインデックス。一致しなかったら-1が返却。
     *
     */
    public int findTargetNum(int targetNumber) {

        // リスト先頭から順に一致するか確認。
        for (int num : this.targetList) {

            // ターゲットの数字がリストに含まれていたらインデックス番号を返却。
            if (num == targetNumber) {
                return this.targetList.indexOf(targetNumber);
            }
        }
        // 最後まで一致しなかった場合。
        return -1;
    }
}

線形探索法を実行するメインのクラス

MainSeq.java

import java.util.List;
import java.util.Scanner;
import common.MessagePrinter;
import common.RandomListCreator;
import seqsearch.SeqSearch;

/**
 * 2分探索法実行メインクラス
 *
 * @author hatena
 *
 */
public class MainSeq {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        // ランダムなリスト作成に必要な情報（長さ、リスト内の最大数）をユーザーに入力させる
        System.out.print("リストの長さを正の整数で入力：");
        int lengthOfList = scanner.nextInt();
        System.out.print("リストに含める最大の数を入力：");
        int maximumNumber = scanner.nextInt();


        // ランダムなリストを作成
        RandomListCreator listCreator = new RandomListCreator(lengthOfList, maximumNumber);
        List<Integer> targetList = listCreator.createRandUnorderdList();
        System.out.println("ランダムな数のリストを作成しました。");

        // 探索したい数を標準入力する
        System.out.print("線形探索したい数を入力:");
        int targetNumber = scanner.nextInt();
        System.out.println("このリストの中に" + targetNumber + "があるか線形探索します。");

        // 線形探索本体のクラスに、リストと探索対象を渡す。
        SeqSearch seqSearch = new SeqSearch(targetList);

        // 結果メッセージ表示用クラスインスタンス化
        MessagePrinter messagePrinter = new MessagePrinter();

        // リストに該当すれば0以上の整数が返り、結果をプリント
        if (seqSearch.findTargetNum(targetNumber) >= 0) {
            messagePrinter.printFoundMessages(targetNumber, seqSearch.getTargetList());
        } else {
            messagePrinter.printNotFoundMessages(targetNumber, seqSearch.getTargetList());
        }

        scanner.close();

    }

}

結果例

■ リストにターゲットの数字が存在したとき

リストの長さを正の整数で入力：10
リストに含める最大の数を入力：15
ランダムな数のリストを作成しました。
線形探索したい数を入力:9
このリストの中に9があるか線形探索します。
リストの中に探索対象の数9が存在しました。
探索対象リストは[0, 14, 14, 9, 6, 0, 4, 7, 15, 7]でした。
探索対象の数のインデックスは3です。

■ リストにターゲットの数字が存在しなかったとき

リストの長さを正の整数で入力：10
リストに含める最大の数を入力：15
ランダムな数のリストを作成しました。
線形探索したい数を入力してください。:9
このリストの中に9があるか線形探索します。
リストの中に探索対象の数9は存在しませんでした。
探索対象のリストは[11, 7, 10, 10, 14, 4, 11, 3, 11, 1]でした。