プログラミング/6

出典: CourseWiki

今回はちょっと難しいかも知れません.分からなかったら教員を捕まえて聞いてください. 演習はスキップせずに,まずは自分で解いてから回答を見るように.

目次

メソッドと配列

メソッドの引数として配列を使うこともできます.

下の例では,mainメソッドの中からdataという配列をprintArrayメソッドとaddAllメソッドに渡しています. mainメソッドではdataという名前の配列を,printArrayメソッドやaddAllメソッドでは異なる名前の引数(それぞれnums, values)で受け取っています.

public class MethodAndArray {
    public static void main(String[] args) {
        int[] data = {1, 2, 3};
        printArray(data);
        addAll(data, 10);
        printArray(data);
    }
    
    // 配列を表示するメソッド
    private static void printArray(int[] nums) {
        System.out.print("<");
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
            if (i < nums.length - 1) {        // 最後の要素の後には "," を表示しない
                System.out.print(", ");
            }
        }
        System.out.println(">");
    }
    
    // 配列の全ての要素に n を加算する
    private static void addAll(int[] values, int n) {
        for (int i = 0; i < values.length; i++) {
            values[i] += n;
        }
    }
}

まず,プログラムをよく読んでください.

これを実行すると,次の出力が得られます.

<1, 2, 3>
<11, 12, 13>

addAllメソッドの中で配列の中身を書き換えると,mainメソッドで確保している配列dataまで書き変わっている点に注意してください.

前回の説明では,メソッドを呼び出す際,引数の値はコピーされて渡されるので,呼び出されたメソッドで値を書き換えても呼び出し側の変数には影響を受けないということでした.何か矛盾しているような気がしますね.

ヒープメモリとnew演算子

実は,配列は普通の変数とは扱いが異なります.

配列を作成すると,配列の中身はヒープメモリ(heap memory)と呼ばれるメモリ領域に格納されます(単にヒープともいいます). Javaのヒープメモリは,さまざまなオブジェクトを格納することができるメモリです. Javaでは配列はオブジェクトなのでヒープメモリに格納されることになります.(オブジェクトの話はまた後日やりますが, とりあえず配列はオブジェクトということだけは理解しておいて下さい)

ちなみに(配列ではない)普通の変数はスタックに格納されます. スタック上の変数はメソッドが終了したら消滅するのに対し, ヒープメモリ上のオブジェクトはメソッドが終了しても消滅しません.

さて,mainメソッドで

int[] data = {1, 2, 3};

と書いていますが,これは実際には

int[] data;
data = new int[3];
data[0] = 1;
data[1] = 2;
data[2] = 3;

