新・明解Javaで学ぶアルゴリズムとデータ構造

Size: px

Start display at page:

Download "新・明解Javaで学ぶアルゴリズムとデータ構造"

みいかむこやま
4 years ago
Views:

1 第 1 章基本的 1 n

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

3 3 Fig.1C-1 import java.util.scanner; a class A { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); b main stdin.nextint() c c 1-1 Column 1-1 数値文字列読込 (1) Fig.1C-1 a java.util Scanner Column 2-4p.42 b main csystem.in standard input stream c int stdin.nextint() Column 1-3p.7 Fig.1C-2 int -2,147,483,648 2,147,483,647 System.in stdin stdin stdin List 1-1 a, b, c c a = stdin.nextint(); nextint() stdin a System.in Fig.1C-2

4 41 flowchart Fig.1-1 p.12 max = a; if (b > max) max = b; if (c > max) max = c; a max b > c > a b > max Yes No b max c > max Yes No c max Fig b > max c > max b > max c > max true false if while ( ) if a max a max List 1-1 int max = a; Fig.1-1 max = a;

5 5 a, b, c 1, 3, 2 a, b, c 1, 2, 3 3, 2, 1 5, 5, 5 1, 3, 1 Fig.1-2 max = a; if (b > max) max = b; a a = 1 b = 3 c = 2 max 1 3 b a = 1 b = 2 c = 3 max 1 2 c a = 3 b = 2 c = 1 max 3 3 d a = 5 b = 5 c = 5 max 5 5 e a = 1 b = 3 c = 1 max if (c > max) max = c; Fig.1-2 max a, b, c 6, 10, 7-10, 100, 10 b c a Column 1-2 数値文字列読込 (2) Column 1-1 int Table 1C-1 Table 1C-1Scanner next... nextboolean() boolean true false nextbyte() byte nextshort() short nextint() int nextlong() long nextfloat() float E E-45 nextdouble() double E E-324 next() String nextline() String

6 List 1-2 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 // [A] abc // [B] abc // [C] acb // [D] acb // [E] cab // [F] abc // [G] abc // [H] cab // [I bac // [J] bac // [K] bca // [L] bca // [M] cba [A], [B],, [M] Fig.1C-4p.8 A, ʙ,, M method max3 int a, b, c int main max3 Column Column 1-4p.8

7 7 JISJapanese Industrial Standards static int max4(int a, int b, int c, int d) 1-2 static int min3(int a, int b, int c) 1-3 static int min4(int a, int b, int c, int d) p.iv Column 1-3 返却値呼出式評価 return max3 int max 4 4 max(3, 2, 1) Fig.1C-3 max(3, 2, 1) int 3 max(3, 2, 1) int 3 Fig.1C-3

8 81 13 Fig.1C-4 decision tree a b A a b c Yes b c ʙ No a b c C b c a c b a c D a c E a c b c a b a b F a b c b c ɢ b c ʜ a b c a b c a b ɪ b a c a c J b a c K a c b c a b c ʟ b c M b c a c b a Column 1-4 三値大小関係中央値 Fig.1C-4 a, b, c List 1-2 A, ʙ,, M 13 List 1C-1 return A, ʙ,, MFig.1C-4

9 9List 1C-1 // import java.util.scanner; class Median { static int med3(int a, int b, int c) { if (a >= b) if (b >= c) return b; A ʙ F ɢ else if (a <= c) return a; D E ʜ else return c; C else if (a > c) return a; ɪ else if (b > c) return c; J K else return b; ʟ M public static void main(string[] args) { Scanner stdin = new Scanner(System.in); Chap01/Median.java 実行例 a1 Ÿ b3 Ÿ c2 Ÿ System.out.println(""); System.out.print("a"); int a = stdin.nextint(); System.out.print("b"); int b = stdin.nextint(); System.out.print("c"); int c = stdin.nextint(); System.out.println("" + med3(a, b, c) + ""); List 1-2 List 1C List 1C-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 条件判定分岐 List 1-3 // import java.util.scanner; class JudgeSign { List 1-3 public static void main(string[] args) { Scanner stdin = new Scanner(System.in); System.out.print(""); int n = stdin.nextint(); if (n > 0) System.out.println(""); else if (n < 0) System.out.println(""); else System.out.println(""); ㆒ ㆓ 叅 Chap01/JudgeSign.java 実行例㆒ 5 Ÿ 実行例㆓ -5 Ÿ 実行例叅 0 Ÿ Fig.1-3 n ㆒ ㆓ 0 叅 "Chap01/Judge123A.java" ㆒,, n No Yes n No ㆒㆓ Yes 叅 Fig.1-3 n

11 11if (n == 1) System.out.println(""); else if (n == 2) System.out.println(""); else if (n == 3) System.out.println(""); n 1 ㆒ 2 ㆓ 3 叅 if if () else if () else List 1-3 "Chap01/Judge123B.java" 4 Ÿ n 叅 if "Chap01/Judge123C.java" ㆒ ㆓ 叅 1-1 if (n == 1) System.out.println(""); else if (n == 2) System.out.println(""); else if (n == 3) System.out.println(""); else ; // ㆒ ㆓ 叅 4 4 List 1-3 if Column 1-5 演算子 + - operator operand a > b > a b unary operator a++ binary operator a < b ternary operator a? b : c conditional operator? : Java a? b : c a true b false c ㆒ a = (x > y)? x : y; ㆓ System.out.println((c == 0)? "c" : "c"); ㆒x y a ㆓ c 0 c c

