<<PREV | ToC | NEXT>>

制御構造の演習

Revised: Nov./06th/2004

前節までで、一通りの制御構造を紹介しました。プログラミング言語の制御構造というものは、極めて本質的なものであり、プログラマにとって最低限度のスキルです。ここでは、代表的な制御構造の使い方を復習しておきます。

演習1

if 文を使って次のアプリケーションを作成してください。

コマンド・ラインの第一引数が、３５より１０以上大きければ「大きい」、１０以上小さければ「小さい」と出力し、３５より１０未満大きければ「少し大きい」、１０未満小さければ「少し小さい」と出力し、３５ちょうどであれば「正解」と出力するアプリケーションをつくりましょう。

回答例1

演習2

if 文を使って次のアプリケーションを作成してください。

コマンドライン引数から３つの数字を入力して、8 0 6 と比べて、全て異なれば「アウト」、一つ正しければ「ヒット」、二つ正しければ「ツーベース」、全て正しければ「ホームラン」と出力してください。

回答例2

演習3

switch 文と if 文を使って次のアプリケーションを作成してください。

コマンドライン引数で 0 から 6 の数字を入力して、対応する曜日を出力してください。但し、 0 から 6 以外のコマンドライン引数が入力された場合以外は、「0 から 6 の整数を入力してください」と出力してください。

最低限度、次のケースを想定してください。

• 引数が無い
• 0 から 6 までの整数以外の引数が指定された

演習4

コマンド・ライン引数から0-10を受け取り、惑星名、ローマ神話の神名とギリシャ神話の神名を出力するアプリケーションを作りましょう。

演習5

while 文を使って次のアプリケーションを作成してください。

1 + 2 + 3 + 4 と足していき、総和が１万を超えたら、そのときの総和と最後に足した数を出力してください。

回答例5

演習6

ユーザ名の配列を用意し、コマンド・ライン引数で指定した名前が存在すればtrue、存在しなければfalseと出力するアプリケーションをつくりましょう。

ヒント

次のソース・コードのxxx部分を埋めて完成させてください。

配列custの要素数はcust.lengthで取得できます。文字列の比較には==演算子ではなくequals()メソッドを用います。returnはメソッドを終了させるキーワードです。ここではmain()メソッドが終了し、アプリケーションが終了します。

class Exam06 {
	public static void main(String[] args) {
		String[] cust = {"sugai", "sugimoto", "sumiyoshi", "suzuki"};
		int i = 0;
		while (x x xxxx.xxxxxx) {
			if (cust[i++].xxxxxx(xxxx[x])) {
				System.out.println(true);
				return;
			}
		}
		System.out.println(false);
	}
}

演習7

for 文を使って次のアプリケーションを作成してください。

2 の 1000 乗を計算してください。

ヒント

最初に、2 の 10 乗を計算してみてください。整数型 byte, short, int, long では、表現できる数字に限界があります。浮動小数点数型 float, double ではどうでしょうか？各々の型の限界まで計算してみてください。今回は何を使うのが最適でしょうか？

型の限界を超えると、結果が正しくなくなります。これを、「桁あふれ」と呼びます。整数であっても、整数型だけを使えば良いわけではありません。型の特徴を把握するようにしましょう。

実行結果：

C:\java>javac Exam07.java
C:\java>java Exam07 1000
2の1000乗：1.0715086071862673E301
C:\java>

2の1000乗は、およそ10の301乗になります。double 型の限界は、[-1.7976931348623157E308, 1.7976931348623157E308]なので、2の1000乗でギリギリですね。

因みに、日本の万進法の漢数字体系は次のようになっています。

尚、仏教典では、10⁵ を洛叉（らくしゃ）、10^7×20 = 10⁷ を倶胝（くてい）、10^7×21 = 10¹⁴ を阿蠎ｾ多（あゆた）と始まって、 10^7×22 = 10 ²⁸ を那由他（なゆた）、10^7×23 = 10 ⁵⁶ を頻波羅（びんばら）、10^7×24 = 10¹¹² を矜羯羅（こんがら）、10^7×25 = 10²²⁴ を阿伽羅（あから）などと続くそうです。この体系での最大の単位は、10^7×2119 = 10^{4652297985247205555163324710981206016}を不可説（ふかせつ）、10^7×2120 = 10^{9304595970494411110326649421962412032} を不可説転（ふかせつてん）、10^7×2121 = 10^{18609191940988822220653298843924824064} を不可説不可説（ふかせつふかせつ）、10^7×2122 = 10^{37218383881977644441306597687849648128}を不可説不可説転（ふかせつふかせつてん）であるそうで。