という動作になります(プログラミング/4#初期値がある配列の作成参照).

今まで new を説明なしに使ってきましたが,実は new はヒープメモリ上にオブジェクトを生成し,生成した場所を示す値を返す演算子です

場所を示す値というのが分かりにくいかも知れませんが,ヒープメモリ上の複数のオブジェクトを識別するための何らかの値と思って下さい.(他の言語を知っている人にはポインタに相当すると言えばわかりやすいでしょう).

  • int[] data; は,int型の配列の場所を示す値 を入れるための変数 data を宣言しています.
  • data = new int[3]; は,ヒープメモリ上に配列(int[3])を格納するためのメモリ領域を確保し,確保した場所を示す値を data に代入しています.

参照

このとき,data はヒープメモリ上のオブジェクトを参照(refer)している,あるいは参照(reference)を保持している,といいます.new 演算子は参照を返す演算子ということになります.

参照は値なのですが,普通の数式と同じように加算したり,int型の変数に代入したりはできません. ただし,次のUnderstandReferenceプログラムで出てくるように同じ型の変数には代入できます.

mainメソッドからprintArrayやaddAllメソッドを呼ぶ際,dataに入っている参照(場所の情報)だけがコピーされています. 配列そのものはコピーされていないので,addAllメソッドで配列の中身を書き換えるとmainメソッドからもその結果が見えたのです.

画像:ArrayAndHeapMemory.png

イメージできましたか?

次のプログラムは参照を理解するためのものです.

public class UnderstandReference {
    public static void main(String[] args) {
        int[] data = new int[3];
        int[] data2 = data;        // 参照のコピー
        int[] data3 = data;        // 参照のコピー
        data[0] = 10;
        data2[1] = 20;
        data3[2] = 30;
        System.out.println(java.util.Arrays.toString(data));
        System.out.println(java.util.Arrays.toString(data2));
        System.out.println(java.util.Arrays.toString(data3));
    }
}

このプログラムを実行すると,次の出力が得られます.なぜそうなるのかよく考えてください.

[10, 20, 30]
[10, 20, 30]
[10, 20, 30]

配列を返すメソッド

メソッドから配列を受け取ることもできます.実行して動作を確認してください.

 
public class MethodAndArray2 {
    public static void main(String[] args) {
        int[] values = getArray(5);
        System.out.println("Sum = " + sum(values));
    }
    
    // 指定された個数の要素を持つ配列にキーボードから値を入れて返すメソッド
    // 返り値の型が int[] になっていることに注目
    private static int[] getArray(int n) {
        int[] data = new int[n];
        System.out.println("Input " + n + " integers");
        for (int i = 0; i < n; i++) {
            System.out.print((i + 1) + ": ");
            data[i] = Keyboard.intValue();
        }
        return data;        // 配列(実際は配列への参照)を返している
    }
    
    // 指定された配列の合計を返すメソッド
    private static int sum(int[] data) {
        int sum = 0;
        for (int i = 0; i < data.length; i++) {
            sum += data[i];
        }
        return sum;
    }
}

配列を使った演習

演習(検索1)

以下のメソッドを含むプログラム Find1 を書きなさい.

  • 指定された配列(int[])から,指定された値(int)を検索するメソッド find
    • findメソッドでは,値が見つかった場所(配列の添え字)を返す.複数ある場合は,最も添え字の小さいものを返すこと.
    • 見つからない場合は -1 を返す.
private static int find(int[] data, int value) {
  ..
}
  • 指定された配列(int[])から,指定された値の出現回数を返すメソッド count
    • 指定された値がなければ 0 を返す.
private static int count(int[] data, int value) {
  ..
}

以下のmainメソッドでテストしてください.

public static void main(String[] args) {
  int[] data = {1, 2, 3, 2, 5};
  System.out.println(find(data, 1));  // 0 を表示するはず
  System.out.println(find(data, 2));  // 1 を表示するはず
  System.out.println(find(data, 100));  // -1 を表示するはず
  System.out.println(count(data, 1));  // 1 を表示するはず
  System.out.println(count(data, 2));  // 2 を表示するはず
  System.out.println(count(data, 100));  // 0 を表示するはず
} 

演習(検索1)の回答例

演習(配列のコピー)

上で述べたように,配列を参照している変数の値をコピーしても,配列そのものはコピーされません. 配列をコピーしたいときもあるので,指定された配列をコピーした新しい配列を返すメソッド private static int[] copyArray(int[] data) を書いてください.

プログラム名は ArrayCopy とします.以下のmainメソッドでテストしてください.

public static void main(String[] args) {
 int[] data = new int[3];
 data[0] = 10;
 int[] data2 = copyArray(data);
 data2[1] = 20;
 int[] data3 = copyArray(data2);
 data3[2] = 30;
 System.out.println("data  = " + java.util.Arrays.toString(data));
 System.out.println("data2 = " + java.util.Arrays.toString(data2));
 System.out.println("data3 = " + java.util.Arrays.toString(data3));
}

copyArrayでは新しい配列を new で作成して,配列の要素を一つずつコピーします. コピーの配列の大きさは,引数の配列の大きさと同じにしてください.

演習(配列のコピー)の回答例

演習(エラトステネスの篩)

素数を求めるための有名な方法に,エラトステネスの篩(ふるい)があります.これを使ってnより小さい全ての素数を表示するプログラム Eratosthenes を書きましょう.

上のページを参考に,nより小さい(n未満の)全ての素数を見つけるメソッド private static boolean[] sieve(int n) を書いて下さい.

このメソッドの返り値の型はboolean[]なので,boolean型の配列です.つまり,各要素がtrueかfalseの配列になります.

返り値のboolean型の配列は,i が素数ならば配列のi番目の要素が true に,そうでなければ false になっているような,大きさがnの配列です(例えば,2は素数なので配列の2番目の要素はtrue.4は素数ではないので4番目の要素はfalseになります).

なお,配列の「番目」は 0 から数えています

mainメソッドはこんな感じです.配列名にもメソッド名にも同じ sieve を使っていますが,問題ありません. (sieve というのは篩という意味です).

public static void main(String[] args) {
	// 素数だけ true にした配列を得る 
	boolean[] sieve = sieve(1000);
	
	// 素数の表示 (10個表示するごとに改行)
	int n = 0;
	for (int i = 0; i < sieve.length; i++) {
		if (sieve[i]) {
			System.out.print(i);
			n++;
			if (n % 10 == 0) {
				System.out.println();
			} else {
				System.out.print(" ");
			}
		}
	}
	System.out.println();
}

余裕がある人は,下のヒントを見ずに sieve を自分で書いてみてください.

なお,boolean型の配列を作ると,全ての要素には最初 false が入っています (プログラミング/4#配列の作成参照).

課題6-1

ある配列の中で,別の配列の並び(シーケンス)が出現する場所を検索するプログラム Find2 を書きましょう. これは様々な検索の基本的な処理になります.

例えば {1, 2, 3, 4, 5} という配列から,{3, 4} のシーケンスが出現する場所を検索する場合, {3, 4} は最初の配列の2番目(0から数えて)の要素から始まっているので,2という値を表示します.

これを,以下の find メソッドと match メソッドを使って実現してください.

findメソッド

以下の動作をするメソッド private static int find(int[] data, int[] seq) を書いてください.

  • 配列data上で,配列seqのシーケンスが始まる要素の添え字(インデックス)を返す.
  • もし複数の個所にシーケンスが存在する場合,もっとも先頭に近い個所のインデックスを返す.
  • シーケンスが存在しなければ -1 を返す.

例:

// mainメソッドとして使って下さい
int[] data = {1, 2, 3, 2, 3, 4};  // この配列から
int[] seq1 = {1, 2, 3};           // このシーケンスが出現するところを探す
System.out.println(find(data, seq1)); // 0 を返す((1, 2, 3) は dataの0番目から存在)
int[] seq2 = {2, 3};
System.out.println(find(data, seq2)); // 1 を返す((2, 3) はdataの1番目と3番目にあるが,先頭に近いのは1番目)
int[] seq3 = {2, 1};
System.out.println(find(data, seq3)); // -1 を返す((2, 1) は存在しない)
int[] seq4 = {3, 4, 5};
System.out.println(find(data, seq4)); // -1 を返す((3, 4, 5) は存在しない)

この処理は2重ループで実現できますが,ここではより簡単に書くために次のmatchメソッドを使います. matchメソッドを使って,findメソッドを書いてください.

matchメソッド

配列の指定された位置から,シーケンスがマッチするか(一致するか)どうかを判定するメソッド
private static boolean match(int[] data, int[] seq, int base) を書いてください.

このメソッドは配列 data の base 番目の要素からと,配列 seq の(先頭からの)シーケンスがマッチすれば true,マッチしなければ false を返します.指定された個所しかチェックしないで良いので,find メソッドより簡単です.

例:

int[] data = {1, 2, 3, 2, 3, 4};
int[] seq = {1, 2, 3};
System.out.println(match(data, seq, 0)); // true
System.out.println(match(data, seq, 1)); // false

シーケンスがマッチするかどうかは,シーケンスの長さだけ繰り返して調べる必要があります.そのためには, i を 0 から seq.length - 1 までの範囲で動かしながら,data[base + i] と seq[i] が全て等しいときだけ true を返し,一ヶ所でも違うところがあればfalseを返すようにすればよいでしょう.

構造としてはプログラミング/5#isPrimeメソッドに少し似ています.

注意

matchメソッドができれば,findメソッドではbaseの値を変化させながらmatchメソッドを呼べばよいはずです.

matchメソッドの引数で与える base の値によっては,配列 data の末尾より後ろをチェックしようとしてしまう (上の例だと,dataの長さが6,seq1の長さが3なので,base に 4 を与えるとdata[4], data[5], data[6]をチェックする可能性があるが,data[6]は配列の範囲外).このようなことがないように,match を呼び出す側 (findメソッド側) で与える base の値に注意して下さい.

いきなり find メソッドと match メソッドの両方を書くのは難しい場合は,まず match メソッドを書いて,それが期待通りに動くことを確認してから find メソッドを書きましょう.

課題6-2

エラトステネスの篩のプログラムでは,boolean型の配列で結果を受け取りました. これだと,n番目の素数は何かというのは簡単にはわかりません(配列の先頭から数える必要がある).

簡単にわかるためには,n番目の要素がn番目の素数になっているような配列があれば都合がよさそうです.

  • 0番目の要素: 2
  • 1番目の要素: 3
  • 2番目の要素: 5
  • 3番目の要素: 7
  • ...

そこで,sieveメソッドで得られる boolean 型の配列を使って,そのような配列を得るメソッド private static int[] convert(boolean[] sieve) を書いてください. また,mainメソッドではconvertを呼び出して,得られた配列を表示してください.

convertの返り値の配列の大きさは,sieve に含まれている素数の数になります(素数の数は sieve.length ではなく, 配列のなかの true の要素の数です).

プログラム名(クラス名)は Eratosthenes2 としておきます.

ヒント

  • Eratosthenes プログラムに convert メソッドを追加することになる.
  • 返り値の配列を int[] primes とする.
  • primes を new するためには,まずsieveの中の素数の数を数える必要がある (そうしないとprimesの要素の数が分からない)
  • あとは,sieveをチェックして,素数があったら primes に詰めていく.
  • sieveをチェックするときのインデックス(添え字)と,primes に詰めるときのインデックスは異なる.
    • 両方のインデックスを別々の変数で持つ必要がある.


Copyright (C) 2002-2015 Kota Abe, Osaka City University

ナビゲーション