12 121 ( 流図 ) 記号 flowchart 流図 (program flowchart) (data) Fig.1-4 処理 (process) Fig.1-5 定義処理 (predefined process) Fig.1-6 Fig.1-4 Fig.1-5 判断 (decision) Fig.1-7 Fig.1-6 Fig.1-7

13 13 端 (loop limit) Fig.1-8 Fig.1-9 Fig a b i a, b, c i : 1, 1, n i : 1, 1, n Fig.1-9 ab i 1 n 1 n 1, 1, n 1, 2,, n 線 (line) Fig.1-10 Fig.1-10 端子 (terminator) Fig.1-11 Fig.1-11

14 繰返 1 n 整数和求 1 n n n n List 1-4Fig.1-12 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 Ÿ 1515 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 + ""); while 文繰返 repetitionloop while 4 while true while ( )

15 15 sum ㆒ ㆓ 1 i i n Yes sum + i sum i + 1 i No i sum i sum Fig n ㆒ ㆓ ㆒ sum 0 i 1 ㆓ i n i n += ++ i n i <= n i sum i sum ㆒ 1 0 i sum i i 5 sum i 5 4 i n while i n n List 1-4 while i n + 1 i

16 161 for 文繰返 while for 1 n 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); System.out.println("1n"); System.out.print("n"); int n = stdin.nextint(); Chap01/SumFor.java 実行例 1n n5 Ÿ 1515 int sum = 0; // for (int i = 1; i <= n; i++) sum += i; // sumi System.out.println("1" + n + "" + sum + ""); Fig.1-13 loop limit i 1, 2, 3, 1 n 1 sum += i; sum i : 1, 1, n sum + i sum i 1 n Fig n

17 17for for (for ; ; for ) for 4 true for List 1-5 n = (1 + 10) * a, b static int sumof(int a, int b) a b a 3 b 5 12 a 6 b 4 15 Column 1-6 for 文 for for for for for for for for for int i; for (i = 1; i <= n; i++) sum += i; // fori for for for (int i = 1; i <= 5; i++) sum += i; for (int i = 1; i <= 7; i++) System.out.println(i);

18 181 正値読込 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); n 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 ; do 4 ( ) true Fig.1-14

19 19 Yes n n n n 1-2 a b No n n Fig.1-14 ab ba do n 0 do n 前判定繰返後判定繰返相違点 while for false do 1-10 a, b b - a b a b a6 Ÿ b6 Ÿ a b8 Ÿ b - a

20 201 構造化 structured programming Column 1-7 論理演算法則 p.18list 1-6 List 1C-2 List 1C-2 // 1099 import java.util.scanner; class Digits { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); int no; Chap01/Digits.java 実行例 5 Ÿ 105 Ÿ 57 Ÿ no57 System.out.println(""); do { System.out.print(""); no = stdin.nextint(); while (no < 10 no > 99); System.out.println("no" + no + ""); do List 1-6 no && Fig.1C-5 a b x y x && y true true true true false false false true false false false false x y x y true true true true false true false true true false false false Fig.1C-5

21 21 no 5 no < 10 true no > 99 no < 10 no > 99 true x y true x y true true && false false false 4 4 short circuit evaluation 1-2! true false false true!(no >= 10 && no <= 99) 4 4 De Morgan's laws x && y!(!x!y) x y!(!x &&!y) no < 10 no > 99!(no >= 10 && no <= 99) Fig.1C-6 do { /* no */ while (no < 10 no > 99); do { /* no */ while (!(no >= 10 && no <= 99)); ㆒ ㆓ Yes! Yes No No Fig.1C-6

22 221 多重九九表 List 1-7 // public class Multi99Table { List 1-7 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-15 i j for 4 i for 4 j i j i 1 j * j i 2 j * j i 3 j * j i 9 j * j

23 23 i : 1, 1, 9 i j i j j : 1, 1, 9 i * j Fig ' ' '-' '+' * 5 Ÿ ***** ***** ***** ***** *****

24 241 直角三角形表示 List 1-8 List 1-8 do n // import java.util.scanner; public class TriangleLB { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); int n; System.out.println(""); Chap01/TriangleLB.java 実行例 5 Ÿ * ** *** **** ***** 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(); Fig.1-16 i j n 5 for 4 i 1 n 5 4 for 4 j 1 i 4 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 * *****

25 25 i : 1, 1, n i j n 5 i j j : 1, 1, i * Fig n i i '*' n n '*' 1-15 static void trianglelb(int n) // static void trianglelu(int n) // static void triangleru(int n) // static void trianglerb(int n) // 1-16 n 4 static void spira(int n) i (i - 1) * '*' n (n - 1) * '*' * *** ***** ******* 1-17 n static void npira(int n) i i %

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

明解Javaによるアルゴリズムとデータ構造 21 algorithm List 1-1 a, b, c max Scanner Column 1-1 List 1-1 // import java.util.scanner; class Max3 { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); Chap01/Max3.java