| 目次 | 索引 |
|---|---|
変数の値を交換することを、変数の
スワップ
（
swap
）
と言います。
変数
x
と
y
をスワップするプログラムを考えます。
次は間違っている例です。
/* 1*/ class BadSwap { /* 2*/ public static void main (String[] args) { /* 3*/ int x = 100, y = 200; /* 4*/ x = y; /* 5*/ y = x; /* 6*/ System.out.println("x is " + x); /* 7*/ System.out.println("y is " + y); /* 8*/ } /* 9*/ }
b00a001@Ampere:~/java% java BadSwap x is 200 y is 200 b00a001@Ampere:~/java%
4行目を実行した段階で、
x
に格納されているデータが消えてしまいますので、うまくいかないのです。
もう一つ変数
z
を用意し、そこにいったん
x
の値をコピーしておくとうまくいきます。
/* 1*/ class GoodSwap { /* 2*/ public static void main (String[] args) { /* 3*/ int x = 100, y = 200, z; /* 4*/ z = x; /* 5*/ x = y; /* 6*/ y = z; /* 7*/ System.out.println("x is " + x); /* 8*/ System.out.println("y is " + y); /* 9*/ } /*10*/ }
b00a001@Ampere:~/java% java GoodSwap x is 200 y is 100 b00a001@Ampere:~/java%
スワップを使う例として、ユークリッドの互除法を取り上げます。
ユークリッドの互除法 （ Euclidean algorithm ） とは、二つの整数の最大公約数を求めるアルゴリズムです。 これは、 m > n （> 0）としますと、 m と n の最大公約数は、 n と m ％ n の最大公約数に等しいという性質を利用します。 つまり、次々と割った余りを求めていき、割り切れたときの割る数が最大公約数であるということです。
例として、105 と 287 の最大公約数を求めます。 287％105 は 77 ですので、答えは 105 と 77 の最大公約数と等しいことが分かります。 さらに 105％77 は 28 ですので、答えは 77 と 28 の最大公約数となり、77％28 は 21 ですので、28 と 21 となり、28％21 は 7 ですので、21 と 7 となり、ここで割り切れますので、7 が最大公約数であるという結論が得られるのです。
アルゴリズムは次のようになります。
プログラムは以下のようになります。
/* 1*/ class Euclidean { /* 2*/ public static void main (String[] args) { /* 3*/ int m = 105, n = 287, temp; /* 4*/ if (m < n) { /* 5*/ temp = m; m = n; n = temp; /* 6*/ } /* 7*/ while (n > 0) { /* 8*/ System.out.print("m is " + m); /* 9*/ System.out.println(" n is " + n); /*10*/ temp = m % n; /*11*/ m = n; n = temp; /*12*/ } /*13*/ System.out.println("GCD is " + m); /*14*/ } /*15*/ }
b00a001@Ampere:~/java% java Euclidean m is 287 n is 105 m is 105 n is 77 m is 77 n is 28 m is 28 n is 21 m is 21 n is 7 GCD is 7 b00a001@Ampere:~/java%
反復は、
for
文や
while
文を用いて書き表しました。
for
文の中に、さらに
for
文を書くこともできます。
このような、「反復の反復」となる構造は、
多重ループ
（
nested loop
）
とよばれます。
多重ループでは、ループ制御変数が衝突しないように注意する必要があります。
次のプログラムは、2重のループの中で、ループ制御変数の値を出力するものです。
ループ制御変数は、
i
と
j
の2つです。
この2つの変数の値がどう変化するかに注目してください。
/* 1*/ class NestedLoop { /* 2*/ public static void main (String[] args) { /* 3*/ int i, j; /* 4*/ for (i = 0; i < 3; i++) { /* 5*/ for (j = 0; j < 4; j++) { /* 6*/ System.out.print("i is " + i); /* 7*/ System.out.println(" j is " + j); /* 8*/ } /* 9*/ } /*10*/ } /*11*/ }
b00a001@Ampere:~/java% java NestedLoop i is 0 j is 0 i is 0 j is 1 i is 0 j is 2 i is 0 j is 3 i is 1 j is 0 i is 1 j is 1 i is 1 j is 2 i is 1 j is 3 i is 2 j is 0 i is 2 j is 1 i is 2 j is 2 i is 2 j is 3 b00a001@Ampere:~/java%
多重ループは、「長方形」のように実行されるとは限りません。 より複雑な多重ループも考えられます。
次のプログラムは、「三角形」のように実行される2重ループです。
/* 1*/ class NestedLoop2 { /* 2*/ public static void main (String[] args) { /* 3*/ int i, j; /* 4*/ for (i = 0; i < 4; i++) { /* 5*/ for (j = 0; j < i + 1; j++) { /* 6*/ System.out.print("i is " + i); /* 7*/ System.out.println(" j is " + j); /* 8*/ } /* 9*/ } /*10*/ } /*11*/ }
b00a001@Ampere:~/java% java NestedLoop2 i is 0 j is 0 i is 1 j is 0 i is 1 j is 1 i is 2 j is 0 i is 2 j is 1 i is 2 j is 2 i is 3 j is 0 i is 3 j is 1 i is 3 j is 2 i is 3 j is 3 b00a001@Ampere:~/java%
6行目と7行目の反復回数は、
i
の値が 0 のときは 1 回、1 のときは 2 回、2 のときは 3 回、そして 3 のときは 4 回です。
多重ループの例として、エラトステネスのふるいを取り上げます。
エラトステネスのふるい （ Eratosthenes' sieve ） とは、与えられた数未満の素数をリストアップするアルゴリズムです。 素数とは、1 と自分以外に約数を持たない数であることを思い出してください。
例として、100 未満の素数をすべて求めます。 このアルゴリズムでは、はじめに 2 以上 100 未満の数をすべてふるいにのせます。 次に、2 より大きな 2 の倍数は素数ではありませんので、これらをふるいから落とします。 続いて、3 より大きな 3 の倍数は素数ではありませんので、これらをふるいから落とします。 4 は 2 の倍数のときにふるいから落ちています。 これは、4 の倍数は 2 の倍数だから、新たにふるいから落ちるものはないことを意味しています。 5 はふるいに残っていますので、5 より大きな 5 の倍数をふるいから落とします。 この作業を 100 まで行い、最後までふるいに残った数が素数だというわけです。
アルゴリズムは次のようになります。
プログラムは以下のようになります。
/* 1*/ class Eratosthenes { /* 2*/ public static void main (String[] args) { /* 3*/ int i, j; /* 4*/ int[] sieve = new int[100]; /* 5*/ for (i = 2; i < sieve.length; i++) { /* 6*/ sieve[i] = 1; /* 7*/ } /* 8*/ for (i = 2; i < sieve.length; i++) { /* 9*/ if (sieve[i] == 1) { /*10*/ j = 2 * i; /*11*/ while (j < sieve.length) { /*12*/ sieve[j] = 0; /*13*/ j = j + i; /*14*/ } /*15*/ } /*16*/ } /*17*/ for (i = 2; i < sieve.length; i++) { /*18*/ if (sieve[i] == 1) { /*19*/ System.out.println(i); /*20*/ } /*21*/ } /*22*/ } /*23*/ }
b00a001@Ampere:~/java% java Eratosthenes 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 b00a001@Ampere:~/java%
整列 （ sorting ） とは、要素の列を小さい順（あるいは大きい順）に並べ替えることです。 ここで、大小関係は必ずしも数のものとは限りません。 例えば、辞書のより前にあらわれることをより小さいとすれば、単語の列を整列することは、辞書を編集することに相当します。 また、図書館では、分類コードの順番にしたがって本が整列されています。
整列はデータ処理の基本的かつ重要なテーマであり、今日までに様々なアルゴリズムが提案されています。 この授業では、その中から簡単なものを紹介します。
選択整列法 （ selection sort ） とは、「0 番目以降の要素から最小要素を選択し、それと 0 番目の要素を交換する。1 番目以降の要素から最小要素を選択し、それと 1 番目の要素と交換する。…。」という整列法です。 この方法によって、最終的に、一番小さい要素、その次に小さい要素、…と並ぶというわけです。
例えば、
{30, 50, 10, 20, 40}
で表される配列の場合は次のようになります。 括弧は交換される要素を表します。
(30) 50 (10) 20 40 10 (50) 30 (20) 40 10 20 30 50 40 10 20 30 (50)(40) 10 20 30 40 50
アルゴリズムは次のようになります。
プログラムは以下のようになります。
/* 1*/ class Selection { /* 2*/ public static void main (String[] args) { /* 3*/ int i, j, minIndex, minValue; /* 4*/ int[] a = {30, 50, 10, 20, 40}; /* 5*/ for (i = 0; i < a.length - 1; i++) { /* 6*/ minIndex = i; minValue = a[i]; /* 7*/ for (j = i + 1; j < a.length; j++) { /* 8*/ if (a[j] < minValue) { /* 9*/ minIndex = j; /*10*/ minValue = a[j]; /*11*/ } /*12*/ } /*13*/ a[minIndex] = a[i]; /*14*/ a[i] = minValue; /*15*/ for (j = 0; j < a.length; j++) { /*16*/ System.out.print(" " + a[j]); /*17*/ } /*18*/ System.out.println(); /*19*/ } /*20*/ } /*21*/ }
b00a001@Ampere:~/java% java Selection 10 50 30 20 40 10 20 30 50 40 10 20 30 50 40 10 20 30 40 50 b00a001@Ampere:~/java%
挿入整列法 （ insertion sort ） とは、「左側に整列済みの範囲を確保し、範囲外の要素を一つづつ整列済みの範囲に挿入することによって、最終的に全体を整列済みにする。」という整列法です。 最初の整列済みの範囲は、0 番目の要素一つだけとします。 1 番目の要素を挿入し、2 番目の要素を挿入し、…と繰り返し、右端の要素を挿入したら、整列は完了します。 挿入位置は、整列済みの範囲を右から見ていき、挿入要素より大きな要素をずらしていって、そうでない所（すべての要素をずらしたときは左端）になります。
例えば、
{30, 50, 10, 20, 40}
で表される配列の場合は次のようになります。 括弧は整列済みの範囲を表します。
(30) 50 10 20 40 (30 50) 10 20 40 (10 30 50) 20 40 (10 20 30 50) 40 (10 20 30 40 50)
アルゴリズムは次のようになります。
プログラムは以下のようになります。
/* 1*/ class Insertion { /* 2*/ public static void main (String[] args) { /* 3*/ int i, j, insValue; /* 4*/ int[] a = {30, 50, 10, 20, 40}; /* 5*/ for (i = 1; i < a.length; i++) { /* 6*/ insValue = a[i]; /* 7*/ j = i - 1; /* 8*/ while (j >= 0 && a[j] > insValue) { /* 9*/ a[j + 1] = a[j]; /*10*/ j--; /*11*/ } /*12*/ a[j + 1] = insValue; /*13*/ for (j = 0; j < a.length; j++) { /*14*/ System.out.print(" " + a[j]); /*15*/ } /*16*/ System.out.println(); /*17*/ } /*18*/ } /*19*/ }
b00a001@Ampere:~/java% java Insertion 30 50 10 20 40 10 30 50 20 40 10 20 30 50 40 10 20 30 40 50 b00a001@Ampere:~/java%
以下のアルゴリズムにしたがってバブル整列法のプログラムを作成し、
{30, 50, 10, 20, 40}
で表される配列を整列してください。
ここで バブル整列法 （ bubble sort ） とは、「左端から順に見ていき、隣り合っていて逆順になっている二要素が見つかったら、そこを交換する。」という整列法です。 交換した後もそこから右へ見ていくことにすれば、右端にたどり着いたときには、右端に最大要素が来るはずです。 再び左端から見ていきますが、右端は最大要素ですから、右端の一つ手前まで見れば十分です。 この段階で、右端の一つ手前には2番目に大きな要素が来ます。 見る範囲をだんだん狭めていき、左端の二要素のみになってそれが終わったとき、整列が完了するわけです。
アルゴリズムは次のようにします。
b00a001@Ampere:~/java% java Bubble 30 10 20 40 50 10 20 30 40 50 10 20 30 40 50 10 20 30 40 50 b00a001@Ampere:~/java%
この例については、バブル整列法は第2段階で整列状態になります。 余力のある人は、バブル整列法で最終段階まで整列状態にならない例を考えてください。 一般的に、バブル整列法は選択整列法や挿入整列法よりも非能率的です。
今日の演習7に従ってJavaプログラムを作成し、そのプログラムをkonishi@twcu.ac.jpあてにメールで提出してください。 メールには、学生番号、氏名、科目名、授業日（11/7）を明記してください。