Javaによるアルゴリズムとデータ構造

Transcription

1

2 1 algorithm List 1-1 a, b, c List 1-1 // import java.util.scanner; class Max3 { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); int a, b, c; int max; // Chap01/Max3.java a1 Ÿ b3 Ÿ c2 Ÿ 3 System.out.println(""); System.out.print("a"); a = stdin.nextint(); System.out.print("b"); b = stdin.nextint(); System.out.print("c"); c = stdin.nextint(); max = a; if (b > max) max = b; if (c > max) max = c; System.out.println("" + max + ""); max a b max max b c max max c flowchart Fig if

3 max = a; if (b > max) max = b; if (c > max) max = c; 上から下へと流れていく 開始 a max b > max No Yes b max b > c> a である場合に通る経路 1-1 c > max Yes Fig.1-1 No c max 終 了 b > max c > max a max a max フローチャートの記号は p.8 で解説します a, b, c 1, 3, 2 a, b, c 1, 2, 3 3, 2, 1 5, 5, 5 5, 3, 5 a, b, c 6, 10, 7-10, 100, 10 b c a List 1-2a, b, c 3

4 1 List 1-2 Chap01/Max3m.java // class Max3m { //--- a, b, c ---// static int max3(int a, int b, int c) { int max = a; if (b > max) max = b; if (c > max) max = c; return max; // public static void main(string[] args) { System.out.println("max3(3,2,1) = " + max3(3,2,1)); System.out.println("max3(3,2,2) = " + max3(3,2,2)); System.out.println("max3(3,1,2) = " + max3(3,1,2)); System.out.println("max3(3,2,3) = " + max3(3,2,3)); System.out.println("max3(2,1,3) = " + max3(2,1,3)); System.out.println("max3(3,3,2) = " + max3(3,3,2)); System.out.println("max3(3,3,3) = " + max3(3,3,3)); System.out.println("max3(2,2,3) = " + max3(2,2,3)); System.out.println("max3(2,3,1) = " + max3(2,3,1)); System.out.println("max3(2,3,2) = " + max3(2,3,2)); System.out.println("max3(1,3,2) = " + max3(1,3,2)); System.out.println("max3(2,3,3) = " + max3(2,3,3)); System.out.println("max3(1,2,3) = " + max3(1,2,3)); max3(3,2,1) = 3 max3(3,2,2) = 3 max3(3,1,2) = 3 max3(3,2,3) = 3 max3(2,3,2) = 3 max3(1,3,2) = 3 max3(2,3,3) = 3 max3(1,2,3) = 3 // abc // abc // acb // acb // cab // abc // abc // cab // bac // bac // bca // bca // cba Column method max3 int a, b, c int ここでは 三値の最大値を求めるアルゴリズムが正しいことを 論理的に確認するとと もに プログラムの実行結果からも確認したわけです 四値の最大値を求めるメソッドを作成せよ ( もちろん それをテストするプログラム=クラスを作成しなければならない ) static int max4(int a, int b, int c, int d)