演習8

for 文を使って次のアプリケーションを作成してください。

1*1, 11*11, 111*111, 1111*1111, 11111*11111, 111111*111111 を計算してください。

演習9

ユークリッドのアルゴリズムに、二つの正の整数の最大公約数 GCD (Greatest Common Divisor) を求めるものがあります。ユークリッドの互除法と呼ばれ、最も古いアルゴリズムとされています。

次のアルゴリズムを実装して、コマンドライン引数から二つの正の整数を受け取り、それらの最大公約数を求めるアプリケーションを作成してください。

1. 整数mとnの剰余rを求める
2. rが0であれば、nが答えである。
3. mにnを代入、 nにrを代入して1に戻る。

ヒント

例えば、m==100とn==10であれば、m%n = 0なので、n==10が答えです。m==65, n==78であれば、各ステップごとに、次のようになります。

 m,  n,  r
65, 78, 65  <- 0が立って余りは65
78, 65, 13  <- 1が立って余りは13
65, 13,  0  <- 5が立って余りは 0
--------------
最大公約数：13

数学的帰納法を用いて証明してみてください。

次の、while文による実装例のx部分を埋めて完成させてください。

class Exam09 {
	public static void main(String[] args) {
		// 引数をint型に変換
		int m = Integer.parseInt(args[0]);
		int n = Integer.parseInt(args[1]);
		// 余りを代入する変数
		int r = 0;
		System.out.println(" m,\t n,\t r");

		// ユークリッド互除法
		while (n xx 0) {	// <= change
			r = xxx;    	// <= change
			System.out.println(m + ",\t" + n + ",\t" + r);
			x = x;      	// <= change
			x = x;      	// <= change
		}
		System.out.println("gcd(" + args[0] + ", "
			+ args[1] + ") = " + x);	// <= change
	}
}

実行結果

C:\java>javac Exam09.java

C:\java>java Exam09 100 10
 m,      n,      r
100,    10,     0
gcd(100, 10) = 10

C:\java>java Exam09 65 78
 m,      n,      r
65,     78,     65
78,     65,     13
65,     13,     0
gcd(65, 78) = 13

C:\java>java Exam09 99991 433
 m,      n,      r
99991,  433,    401
433,    401,    32
401,    32,     17
32,     17,     15
17,     15,     2
15,     2,      1
2,      1,      0
gcd(99991, 433) = 1

回答例9

演習10

for 文と if 文を使って次の出力が得られるアプリケーションを作成してください。

*
**
* *
*  *
*   *
*    *
*     *
********

ヒント

考え方の問題です。出力時には、斜めに出力することはできず、行毎に出力されます。

最初は、中抜きしない三角形を出力してみてください。中抜きしない三角形が出力されたら、if 文を使って、各行の最初と最後のカラムにだけ出力してみてください。考え方は次のようになります。

• 3行目ならば、第1カラムに*、第3カラムに*、他のカラムはスペース1つ、
• 4行目ならば、第1カラムに*、第4カラムに*、他のカラムはスペース1つ、
• 5行目ならば、第1カラムに*、第5カラムに*、他のカラムはスペース1つ、
• i行目ならば、第1カラムに*、第iカラムに*、他のカラムはスペース1つ、

規則性が現れるとき、ループが使えます。for ループと if 文を組み合わせて、上記の三角形を出力してみてください。

回答例10

演習11

グー、チョキ、パーの入力に対して、じゃんけんするプログラムを作成してください。

プログラム内部では、乱数を利用してください。次のコード断片は、[0.0, 1.0) （0.0以上、1.0未満）の乱数 x を生成します。

double x = Math.random();

回答例11

