演習問題

解答は

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

ディレクトリ: /home/submit/JavaBasic/[今日の日付]/[学籍番号]

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

問題1 (Basic)

int 型の値の引数を受け取り、その絶対値を返すメソッド abs を書きなさい。 main メソッドは次のようにする。

プログラム名は AbsoluteCalculator とする。

class AbsoluteCalculator {
    public static void main(String[] args) {
        int a = -2;

        System.out.println(a + " の絶対値は " + abs(a));
    }

    static int abs(int x) {

        メソッド abs の内容

    }
}

問題2 (Basic)

2 つの int 型変数 x と y を引数として受け取り、べき乗 x^y を返すメソッド power を書きなさい。

main メソッドでは 2 つの int 型の数を用意しておき、そのべき乗の値を表示するようにすること。 y の値は 0 以上だと仮定して良い。

プログラム名は PowerCalculator とする。

class PowerCalculator {
    public static void main(String[] args) {
        int a = 3;
        int b = 4;

        System.out.println(a + " の " + b + " 乗は " + power(a, b));
    }

    ....
    メソッド power の内容
    ....
}

問題3 (Standard)

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

int 型の配列から最大の値を探して返すメソッド maxVariable を書きなさい。上の例で示した配列が与えられたとき 16 が求まれば良い。プログラム名は MaxSearcher とする。

このプログラムは、次のように、引数に配列を受け取り、その配列から最大値を探すメソッド maxVariable を定義し、 main から呼び出すように作ること。

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

        System.out.println("最大値は " + maxVairble(a) + "です");
    }

    ......
    メソッド maxVariable の中身をここに書く
    ......
}

なお、配列から最大または最小の要素を探す方法は配列の回の例題で取り上げている。このプログラムを参考にすると良い。

問題4 (Standard)

組み合せの数 _nＣ_m を求めるメソッド combination を書きなさい。このメソッドの引数は、 int 型整数が 2 つ (n と m) である。例題 1 のメソッド fact を利用して書くこと。したがって、 main が combination を呼び、combination が fact を呼ぶので、 2 段階の呼び出しになる。

このメソッド combination を使い、Pascal の三角形 (0 ≦ n ≦ 10 における 0 ≦ m ≦ n の _nＣ_m の一覧表) を表示する main を書きなさい。

このプログラムを実行したとき、次のような結果になれば良い。

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1

ファイル名は PascalsTriangle.java としなさい。

問題5 (Advanced)

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

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

メソッド swap: 配列内の指定された2つの要素同士を入れ替えるメソッド。入れ替えの対象となる配列と、何番目と何番目を入れ替えるか (要素の通し番号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 の内容をここに書く


}

問題6 (Advanced)

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

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, 10, 12, 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 とする。

問題7 (Advanced)

階乗を求めるメソッド factorial を、漸化式の考え方を使って作成することを考えてみよう。 nの階乗は次の式で計算することができる。

    nの階乗 = n-1の階乗 * n;

    ただし、 n が 1 のときだけは n の階乗は 1 とする

これをプログラムとして書こうとすると次のようになる。

n ≠ 1 のとき
```
    factorial(n) = factorial(n-1) * n;
```
n = 1 のとき
```
    factorial(n) = 1
```

この考え方では、factorial(n) を計算するのに factorial(n - 1) を使っている。これに従ってメソッド factorial の定義とすると、 factorial の定義の中に factorial 自身が現れることになる。このような定義のことを再帰的定義と呼ぶ。

    static int factorial(int n) {
	// この中で factorial(n - 1) を使う
    }

ただし、n が 1 のときは factorial(1) = 1 であり、factorial(n - 1) を使わずに値が定まる。

n = 3 の場合の処理の流れは次のようになる。

factorial(3) を計算しようとすると、factorial(2) が必要になる。
  そこで factorial(2) を計算しようとすると、factorial(1) が必要になる。
    そこで factorial(1) を計算しようとすると、定義から 1 と決まっている。
  よって factorial(2)が計算できて、
そして factorial(3)が計算できる。めでたし。

以上の考え方から、階乗を計算するメソッド factorial を定義し、適当な数の階乗を計算するプログラムを作成しなさい。プログラム名は FactorialRecursively とする。