5 三値の最小値を求めるメソッドを作成せよ static int min3(int a, int b, int c) 四値の最小値を求めるメソッドを作成せよ static int min4(int a, int b, int c, int d) Column 1-1 三値の大小関係の組合せ 13 種類は 下図 によって列挙できます ( このような木を と呼びます ) 左端の枠から始めて 枠内 の条件が成立すれば上側の黒線を 成立しな ければ下側の青線をたどっていきます 右端 の枠内が大小関係です なお 最大値 最小値とは異なり 中央値 を求める手続きは複雑であり 右のようにな ります ( 各 return に与えられた注釈,, は下の図と対応しています ) static int med3(int a, int b, int c) { if (a >= b) if (b >= c) return b; else if (a <= c) return a; else return c; else if (a > c) return a; else if (b > c) return c; else return b; A B F G D E H C I J K L M 1-1 a b Yes No a>b a c b c b c a>c b c b>c a c b>c H c>a=b I b>a>c J b>a=c b>c M c>b>a A a>b>c B a>b=c a>c E c>a>b F a=b>c G a=b=c K b>c>a L b=c>a C a>c>b D a=c>b

6 1 List 1-3 Fig.1-2 List 1-3 // import java.util.scanner; class JudgeSign { Chap01/JudgeSign.java 5 Ÿ public static void main(string[] args) { Scanner stdin = new Scanner(System.in); System.out.print(""); int n = stdin.nextint(); -5 Ÿ if (n > 0) System.out.println(""); else if (n < 0) System.out.println(""); else System.out.println(""); 0 Ÿ n Fig.1-2 開 始 a n > max 0 No Yes それは正です a n < max 0 No Yes それは負です それは0です 終 了

7 if List 1-3 if (n == 1) System.out.println(""); else if (n == 2) System.out.println(""); else if (n == 3) System.out.println(""); n if if ( ) else if ( ) else List 1-3 n if 1-1 if (n == 1) System.out.println(""); else if (n == 2) System.out.println(""); else if (n == 3) System.out.println(""); else ; // List 1-3 if Column 1-2 プログラミング言語の世界では + や - などの演算を行う記号を(operator) と呼び 演算の対象となる式のことを(operand) と呼びます たとえば 大小関係の比較を行う式 a > b において 演算子は > であって オペランドは a と b です このように二つのオペランドをもつ演算子を(binary operator) と呼びます Java には 2 項演算子のほかにも オペランドが一つの(unary operator) と オペランドが三つの(ternary operator) があります? : 演算子は Java で唯一の3 項演算子です 式 a? b : c が評価されると 式 a を評価した値が真であれば b の値を生成し 偽であれば c の値を生成します

8 1 flowchart データ 処理 定義済み処理 判断

9 名前 名前 1-1 端子 List 1-2 を参考にして 三値の大小関係 13 種類すべてに対して中央値を求めて表 示するプログラムを作成せよ 中央値を求める手続きは 以下のようにも実現できるものの Column 1-1 中に 示した med3 と比較すると実行効率が悪い その理由を考察せよ static int med3(int a, int b, int c) { if ((b >= a && c <= a) (b <= a && c >= a)) return a; else if ((a > b && c < b) (a < b && c > b)) return b; return c;

10 101 1 n n n n Fig.1-3 List 1-4 Fig.1-3 開 始 0 sum 1 i ここを通過する際の i と sum の値の変化 i n Yes sum + i sum i + 1 i No i sum 終 了 while while ( 式 ) 文

11 11 List 1-4 // 1, 2,, nwhile import java.util.scanner; class SumWhile { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); Chap01/SumWhile.java 1n n5 Ÿ System.out.println("1n"); System.out.print("n"); int n = stdin.nextint(); int sum = 0; int i = 1; // while (i <= n) { // in sum += i; // sumi i++; // i System.out.println("1" + n + "" + sum + ""); true 文 while 文では 最初に を評価した結果が false であればループ本体は一度も実行され ません この点が を実現する do 文 (p.14) と大きく異なります sum 0 i 1 i n i n i n i sum 複合代入演算子 += は右辺の値を左辺に加えます 単項演算子である増分演算子 ++ はオ ペランドの値を一つ増やします i n while i n n + 1 List 1-4 の while 文終了時点における変数 i の値が n + 1 となることを確認せよ ( 変 数 i の値を表示するプログラムを作成せよ )

12 121 while for for List 1-5 List 1-5 // 1, 2,, nfor import java.util.scanner; class SumFor { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); Chap01/SumFor.java 1n n5 Ÿ 1515 System.out.println("1n"); System.out.print("n"); int n = stdin.nextint(); int sum = 0; // for (int i = 1; i <= n; i++) sum += i; // sumi System.out.println("1" + n + "" + sum + ""); Fig.1-4 loop limit Fig.1-4 開 始 0 sum 合計 i : 1, 1, n 合計 i : 1, 1, n sum + i sum i の値を 1 から始めて n になるまで一つずつ増やしながら繰り返す 終値増分初期値変数名 合計 終 了

13 13 i 1, 2, 3, 1 n 1 sum += i; Fig.1-5 for 1-2 for (for 初期化式 ; 式 1; 式 2) 文 for 初期化式 式 1 true 文 文 式 2 Fig.1-5 合計 i : 1, 2,, n sum + i sum 合計 for 初期化式 式 1 式 2 のいずれも省略でき ます ( セミコロンは省略できません ) また for 初期化式中で宣言された変数は その for 文の中でのみ利用できるものであり for 文の終了とともに消えてしまいます for 文の実行が終了した後にも値が必要で あれば 以下のように for 文に先立って変 数を宣言しなければなりません int i; for (i = 1; i <= n; i++) sum += i; List 1-5 のプログラムをもとにして たとえば n が 7 であれば 1 から 7 までの和は 28 です ではなくて = 28 と表示するプログラムを作成せよ ガウスの方法 ( たとえば 1 から 10 までの和であれば (1 + 10) * 5 によって求める ) を用いて和を求めるプログラムを作成せよ 整数 a, b を含め その間の全整数の和を求めて返す以下のメソッドを作成せよ static int sumof(int a, int b) なお a と b の大小関係に関係なく和を求めること たとえば a が 3 で b が 5 であれば 12 を a が 6 で b が 4 であれば 15 を返すこと

14 141 List 1-5 n n List 1-6 List 1-6 Chap01/SumForPos.java // 1, 2,, ndon import java.util.scanner; class SumForPos { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); int n; 1n n-6 Ÿ n0 Ÿ n10 Ÿ System.out.println("1n"); do { System.out.print("n"); n = stdin.nextint(); while (n <= 0); int sum = 0; // for (int i = 1; i <= n; i++) sum += i; // sumi System.out.println("1" + n + "" + sum + ""); n 0 n do do 文 while ( 式 ); while 文や for 文などとは異なり 構文の末尾にセミコロン ; が付きます

15 15 do Fig.1-6 Fig 読込み n を入力 n を入力 Yes n 0 No n > 0 読込み n の値は正になっている n の値は正になっている n 0 do n 右に示すように 二つの変数 a, b に整数値を読み込んで b - a の値を表示するプログラムを作成せよ なお 変数 b に読み込んだ値が a 以下であれば再入力させること a6 Ÿ b6 Ÿ a b8 Ÿ b - a2 正の整数値を読み込んで その値の桁数を表示するプログラムを作成せよ たとえば 135 を読み込んだら その数は 3 桁です と表示し 1314 を読み込んだら その数は 4 桁です と表示すること

16 161 List 1-7 List 1-7 // public class Multi99Table { public static void main(string[] args) { System.out.println(" "); for (int i = 1; i <= 9; i++) { for (int j = 1; j <= 9; j++) System.out.printf("%3d", i * j); System.out.println(); Chap01/Multi99Table.java Fig.1-7 i j for i 1 9 for j i 1 j * j i 2 j * j i 3 j * j 以下省略 i 1 9

17 17 Fig.1-7 開始 行ループ i : 1, 1, 9 列ループ j : 1, 1, 9 i * j を表示 列ループ 改行 行ループ 終了 変数 i と j の変化 i 1 j j の値を1から9まで増やして繰り返す 1-2 j 1 9 右のように 九九の表の上と左に 掛ける数を表示するプログラムを作成せよ 表示には マイナス記号 - プラス記号 + 縦 線記号 を用いること 九九の掛け算ではなく足し算を行う表を表示するプログラムを作成せよ 右図のように 読み込んだ段数を一辺としてもつ正方形 を * 記号で表示するプログラムを作成せよ 5 Ÿ ***** ***** ***** ***** *****

18 181 * List 1-8 Fig.1-8 List 1-8 Chap01/TriangleLB.java // import java.util.scanner; public class TriangleLB { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); int n; System.out.println(""); do { System.out.print(""); n = stdin.nextint(); while (n <= 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) System.out.print('*'); System.out.println(); 5 Ÿ * ** *** **** ***** n 5 for i 1 n for j 1 i i 1 j 1 1 * * i 2 j 1 2 * ** i 3 j 1 3 * *** i 4 j 1 4 * **** i 5 j 1 5 * ***** 1 n i i * n n *

19 19 Fig.1-8 開始 行ループ i : 1, 1, n 列ループ j : 1, 1, i * を表示 列ループ 改行 変数 i と j の変化 ( 変数 nの値が5である場合 ) i j j の値を1から i まで増やして繰り返す 1-2 行ループ 終了 直角三角形を表示する部分を独立させて 以下の形式のメソッドとして実現せよ static void trianglelb(int n) // さらに 直角が左上側 右上側 右下側の三角形を表示するメソッドを作成せよ static void trianglelu(int n) // static void triangleru(int n) // static void trianglerb(int n) // n 段のピラミッドを表示する関数を作成せよ ( 右図は 4 段の例 ) static void spira(int n) 第 i 行目には (i - 1) * 個の * 記号を表示して 最終行である第 n 行目には (n - 1) * 個の * 記号を表示すること * *** ***** ******* 右図のように n 段の数字ピラミッドを表示する関数を作成せよ static void npira(int n) 第 i 行目に表示する数字は i % 10 によって得られる