演習の回答例

気が向いたら載せます。

回答例1

演習1の回答例です。

基準値の 35 を a、差分の 10 を b、引数を x に代入して処理します。

図：演習1の概念図

Exam01.java:

class Exam01 {
	public static void main(String[] args) {
		int x = Integer.parseInt(args[0]);
		int a = 35;
		int b = 10;
		if (x == a) {
			System.out.println("正解");
		} else if (x - a + b <= 0) {
			System.out.println("小さい");
		} else if (0 < x - a + b && x - a < 0) {
			System.out.println("少し小さい");
		} else if (0 < x - a && x - a - b < 0) {
			System.out.println("少し大きい");
		} else if (a + b - x <= 0) {
			System.out.println("大きい");
		}
	}
}

実行結果は次のようになります。

C:\java>javac Exam01.java
C:\java>java Exam01 10
小さい
C:\java>java Exam01 25
小さい
C:\java>java Exam01 26
少し小さい
C:\java>java Exam01 35
正解
C:\java>java Exam01 36
少し大きい
C:\java>java Exam01 45
大きい
C:\java>java Exam01 50
大きい
C:\java>java Exam01 a
Exception in thread "main" java.lang.NumberFormatException: For input string: "a"
        at java.lang.NumberFormatException.forInputString(Unknown Source)
        at java.lang.Integer.parseInt(Unknown Source)
        at java.lang.Integer.parseInt(Unknown Source)
        at Exam01.main(Exam01.java:3)
C:\java>java Exam01
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
        at Exam01.main(Exam01.java:3)
C:\java>

最初は目的通りに動くことを目指してください。ここまでブレークダウンできなくても結構です。

演習1補題

ここまでコーディングできたら、改造してみてください。例えば、等しい場合を含めた 5 つの領域は排他的なので、最後の評価式 a + b - x <= 0 は無駄であり、else if ではなく、else で十分です。また、全ての領域を並列な else if で結んでいますが、最初に 35 より大きい／小さいで振り分けて、その内部に差異が 10 未満／以上という if ブロックを含むようにすれば、実行時の評価回数を減らせます。

これができたら、機能的にも変更してみてください。例えば、引数が与えられない場合、引数が数値で無い場合の例外処理を追加してください。

回答2

演習2の回答例です。

いろいろな方法で実装可能でしょう。ここでは、一つの例として、次のコードを載せておきます。

class Exam02 {
	public static void main(String[]args) {
		int a = Integer.parseInt(args[0]);
		int b = Integer.parseInt(args[1]);
		int c = Integer.parseInt(args[2]);
		int val1 = 8, val2 = 0, val3 = 6, score = 0;
		
		if (a == val1) {
			score += 1;
		}
		if (b == val2) {
			score += 1;
		}
		if (c == val3) {
			score += 1;
		}
		
		if (score == 0) {
			System.out.println("アウト");
		} else if (score == 1) {
			System.out.println("ヒット");
		} else if (score == 2) {
			System.out.println("ツーベース");
		} else if (score == 3) {
			System.out.println("ホームラン");
		}
	}
}

実行結果

C:\java>javac Exam02.java
C:\java>java Exam02
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
        at Exam02.main(Exam02.java:3)
C:\java>java Exam02 1 2 3
アウト
C:\java>java Exam02 1 0 3
ヒット
C:\java>java Exam02 8 0 3
ツーベース
C:\java>java Exam02 8 0 6
ホームラン
C:\java>

演習2補題

この類のゲームは、いくらでも複雑にすることができます。

この演習では、三つの数字の並び順で、同じ場所でないとスコアが上がりませんでしたが、8, 0, 6の何れかに該当すれば、スコアが上がるように変更してみてください。

例えば、引数 a, b, c に対して、a が 0, 6の何れかであればスコアが1つ上がり、8 であればスコアが 2 上がるようにします。このとき、全ての数字が場所も含めて当たると、最高得点は 6 点になります。

次に、他の数字と重複する場合は、スコアが上がらないようにしてみてください。例えば、0, 1, 0とすると、スコアは1 + 0 + 1で 2 点になりますが、このスコアは 1 点になるようにしてみてください。また、0, 0, 0の場合は、場所があっているものが一つ存在するので、スコアが 2 点になるようにしてみてください。

