[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

情報処理IIIA(Javaプログラミング入門)第7回

目次 索引
7.1 反復と変数
7.1.1 変数のスワップ
7.1.2 ユークリッドの互除法
7.2 反復と配列
7.2.1 多重ループ
7.2.2 エラトステネスのふるい
7.2.3 選択整列法
7.2.4 挿入整列法
7.3 演習7
7.4 レポート課題
エラトステネスのふるい  スワップ  整列  選択整列法  挿入整列法  多重ループ  ユークリッドの互除法 

7.1 反復と変数

7.1.1 変数のスワップ

変数の値を交換することを、変数の スワップswap ) と言います。 変数 xy をスワップするプログラムを考えます。 次は間違っている例です。

/*  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@AsiaA1:~/java% java BadSwap
x is 200
y is 200
b00a001@AsiaA1:~/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@AsiaA1:~/java% java GoodSwap
x is 200
y is 100
b00a001@AsiaA1:~/java%

7.1.2 ユークリッドの互除法

スワップを使う例として、ユークリッドの互除法を取り上げます。

ユークリッドの互除法Euclidean algorithm ) とは、二つの整数の最大公約数を求めるアルゴリズムです。 これは、 m > n (> 0)としますと、 mn の最大公約数は、 nmn の最大公約数に等しいという性質を利用します。 つまり、次々と割った余りを求めていき、割り切れたときの割る数が最大公約数であるということです。

例として、105 と 287 の最大公約数を求めます。 287%105 は 77 ですので、答えは 105 と 77 の最大公約数と等しいことが分かります。 さらに 105%77 は 28 ですので、答えは 77 と 28 の最大公約数となり、77%28 は 21 ですので、28 と 21 となり、28%21 は 7 ですので、21 と 7 となり、ここで割り切れますので、7 が最大公約数であるという結論が得られるのです。

アルゴリズムは次のようになります。

  1. 変数 m を宣言し、初期値を 105 とする。
  2. 変数 n を宣言し、初期値を 287 とする。
  3. スワップ用の変数 temp を宣言する。
  4. もし m < n ならば、{
  5.     変数 mn をスワップする。
  6. n > 0 の間、以下を繰り返す。{
  7.     確認のため、変数 mn の値を出力する。
  8.     式 mn の値を変数 temp に格納する。
  9.     変数 n の値を変数 m に格納する。
  10.     変数 temp の値を変数 n に格納する。
  11. 最大公約数として、変数 m の値を出力する。

プログラムは以下のようになります。

/*  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@AsiaA1:~/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@AsiaA1:~/java%

7.2 反復と配列

7.2.1 多重ループ

反復は、 for 文や while 文を用いて書き表しました。 for 文の中に、さらに for 文を書くこともできます。 このような、「反復の反復」となる構造は、 多重ループnested loop ) とよばれます。 多重ループでは、ループ制御変数が衝突しないように注意する必要があります。

次のプログラムは、2重のループの中で、ループ制御変数の値を出力するものです。 ループ制御変数は、 ij の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@AsiaA1:~/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@AsiaA1:~/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@AsiaA1:~/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@AsiaA1:~/java%

6行目と7行目の反復回数は、 i の値が 0 のときは 1 回、1 のときは 2 回、2 のときは 3 回、そして 3 のときは 4 回です。

7.2.2 エラトステネスのふるい

多重ループの例として、エラトステネスのふるいを取り上げます。

エラトステネスのふるいEratosthenes' sieve ) とは、与えられた数未満の素数をリストアップするアルゴリズムです。 素数とは、1 と自分以外に約数を持たない数であることを思い出してください。

例として、100 未満の素数をすべて求めます。 このアルゴリズムでは、はじめに 2 以上 100 未満の数をすべてふるいにのせます。 次に、2 より大きな 2 の倍数は素数ではありませんので、これらをふるいから落とします。 続いて、3 より大きな 3 の倍数は素数ではありませんので、これらをふるいから落とします。 4 は 2 の倍数のときにふるいから落ちています。 これは、4 の倍数は 2 の倍数だから、新たにふるいから落ちるものはないことを意味しています。 5 はふるいに残っていますので、5 より大きな 5 の倍数をふるいから落とします。 この作業を 100 まで行い、最後までふるいに残った数が素数だというわけです。

An image of the sieve
図 7.1  ふるいのイメージ

アルゴリズムは次のようになります。

  1. ループ制御変数 ij を宣言する。
  2. ふるいを表す配列 sieve を宣言し、要素数を 100 とする。
  3. 変数 i の値を 2 から配列 sieve の要素数未満の間増加させながら、以下を繰り返す。{
  4.     ふるいに残っていることを表す数 1 を配列要素 sieve [ i ] に格納する。
  5. 変数 i の値を 2 から配列 sieve の要素数未満の間増加させながら、以下を繰り返す。{
  6.     もし sieve [ i ] が 1 ならば、{
  7.         式 2× i の値を変数 j に格納する。
  8.          jsieve の要素数未満の間、以下を繰り返す。{
  9.             数 0 を配列要素 sieve [ j ] に格納する。
  10.             変数 j の値を i 増やす。
  11.         }
  12.     }
  13. 変数 i の値を 2 から配列 sieve の要素数未満の間増加させながら、以下を繰り返す。{
  14.     もし sieve [ i ] が 1 ならば、{
  15.         変数 i の値を出力する。
  16.     }

プログラムは以下のようになります。

/*  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@AsiaA1:~/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@AsiaA1:~/java%

7.2.3 選択整列法

整列sorting ) とは、要素の列を小さい順(あるいは大きい順)に並べ替えることです。 ここで、大小関係は必ずしも数のものとは限りません。 例えば、辞書のより前にあらわれることをより小さいとすれば、単語の列を整列することは、辞書を編集することに相当します。 また、図書館では、分類コードの順番にしたがって本が整列されています。

整列はデータ処理の基本的かつ重要なテーマであり、今日までに様々なアルゴリズムが提案されています。 この授業では、その中から簡単なものを紹介します。

選択整列法selection sort ) とは、「0 番目以降の要素から最小要素を選択し、それと 0 番目の要素を交換する。1 番目以降の要素から最小要素を選択し、それと 1 番目の要素と交換する。…。」という整列法です。 この方法によって、最終的に、一番小さい要素、その次に小さい要素、…と並ぶというわけです。

例えば、

{30, 50, 10, 20, 40}

で表される配列の場合は次のようになります。

An image of the selection sort
図 7.2  選択整列法のイメージ

アルゴリズムは次のようになります。

  1. ループ制御変数 i , j 、最小要素の添字を表す変数 minIndex およびその値を表す変数 minValue を宣言する。
  2. 整列する配列 a を宣言し、初期値を 30, 50, 10, 20, 40 とする。
  3. 変数 i の値を 0 から配列 a の要素数 ー1 未満の間増加させながら、以下を繰り返す。{
  4.     とりあえず変数 i の値を変数 minIndex に格納する。
  5.     とりあえず配列要素 a [ i ] の値を変数 minValue に格納する。
  6.     変数 j の値を i +1 から配列 a の要素数未満の間増加させながら、以下を繰り返す。{
  7.         もし a [ j ] が minValue より小さいならば、{
  8.             変数 j の値を変数 minIndex に格納する。
  9.             配列要素 a [ j ] の値を変数 minValue に格納する。
  10.         }
  11.     }
  12.     配列要素 a [ i ] の値を配列要素 a [ minIndex ] に格納する。
  13.     変数 minValue の値を配列要素 a [ i ] に格納する。
  14.     確認のため、配列 a の各要素を出力する。

プログラムは以下のようになります。

/*  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@AsiaA1:~/java% java Selection
 10 50 30 20 40
 10 20 30 50 40
 10 20 30 50 40
 10 20 30 40 50
b00a001@AsiaA1:~/java%

7.2.4 挿入整列法

挿入整列法insertion sort ) とは、「左側に整列済みの範囲を確保し、範囲外の要素を一つづつ整列済みの範囲に挿入することによって、最終的に全体を整列済みにする。」という整列法です。 最初の整列済みの範囲は、0 番目の要素一つだけとします。 1 番目の要素を挿入し、2 番目の要素を挿入し、…と繰り返し、右端の要素を挿入したら、整列は完了します。 挿入位置は、整列済みの範囲を右から見ていき、挿入要素より大きな要素をずらしていって、そうでない所(すべての要素をずらしたときは左端)になります。

例えば、

{30, 50, 10, 20, 40}

で表される配列の場合は次のようになります。

An image of the insertion sort
図 7.3  挿入整列法のイメージ

アルゴリズムは次のようになります。

  1. ループ制御変数 i , j と挿入要素を表す変数 insValue を宣言する。
  2. 整列する配列 a を宣言し、初期値を 30, 50, 10, 20, 40 とする。
  3. 変数 i の値を 1 から配列 a の要素数未満の間増加させながら、以下を繰り返す。{
  4.     配列要素 a [ i ] の値を変数 insValue に格納する。
  5.     式 i ー1 の値を変数 j に格納する。
  6.      j が 0 以上で、 a [ j ] が insValue より大きい間、以下を繰り返す。{
  7.         配列要素 a [ j ] の値を配列要素 a [ j +1] に格納する。
  8.         変数 j の値を1減らす。
  9.     }
  10.     変数 insValue の値を配列要素 a [ j +1] に格納する。
  11.     確認のため、配列 a の各要素を出力する。

プログラムは以下のようになります。

/*  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@AsiaA1:~/java% java Insertion
 30 50 10 20 40
 10 30 50 20 40
 10 20 30 50 40
 10 20 30 40 50
b00a001@AsiaA1:~/java%

7.3 演習7

次の5人を背の低い順に並べ替えます。

表 7.1  身長と体重
No. 0 1 2 3 4
身長 160 150 180 170 140
体重 60 50 80 70 40

身長と体重は並列配列に格納し、これを挿入整列法によって整列します。 身長と体重を同時に並べ替えなくてはならないことに注意してください。

アルゴリズムは次のようにします。

  1. ループ制御変数 i , j を宣言する。
  2. 挿入身長を表す変数 s と挿入体重を表す変数 w を宣言する。
  3. 身長を表す配列 stature を宣言し、初期値を 160, 150, 180, 170, 140 とする。
  4. 体重を表す配列 weight を宣言し、初期値を 60, 50, 80, 70, 40 とする。
  5. 変数 i の値を 1 から配列 stature の要素数未満の間増加させながら、以下を繰り返す。{
  6.     配列要素 stature [ i ] の値を変数 s に格納する。
  7.     配列要素 weight [ i ] の値を変数 w に格納する。
  8.     式 i ー1 の値を変数 j に格納する。
  9.      j が 0 以上で stature [ j ] が s より大きい間、以下を繰り返す。{
  10.         配列要素 stature [ j ] の値を配列要素 stature [ j +1] に格納する。
  11.         配列要素 weight [ j ] の値を配列要素 weight [ j +1] に格納する。
  12.         変数 j の値を 1 減らす。
  13.     }
  14.     変数 s の値を配列要素 stature [ j +1] に格納する。
  15.     変数 w の値を配列要素 weight [ j +1] に格納する。
  16. 文字列"Stature"と"Weight"をタブで区切って出力する。
  17. 変数 i の値を 0 から配列 stature の要素数未満の間増加させながら、以下を繰り返す。{
  18.      i 番目の身長と体重をタブで区切って出力する。

このアルゴリズムをプログラムにしてください。

b00a001@AsiaA1:~/java% java StatureWeight
Stature Weight
140     40
150     50
160     60
170     70
180     80
b00a001@AsiaA1:~/java%

余力のある人は、挿入整列法の代わりに選択整列法を使ってください。


7.4 レポート課題

今日の演習7に従ってJavaプログラムを作成し、そのプログラムをkonishi@twcu.ac.jpあてにメールで提出してください。 メールには、学生番号、氏名、科目名、授業日(11/6)を明記してください。


[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

2003年11月13日更新
konishi@twcu.ac.jp
Copyright (C) 2003 Zenjiro Konishi. All rights reserved.