演習問題 (中級～上級)

解答は

ホスト名: earth.mlab.im.dendai.ac.jp

ディレクトリ: /home/submit/1I-Computer2/[出題日]/[学籍番号]

に提出しなさい。ソースファイル (～.java) のみを提出。提出は gFTP 等の ftp ソフトを用いて行う。

問題1

int 型の配列を用意し適当な数を複数用意しておく。
(例: int[] a = {15, 9, 12, 10, 6, 8, 16, 5, 13, 14};)

配列に対して次の操作を行うメソッドを書きなさい。

メソッド swap: 配列と入れ替えの対象となる2つの数値を引数にとり、指定した配列の要素同士を入れ替えるメソッド。例えば、上の配列で0番めと2番めの要素を入れ換えると 12, 9, 15, 10, 6,... という内容になる。
メソッド searchMinimum: 配列と検索範囲を引数にとり、配列の指定された範囲内の最小の要素を探すメソッド。このメソッドは、どの番号の要素に最小値があったか、その要素の番号を返すようにすること。例えば、上の配列で3番めから6番めの範囲で最小値を探すと 6の入っている要素の番号「4」となる。

次のようなプログラムを書き、これらのメソッドが正しく動くようにしなさい。プログラム名は SwapAndSearchMinimum としなさい。

class SwapAndSearchMinimum {
      public static void main(String[] args) {
          int[] a = new int[] {15, 9, 12, 10, 6, 8, 16, 5, 13, 14};

          print(a);

          // 0番めと2番めの要素の入れ換え
          swap(a, 0, 2);
          print(a);

          // 3番めから6番めの範囲で最小値を探す
          int minIndex = searchMinimum(a, 3, 6);
          System.out.println("最小値は " + minIndex + " 番目  " +
	                     "最小値は " + a[minIndex]);
      }

      static void print(int[] a) {
          for(int i = 0; i < a.length; i++)
              System.out.print(a[i] + " ");
          System.out.println();
      }


      // メソッド swap とメソッド searchMinimum の内容をここに書く


}

問題2

配列の内容を小さい順に並び替えるプログラムを作成しなさい。並び変えの方針として次のような考え方を用いる。以下のような配列が用意されているとする。

15, 9, 12, 10, 6, 8, 16, 5, 13, 14

まず配列全体から最小の要素を探し出す。この例では5である。最小のものと配列の先頭の内容を入れ替える。

5, 9, 12, 10, 6, 8, 16, 15, 13, 14

次に、配列の1番め(9の入っている場所)から配列の終わりまでの範囲で最小の要素を探し出す。 (結果的にこの値は配列全体から見ると2番めに小さな値である。) この例では6である。この最小のものと配列の1番めを入れ替える。

5, 6, 12, 10, 9, 8, 16, 15, 13, 14

そして、配列の2番め(12の入っている場所)から配列の終わりまでの範囲で最小の要素を探し出す。 (結果的にこの値は配列全体から見ると3番めに小さな値である。) この例では8である。この最小のものと配列の2番めを入れ替える。

5, 6, 8, 10, 9, 12, 16, 15, 13, 14

このような操作を配列の終わりまで繰り返していけば、配列の中身を小さい順に並び替えることができる。

5, 6, 8, 9, 12, 10, 16, 15, 13, 14
5, 6, 8, 9, 10, 12, 16, 15, 13, 14
5, 6, 8, 9, 10, 12, 16, 15, 13, 14
5, 6, 8, 9, 10, 12, 13, 15, 16, 14
5, 6, 8, 9, 10, 12, 13, 14, 16, 15
5, 6, 8, 9, 10, 12, 13, 14, 15, 16

以上の動作をプログラムとして書くと次のようになる。

すべての要素から最小の値を探し、それを配列の先頭と交換する。
先ほどの最小の値を除いた残りの要素から最小の値を探し、それを配列の 1 番目と交換する。
同様に、さらに残りの要素から最小の値を探し、残りの先頭部分に移動する。これを繰り返す。

この考え方に基づき、前の問題で作成したメソッド swap とメソッド searchMinimum を用い、配列を小さい順に並び替えるプログラムを作成しなさい。プログラム名は SelectionSort とする。

問題3

コマンドライン引数に英文を与えると、その内容を否定する文に変換して表示するプログラムを書きなさい。プログラム名は NagativeTalker とする。

実行例は次のとおり。

$ java NegativeTalker This is a pen
This is not a pen.

$ java NegativeTalker I can speak English
I can not speak English.

$ java NegativeTalker I will go to Tokyo
I will not go to Tokyo.

$ java NegativeTalk I like her
I do not like her.

このプログラムの仕掛けは次のとおり。