回答5

演習5の回答例です。

ループと条件分岐を組み合わせて可能です。while, do-while, forを使って実装してみてください。ここでは、for 文の繰り返し終了条件を使って for ループのみで作成しています。

class Exam05 {
	public static void main(String[] args) {
		int x = 0, i = 0;
		for (i = 0; x <= 10000; i++) {
			x += i;
		}
		// 繰り返し条件式がfalseになった後で、
		// 更新文が一回実行されるので、(i-1)としている。
		// 最後に足す数は、141が正解。
		System.out.println("i = " + (i - 1) + "; x = " + x);
	}
}

演習5補題

別法として、等差数列の和の公式を利用することができます。

初項を a、公差を b、項の数を n、末項を l 、和を S とすると、和の公式は次のようになります。

図：等差数列の和の公式

等差数列の和の公式の求め方は説明しません。高校数学程度でも、結構面白い話題はあるのです。興味を持ったら、インターネットで検索してみてください。証明を解説したページが沢山見つかります。

このように、要件をコンピュータに解決可能な問題として整理したものを、アルゴリズムと呼びます。公式自体は高校数学ですが、プログラムでどう実装するかが腕の見せ所です。

等差数列の和の公式を使えば、ループを使わなくてすみます。計算量を格段に減らすことができます。この問題の場合は、10000 だけが決まっていて、未知数が n と l の二つ存在するので解けないようですが、n と a と b が決まっていれば、 l は n, a, b で表現可能です。

S を 10000 として公式を逆に解いて小数点を繰り込んで項数 n （整数）を求め、和の公式に n を代入して x を求めてみましょう。

ループを使わず、x と l を出力するプログラムを作ってみてください。

回等例9

演習9の回答例です。

class Exam09 {
	public static void main(String[] args) {
		int m = Integer.parseInt(args[0]);
		int n = Integer.parseInt(args[1]);
		int r = 0;
		System.out.println(" m,\t n,\t r");
		System.out.println(m + ",\t" + n);
		while (n != 0) {
			r = m%n;
			System.out.println(m + ",\t" + n + ",\t" + r);
			m = n;
			n = r;
		} 
		System.out.println("gcd(" + args[0] + ", "
			+ args[1] + ") = " + m);
	}
}

とても簡単なアルゴリズムなので簡単なプログラムで記述できます。しかし、その内容は直感的には「何で？」って感じだと思うので、余力のある方は、数学的帰納法を使って証明してみてください。

補題1. 本題のコードの、do文版とfor文版を作って、最大公約数と最小公倍数を求めてください。

AとBの最大公約数 (GCM)をG、最小公倍数 (LCM) をLとすると、次の式が成り立ちます。

A = a * G, B = b * G, L = a * b * G. => L = A * B / G.

まず最大公約数を求めてから、最小公倍数を求めることができます。

補題2. 互除法部分を別のメソッドにして再帰的に呼び出すことでループ部分を実装してください。

自分自身を呼び出す処理を、「再起的」 (recursive) と表現します。次のコードのx部分を埋めて完成させてください。メソッドについては、次の章で詳しく説明します。メソッドに慣れていない方も、感じが掴めると思います。

class Exam09_20 {
	public static void main(String[] args) {
		int m = Integer.parseInt(args[0]);
		int n = Integer.parseInt(args[1]);
		// 互除法メソッド呼び出し
		euclid(m,n);
	}

	// 互除法メソッド
	static void euclid(int m, int n) {
		System.out.println("m = " + m + ", n = " + n);
		if (x xx x) {	// <= change
			// 再起的呼び出し
			euclid(x, xxx);	// <= change
		} else {
			System.out.println("gcd = " + m);
		}
	}
}

補題3. このアルゴリズムで、指定した値以下の素数を見つけるアプリケーションを作成してください。

gcd が 1 となる m, n は互いに素です。素数である m は、n < m である任意の n と互いに素であるはずです。

