演習問題

解答は

• ホスト: earth.mlab.im.dendai.ac.jp
• ディレクトリ: /home/submit/JavaLib/[今日の日付]/[学籍番号]

に提出しなさい。クラスファイル (〜.class) は提出不要。 提出は gFTP 等の ftp ソフトを用いて行うこと。

問題1

ArrayList の要素を線形探索するプログラムを作成しなさい。 ArrayList の要素は Music クラスのオブジェクトとし、 曲名をキーとして探索するものとする。

同一の曲名を持つ Music オブジェクトが複数存在する場合には、 先頭の 1 つが見つかればよいものとする。

main メソッドのあるクラスのクラス名は SequentialSearch とする。

import java.util.*;

class SequentialSearch {
    public static void main(String[] args) {
        ArrayList<Music> songs = new ArrayList<Music>();
        songs.add(new Music("Life Begins At The Hop", "XTC", 235));
        songs.add(new Music("Burning With Optimism's Flame", "XTC", 264));
        songs.add(new Music("Love At First Sight", "XTC", 190));
        songs.add(new Music("Respectable Street", "XTC", 231));
        songs.add(new Music("No Language In Our Lungs", "XTC", 299));
        songs.add(new Music("This Is Pop", "XTC", 169));
        songs.add(new Music("Scissors Man", "XTC", 289));
        songs.add(new Music("Towers Of London", "XTC", 323));
        songs.add(new Music("Battery Brides", "XTC", 438));
        songs.add(new Music("Living Through Another Cuba", "XTC", 209));
        songs.add(new Music("Generals And Majors", "XTC", 268));
        songs.add(new Music("Making Plans For Nigel", "XTC", 269));
        songs.add(new Music("Are You Receiving Me?", "XTC", 198));

        // 全曲表示
        for(Music music: songs)
            System.out.println(music);
        System.out.println();

        // 曲名をキー入力
        System.out.print("Song name：");
        Scanner stdIn = new Scanner(System.in);
        String songName = stdIn.nextLine();

        // 線形探索
        Music song = sequentialSearch(songs, songName);

        // 結果表示
        if (song == null)
            System.out.println("Not Found: " + songName);
        else
            System.out.println("Found: " + song.getTitle() + " by " + song.getArtist() + ".");
    }

    // 線形探索 (戻り値: 見つかったらそのオブジェクト、見つからなかったら null)
    static Music sequentialSearch(ArrayList<Music> list, String songName) {

        // ここを考える

    }
}


class Music {
    private String title;
    private String artist;
    private int time;        // [秒]

    public Music(String title, String artist, int time) {
        this.title = title;
        this.artist = artist;
        this.time = time;
    }
    public String getTitle() {
        return title;
    }
    public String getArtist() {
        return artist;
    }
    public int getTime() {
        return time;
    }
    public String toString() {
        return title + " by " + artist + " (Time: " + time + " sec)";
    }
}

問題2

問題1のプログラムをもとに、 同一の曲名を持つ Music オブジェクトが複数存在する場合には、 そのすべてを見つけるように変更しなさい。 メソッド sequentialSearch の戻り値を変更すること。

main メソッドのあるクラスのクラス名は SequentialSearchAll とする。

問題3

ArrayList の要素を2分探索するプログラムを作成しなさい。 ArrayList の要素は Music クラスのオブジェクトとし、 曲名をキーとして探索するものとする。

2分探索を行う時点で、リストは曲名の辞書順でソートされているものとする。

同一の曲名を持つ Music オブジェクトが複数存在する場合には、 そのいずれか 1 つが見つかればよいものとする。

main メソッドのあるクラスのクラス名は BinarySearch とする。

import java.util.*;

class BinarySearch {
    public static void main(String[] args) {
        ArrayList<Music> songs = new ArrayList<Music>();
        songs.add(new Music("Life Begins At The Hop", "XTC", 235));
        songs.add(new Music("Burning With Optimism's Flame", "XTC", 264));
        songs.add(new Music("Love At First Sight", "XTC", 190));
        songs.add(new Music("Respectable Street", "XTC", 231));
        songs.add(new Music("No Language In Our Lungs", "XTC", 299));
        songs.add(new Music("This Is Pop", "XTC", 169));
        songs.add(new Music("Scissors Man", "XTC", 289));
        songs.add(new Music("Towers Of London", "XTC", 323));
        songs.add(new Music("Battery Brides", "XTC", 438));
        songs.add(new Music("Living Through Another Cuba", "XTC", 209));
        songs.add(new Music("Generals And Majors", "XTC", 268));
        songs.add(new Music("Making Plans For Nigel", "XTC", 269));
        songs.add(new Music("Are You Receiving Me?", "XTC", 198));

        // ソート
        Collections.sort(songs);

        // 全曲表示
        for(Music music: songs)
            System.out.println(music);
        System.out.println();


        // 曲名をキー入力
        System.out.print("Song name：");
        Scanner stdIn = new Scanner(System.in);
        String songName = stdIn.nextLine();

        // 2分探索
        Music song = binarySearch(songs, songName);

        // 結果表示
        if (song == null)
            System.out.println("Not Found: " + songName);
        else
            System.out.println("Found: " + song.getTitle() + " by " + song.getArtist() + ".");
    }

     // 2分探索 (戻り値: 見つかったらそのオブジェクト、見つからなかったら null)
    static Music binarySearch(ArrayList<Music> list, String songName) {

        // ここを考える

    }

}

class Music implements Comparable<Music> {
    private String title;
    private String artist;
    private int time;        // [秒]

    public Music(String title, String artist, int time) {
        this.title = title;
        this.artist = artist;
	this.time = time;
    }
    public String getTitle() {
        return title;
    }
    public String getArtist() {
        return artist;
    }
    public int getTime() {
	return time;
    }
    public int compareTo(Music another) {
        // titleの辞書順
        return title.compareTo(another.getTitle());
    }
    public String toString() {
        return title + " by " + artist + " (Time: " + time + " sec)";
    }
}