文中にbe動詞(is, am, are, was, were)が見つかった場合、その後に not を挿入する。
文中に助動詞(can, will, shall, may, must)が見つかった場合、その後に not を挿入する。
上記のどれにも当てはまらない場合、文の1つ目の単語が主語、2つ目の単語が動詞原形と決めてしまって、その前に do not を挿入する。言語処理としては不適切であるが、今回はこれでがまんすることにする。

コマンドライン引数に与えた英文は、プログラムの中では文字列の配列として使うことができる。

This is a pen

という文があると、args[0]="This", args[1]="is", args[2]="a", args[3]="pen" となる。

この配列を引数に取り、内容を否定する英文を返すメソッド negative を作成すること。

注意

文字列同士が等しいか比較するには、equals メソッドを用い、次のように書く。

String str1 = "This";
String str2 = "This";

if (str1.equals(str2)) {
    str1とstr2が等しいときの処理をここに書く
}

if (str1.equals("This")) {
    str1の内容が "This" であったときの処理をここに書く
}

if (str1 == str2) // ←誤り
if (str1 == "This") // ←誤り

また、strが配列であれば次のようになる。

String str[] = new String[2];
str[0] = "This";
str[1] = "This";
// 上の 3 行は String str[] = {"This", "This"}; と書いても良い

if (str[0].equals(str[1])) {
    str[0]とstr[1]が等しいときの処理をここに書く
}

文字列の内容の比較のために「str1 == str2」という書き方はできない。 (ただしコンパイルエラーにならないので注意)

プログラムの大枠は次のとおり。

class NegativeTalker {
    public static void main(String[] args) {
	System.out.println(negative(args));
    }

    static String negative(String[] str) {

        // 否定文を格納する変数 answer の宣言
	// 初期値として空の文字列 ("") を代入しておく
	String answer = "";


	answer に否定文を作るプログラムをここに書く

	ヒント
	    answer = answer + " " + "This";
	    answer = answer + " " + "is";
	    answer = answer + " " + "a";
	    answer = answer + " " + "pen";
	    のように書くと 「This is a pen」という文ができあがる

	    answer = answer + " " + "This";
	    answer = answer + " " + "is" + " not";
	    answer = answer + " " + "a";
	    answer = answer + " " + "pen";
	    のように書くと 「This is not a pen」という文ができあがる


	return answer;
    }
}

問題4

キーと値の組からなるデータ構造を「マップ (map)」と呼ぶ。氏名から電話番号を検索できるような電話帳のようなものは、氏名をキーとし、電話番号を値としたマップを用いるのが適している。

配列を使ったマップを扱うプログラムを作成しなさい。マップを使った例として電話帳を作成すること。プログラム名は TelephoneBook とする。

考え方は次のとおりである。

プログラムの中に配列を2つ用意する。 1つ目はキーを入れる配列(例えば String[] key)、 2つ目は値を入れる配列(例えば String[] value)である。

Dendai Taro の電話番号が090-1234-5678で、 Denko Hanako の電話番号が080-2345-6789であった場合、各配列の内容を次のようにしておく。

key[0] = "Dendai Taro"
value[0] = "090-1234-5678"

key[1] = "Denko Hanako"
value[1] = "090-2345-6789"

ここで Denko Hanako の電話番号を調べることにする。そのためには、まず配列 key の中から Denko Hanako を探しその要素の番号「1」を得る。次に、value[1]の値を取り出せば、電話番号がわかることになる。

この考え方に基づき、以下のようなマップの操作を行うメソッドと、適当な内容のメソッド main を作成しなさい。電話帳の内容はなるべく現実的な内容が良いが、個人情報の取り扱いには注意すること。

メソッドinitialize: 配列key、配列valueを受け取り、配列の内容を初期化するメソッド。具体的には「未使用」を表わす何らかの特別なデータ (例えば "none") を配列の各要素に代入する働きをするようにする。
メソッドadd: 配列key、配列value、追加したいキーと値のペアを受け取り、マップにデータを追加するメソッド。
メソッドindexOf: 配列key、探したいキーを指定し、マップ上からデータを探し出すメソッド。見つかった場合、配列の何番目に見つかったかを返す。見つからない場合、-1 を返す。
メソッドremove: 配列key、配列value、削除したいキーを指定し、マップ上からデータを削除するメソッド。具体的には、削除した要素に削除済を表わす特別な値 (例えば "void") を代入する方法や、削除された要素より後ろの内容を1つずつ前にずらして上書きする方法などが考えられる。
メソッドget: 配列key、配列value、探したいキーを指定し、キーに対応する値を取り出すメソッド。
メソッドprint: 配列key、配列valueを指定し、マップの内容全体を表示するメソッド。