難しいかもしれません。基本的には、ループを入れ子にして実装します。外側のループは、m を 1 から指定した値までループさせます。内側のループは、n を 1 から m - 1 までループさせて、どれか一つでも gcd が 1 でない n があれば m は素数ではありません。逆に、全ての n について 1 以外の gcd がなければ m は素数です。因みに 1 自体は素数とは呼びません。

実行結果例：

C:\java>java Exam09_30 100
1 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
elapsed time: 0.015 [sec]

C:\java>java Exam09_30 1000
1 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 101 103
 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211
 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331
 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449
 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587
 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709
 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853
 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991
 997
elapsed time: 0.031 [sec]

C:\java>java Exam09_30 10000
...
8951 8963 8969 8971 8999 9001 9007 9011 9013 9029 9041 9043 9049 9059 9067 9091 
9103 9109 9127 9133 9137 9151 9157 9161 9173 9181 9187 9199 9203 9209 9221 9227 
9239 9241 9257 9277 9281 9283 9293 9311 9319 9323 9337 9341 9343 9349 9371 9377 
9391 9397 9403 9413 9419 9421 9431 9433 9437 9439 9461 9463 9467 9473 9479 9491 
9497 9511 9521 9533 9539 9547 9551 9587 9601 9613 9619 9623 9629 9631 9643 9649 
9661 9677 9679 9689 9697 9719 9721 9733 9739 9743 9749 9767 9769 9781 9787 9791 
9803 9811 9817 9829 9833 9839 9851 9857 9859 9871 9883 9887 9901 9907 9923 9929 
9931 9941 9949 9967 9973
elapsed time: 1.109 [sec]

C:\java>java Exam09_30 100000
...
98899 98909 98911 98927 98929 98939 98947 98953 98963 98981 98993 98999 99013 
99017 99023 99041 99053 99079 99083 99089 99103 99109 99119 99131 99133 99137 
99139 99149 99173 99181 99191 99223 99233 99241 99251 99257 99259 99277 99289 
99317 99347 99349 99367 99371 99377 99391 99397 99401 99409 99431 99439 99469 
99487 99497 99523 99527 99529 99551 99559 99563 99571 99577 99581 99607 99611 
99623 99643 99661 99667 99679 99689 99707 99709 99713 99719 99721 99733 99761
99767 99787 99793 99809 99817 99823 99829 99833 99839 99859 99871 99877 99881 
99901 99907 99923 99929 99961 99971 99989 99991
elapsed time: 99.125 [sec]

"elapsed time" は、次のコードで求めています。

class Exam09_30 {
	public static void main(String[] args) {
		// 開始時刻
		long start = System.currentTimeMillis();
		...
		// 終了時刻
		long end = System.currentTimeMillis();
		// 終了時刻と開始時刻の差を出力。単位はミリ秒。
		System.out.println("elapsed time: " + (end - start)/1000.0 + " [sec]");
	}
}

ここで挙げた実行例は、 1 <= n < m である全ての n に対して、 1 から順番に gcd を求めていき、1 以外の gcd が得られたら以降の n の処理は実施せずに次の m のチェックに移るというアルゴリズムの実装です。十万以上だと出力結果が大きくなり、時間も掛かります。私のPCでは、10000以下で1.109秒、100000以下で99.125秒です。java.io をご存知の方は、テキストファイルに書き出してみてください。

素数とだけチェック

上の結果は、指定された値以下の m の各々に対して、単純に n < m の全ての n と素であることを順番に試しました。しかし、素数とだけ素であれば良いはずです。そのためには、それまでに計算した素数を配列に蓄えておき、それらの配列要素と素であるかをチェックし、求まっている最大の素数から m までの間だけ 1 刻みで素であるかどうかチェックします。値が大きくなるほど、時間短縮効果も大きくなります。

例えば、 m = 23 であれば、既に求まっている素数
	1 2 3 5 7 11 13 17 19
の各々と素であるかどうかをチェックし、19より大きい数については、
	20 21 22
と素であるかどうかを試します。

私が実装したところ、10000以下で0.203秒、100000以下で10.359秒くらいになりました。

C:\java>java Exam09_31 10000
...
9803 9811 9817 9829 9833 9839 9851 9857 9859 9871 9883 9887 9901 9907 9923 9929
9931 9941 9949 9967 9973
elapsed time: 0.203 [sec]

C:\java>java Exam09_31 100000
...
99767 99787 99793 99809 99817 99823 99829 99833 99839 99859 99871 99877 99881
99901 99907 99923 99929 99961 99971 99989 99991
elapsed time: 10.359 [sec]

平方根未満の素数とだけチェック

更に高速化するに当たり、チェックする n の値を判定対象の m までではなく、m の平方根までに制限することが考えられます。もし m = x*y であるときに x と y が何れも素数だとすると、何れか一方は必ず平方根よりも小さくなければならないからです。何れも平方根より大きければ、平方根の二乗よりも必ず大きくなりますよね？

平方根は、public static double StrictMath.sqrt(double a) で計算できます。

というわけで実装した実行結果が次のものです。

C:\java>java Exam09_32 10000
...
9803 9811 9817 9829 9833 9839 9851 9857 9859 9871 9883 9887 9901 9907 9923 9929 
9931 9941 9949 9967 9973
elapsed time: 0.109 [sec]

C:\java>java Exam09_32 100000
...
99767 99787 99793 99809 99817 99823 99829 99833 99839 99859 99871 99877 99881 
99901 99907 99923 99929 99961 99971 99989 99991
elapsed time: 1.046 [sec]

C:\java>java Exam09_32 1000000
...
999521 999529 999541 999553 999563 999599 999611 999613 999623 999631 999653 
999667 999671 999683 999721 999727 999749 999763 999769 999773 999809 999853 
999863 999883 999907 999917 999931 999953 999959 999961 999979 999983
elapsed time: 15.203 [sec]

C:\java>java Exam09_32 10000000
...
9999071 9999083 9999161 9999163 9999167 9999193 9999217 9999221 9999233 9999271 
9999277 9999289 9999299 9999317 9999337 9999347 9999397 9999401 9999419 9999433 
9999463 9999469 9999481 9999511 9999533 9999593 9999601 9999637 9999653 9999659 
9999667 9999677 9999713 9999739 9999749 9999761 9999823 9999863 9999877 9999883 
9999889 9999901 9999907 9999929 9999931 9999937 9999943 9999971 9999973 9999991
elapsed time: 286.094 [sec]

C:\java>java Exam09_32 100000000
...
99998909 99998929 99998933 99998953 99998971 99998999 99999043 99999073 99999077 
99999079 99999089 99999103 99999113 99999131 99999157 99999167 99999187 99999217
99999247 99999257 99999259 99999307 99999323 99999329 99999343 99999353 99999373
99999401 99999437 99999439 99999481 99999509 99999517 99999539 99999541 99999547 
99999551 99999563 99999587 99999589 99999611 99999617 99999623 99999643 99999677 
99999703 99999721 99999773 99999787 99999821 99999827 99999839 99999847 99999931 
99999941 99999959 99999971 99999989
elapsed time: 6133.297 [sec]

この例では、コンソールに書き出しているので、I/Oによる遅延が無視できないものになっています。配列に蓄えているので、都度書き出さないで、計算が全て終了後にバッファを持ったjava.ioでファイルに書き出したり、素数判定として入力数値が素数であるかどうかを判定するだけにすれば、全く同じコードでも高速化されます。

最後の出力例では、平方根の計算をニュートン法で高速化したり、演算子 % を使わないで剰余を高速化する方法もあります。四則演算の計算の高速化の例として、高速フーリエ変換 (FFT) について調べてみてください。

それでも、これ以上の劇的な高速化はこのアルゴリズムを使っている限り望めません。エラトステネス (Eratosthenes) のふるい、素数定理による統計処理やゴールドバッハ予想など、より高速な判定法がいろいろあるので、余力のある方は調べて実装してみてください。また、int 型だと 32bit （2**31 - 1 = 2,147,483,647。これは素数）、long 型だと 64bit （2**63 - 1 = 9,223,372,036,854,775,807。これは7で割り切れるので素数でない。）までしか表現できないので、64bit 以上の数まで判定できるようになったら、クラス BigInteger, BigDecimal を使ってみてください。

補題4. 拡張ユークリッド互除法を実装してください。

拡張ユークリッドの互除法によれば、「gcd(m, n) = c であるとき、am + bn = c である a と b が存在する」ので、m と n を入力として a, b, c を求めるアプリケーションを作成してください。アルゴリズムは次のようになります。

1. b = 1, a2 = b, b2 = 0, a = b2
2. m = n*q + r となる q, r を求める。
3. r = 0 であれば終わり。a*m + b*n = c.
4. m = n, n = r, t = a2, a2 = a, a = t - q*a, t = b2, b2 = b, b = t - q*b.
5. 2 に戻る。

実行結果例

C:\java>java Exam09_40 678 66
 m,      n,      r,      q,      a,      a2,     b,      b2
678,    66,     0,      0,      0,      1,      1,      0

678,    66,     18,     10,     1,      0,      -10,    1
66,     18,     12,     3,      -3,     1,      31,     -10
18,     12,     6,      1,      4,      -3,     -41,    31
12,     6,      0,      2
4*678 + -41*66 = 6

C:\java>java Exam09_40 1995 238
 m,      n,      r,      q,      a,      a2,     b,      b2
1995,   238,    0,      0,      0,      1,      1,      0

1995,   238,    91,     8,      1,      0,      -8,     1
238,    91,     56,     2,      -2,     1,      17,     -8
91,     56,     35,     1,      3,      -2,     -25,    17
56,     35,     21,     1,      -5,     3,      42,     -25
35,     21,     14,     1,      8,      -5,     -67,    42
21,     14,     7,      1,      -13,    8,      109,    -67
14,     7,      0,      2
-13*1995 + 109*238 = 7

拡張してもアルゴリズム自体は簡単です。腕試しの積りで挑戦してみてください。結構、あっけなく実装できるかもしれません。

アルゴリズムは簡単ですが、これも直感的には「はぁ？」って感じです。直感的に理解するために、手で計算してみます。例えば、678と66であれば、次のようになります。

ユークリッドの互除法
 m,      n,      r,      q
---------------------------
678,    66,     18,     10	=> 678 - 66*10 = 18	(1)
66,     18,     12,     3	=>  66 - 18*3  = 12	(2)
18,     12,     6,      1	=>  18 - 12*1  =  6	(3)
12,     6,      0,      2	=>  12 - 6*2   =  0	(4)
gcd(678, 66) = 6

拡張ユークリッドの互除法
(2),(3) => 18 - 12*1  =  6       	<- 12 に (2) を代入
           18 - (66 - 18*3)*1 = 6
           18 - 66*1 + 18*3*1 = 6	<- 18 で括る
           18*(1 + 3*1) - 66*1 = 6
           18*4 + 66*(-1) = 6	(5)
(1),(5) => 18*4 + 66*(-1) = 6         	<- 18 に (1) を代入
           (678 - 66*10)*4 + 66*(-1) = 6
           678*4 - 66*10*4 + 66*(-1) = 6	<- 66 で括る
           678*4 + 66*(-10*4 - 1) = 6
           678*4 + 66*(-41) = 6.	(6)
           ( m*a +  n*b  = c )

一般論としては次のようになります。

ユークリッドの互除法より、
	mi+1 = ni, ni+1 = ri,
	mi = ni*qi + ri.
mi, ni を ri で書くと、
	ri-2 = ri-1*qi + ri
	  =>  ri-2 - ri-1*qi = ri.
ここで、ai*m + bi*n = ri となることを仮定すると、
	ai-2*m + bi-2*n - (ai-1*m + bi-1*n)*qi = ri
	  =>  (ai-2 - ai-1*qi)*m + (bi-2 - bi-1*qi)*n = ri.
仮定した式と比べると、
	ai = ai-2 - ai-1*qi,
	bi = bi-2 - bi-1*qi.

r_i = gcd(m, n) となる i まで続けると、am + bn = c となる a と b が求まります。

次の3項間漸化式をアルゴリズムまで整理したのが、補題4の最初に挙げた5つのステップです。

ユークリッドの互除法
	mi = ni*qi + ri
	mi+1 = ni
	ni+1 = ri
拡張用の補助数
	ai+1 = ai-1 - qi+1*ai
	bi+1 = bi-1 - qi+1*bi

数学的帰納法を用いて証明してみてください。

回答例10

演習10の回答例です。

最初に、中抜きしない場合の回答例を挙げます。

public class Exam10 {
	public static void main(String args[]){
		int MAX = 9;
		for (int i = 0; i < MAX; i++) {
			System.out.print(i + ": ");
			for (int j = 0; j < i; j++) {
				System.out.print("*");
			}
			System.out.println();
		}
	}
}

これを改造して、中抜きするようにしてみましょう。条件分岐により、最後の行を特別扱いします。それ以外の行の中では、第一カラムと最終カラムを特別扱いします。

public class Exam10_20 {
	public static void main(String args[]){
		int MAX = 9;
		for (int i = 0; i < MAX; i++) {
			System.out.print(i + ": ");
			for (int j = 0; j < i; j++) {
				if (i == MAX - 1) {
					// 最終行
					System.out.print("*");
				} else {
					if (j == 0) {
						// 第一カラム
						System.out.print("*");
					} else if (j == i - 1) {
						// 最終カラム
						System.out.print("*");
					} else {
						// それ以外
						System.out.print(" ");
					}
				}
			}
			System.out.println();
		}
	}
}

不要な if 文があれば除去するように工夫してみてください。より美しく書き換えられないか、検討してみてください。

演習10補題

次の出力が得られるプログラムを作成してください。

*
**
* *
*  *
*   *
*    *
*     *
********
      * *
     *   *
    *     *
   *       *
  *         *
 *           *
***************

回答例11

演習11の回答例です。

単純に考えると、グー、チョキ、パーを整数に置き換えて、乱数を整数に直したものを3で割った余り（3の法）と比較します。

class Exam11 {
	public static void main(String[] args) {
		int x = 0, y = 0;
		if (args[0].equals("グー")) {
			x = 0;
		} else if (args[0].equals("チョキ")) {
			x = 1;
		} else if (args[0].equals("パー")) {
			x = 2;
		} else {
			System.out.println("エラー");
		}
	
		// [0,10)の乱数を生成して3の法をとる
		y = (int)(Math.random() * 10.0) % 3;
		if (x == 0) {
			if (y == 0) {
				System.out.println("あいこ");
			} else if (y == 1) {
				System.out.println("勝ち");
			} else if (y == 2) {
				System.out.println("負け");
			}
		} else if (x == 1) {
			if (y == 1) {
				System.out.println("あいこ");
			} else if (y == 2) {
				System.out.println("勝ち");
			} else if (y == 0) {
				System.out.println("負け");
			}
		} else if (x == 2) {
			if (y == 2) {
				System.out.println("あいこ");
			} else if (y == 0) {
				System.out.println("勝ち");
			} else if (y == 1) {
				System.out.println("負け");
			}
		}
	}
}

実行結果

C:\java>javac Exam11.java
C:\java>java Exam11 グー
あいこ
C:\java>java Exam11 グー
あいこ
C:\java>java Exam11 グー
勝ち
C:\java>java Exam11 グー
負け
C:\java>

switch 構造を使ったり、for ループでコードの行数を少なくしたりすることも可能でしょう。いろいろ工夫してみてください。

そのような工夫の一方で、実際にはじゃんけんの勝ち負け判定部分のロジックは不要です。というのも、じゃんけんの勝敗は 1/3 なので、実際に判定しなくても、1/3 の確率で、「勝ち」、「負け」、「あいこ」と出力するだけでも、目的を達成できるはずです。ずるいようですが、処理量を少なくするためには、このような考え方の変更も必要となります。

class Exam11_20 {
	public static void main(String[] args) {
		int y = (int)(Math.random()*10.0)%3;
		if (y == 0) {
			System.out.println("勝ち");
		} else if (y == 1) {
			System.out.println("負け");
		} else if (y == 2) {
			System.out.println("あいこ");
		}
	}
}

<<PREV | ToC | NEXT>>