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

Size: px

Start display at page:

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

もえりおいもり
5 years ago
Views:

1 第 1 章基本的 1 n

2 三値最大値 algorithm List 1-1 a, b, c max /* */ #include <stdio.h> int main(void) { int a, b, c; int max; /* */ List 1-1 printf("\n"); printf("a"); scanf("%d", &a); printf("b"); scanf("%d", &b); printf("c"); scanf("%d", &c); max = a; if (b > max) max = b; if (c > max) max = c; printf("%d\n", max); return 0; a, b, c max chap01/max3.c 実行例 a1 Ÿ b3 Ÿ c2 Ÿ 3 a, b, c max max a b max max b c max max c concatination if ( ) if selection

3 15 + > operator operandb max b > max > b max unary operator a++ binary operator a < b ternary operator a? b : c 1-1 Column 1-1 演算子 / 式評価 expression x = n x n int x, n, 135, n + 135, x = n x n x = n assignment expression void evaluation Fig.1C-1 int n 52 n 52 n, 135, n , 135, 187 int int 52 int 135 n int 187 Fig.1C-1 int + int

4 161 flowchart Fig.1-1 p.24 max = a; if (b > max) max = b; if (c > max) max = c; a max b > max Yes b > c > a No b max c > max Yes No c max Fig b > max c > max b > max c > max 1 if while ( ) if a max a max List 1-2p.18 int max = a; max = a;

5 17 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 関係演算子等価演算子 <, <=, >, >= ==,!= int 1 int 0 Fig.1C-2 5 > 3 int 1 a 5 == 3 int 0 bc int int a int > int b int == int c double < double 5 > 3 5 == < 3.2 int 1 int 0 int 0 Fig.1C-2

6 List 1-2 List 1-2 /* */ #include <stdio.h> /*--- a, b, c ---*/ int max3(int a, int b, int c) { int max = a; /* */ if (b > max) max = b; if (c > max) max = c; return max; int main(void) { printf("max3(%d,%d,%d) = %d\n", 3, 2, 1, max3(3, 2, 1)); /* [A] abc */ printf("max3(%d,%d,%d) = %d\n", 3, 2, 2, max3(3, 2, 2)); /* [B] abc */ printf("max3(%d,%d,%d) = %d\n", 3, 1, 2, max3(3, 1, 2)); /* [C] acb */ printf("max3(%d,%d,%d) = %d\n", 3, 2, 3, max3(3, 2, 3)); /* [D] acb */ printf("max3(%d,%d,%d) = %d\n", 2, 1, 3, max3(2, 1, 3)); /* [E] cab */ printf("max3(%d,%d,%d) = %d\n", 3, 3, 2, max3(3, 3, 2)); /* [F] abc */ printf("max3(%d,%d,%d) = %d\n", 3, 3, 3, max3(3, 3, 3)); /* [G] abc */ printf("max3(%d,%d,%d) = %d\n", 2, 2, 3, max3(2, 2, 3)); /* [H] cab */ printf("max3(%d,%d,%d) = %d\n", 2, 3, 1, max3(2, 3, 1)); /* [I] bac */ printf("max3(%d,%d,%d) = %d\n", 2, 3, 2, max3(2, 3, 2)); /* [J] bac */ printf("max3(%d,%d,%d) = %d\n", 1, 3, 2, max3(1, 3, 2)); /* [K] bca */ printf("max3(%d,%d,%d) = %d\n", 2, 3, 3, max3(2, 3, 3)); /* [L] bca */ printf("max3(%d,%d,%d) = %d\n", 1, 2, 3, max3(1, 2, 3)); /* [M] cba */ return 0; chap01/max3comb.c 実行結果 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], [B],, [M] Fig.1C-4p.20A, ʙ,, M function max3 int a, b, c int main max3 Column Column 1-4p.20

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

8 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 a, b, c List 1-2 A, ʙ,, M 13 List 1C-1 return A, ʙ,, MFig.1C-4

9 21List 1C-1 /* */ #include <stdio.h> /*--- a, b, c ---*/ 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 int main(void) { int a, b, c; chap01/med3.c 実行例 a1 Ÿ b3 Ÿ c2 Ÿ printf("\n"); printf("a"); scanf("%d", &a); printf("b"); scanf("%d", &b); printf("c"); scanf("%d", &c); printf("%d\n", med3(a, b, c)); return 0; List 1-2 List 1C List 1C-1 med3 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 221 条件判定分岐 List 1-3 /* */ #include <stdio.h> int main(void) { int n; List 1-3 printf(""); scanf("%d", &n); if (n > 0) printf("\n"); else if (n < 0) printf("\n"); else printf("\n"); return 0; ㆒ ㆓ 叅 chap01/sign.c 実行例㆒ 5 Ÿ 実行例㆓ -5 Ÿ 実行例叅 0 Ÿ Fig.1-3 n ㆒ ㆓ 0 叅 "chap01/if123a.c" ㆒,, n No Yes n No ㆒㆓ Yes 叅 Fig.1-3 n

11 23if (n == 1) printf("\n"); else if (n == 2) printf("\n"); else if (n == 3) printf("\n"); n 1 ㆒ 2 ㆓ 3 叅 ㆒ ㆓ 叅 if if () else if () else List 1-3 "chap01/if123b.c" n Ÿ 叅 if "chap01/if123c.c" 1-1 if (n == 1) printf("\n"); ㆒ else if (n == 2) printf("\n"); ㆓ else if (n == 3) printf("\n"); 叅 else ; /* */ 4 4 List 1-3 if Column 1-5 条件演算子? : conditional operator conditional expressionfig.1c-5 min = a < b? a : b; min a b a b 1? 2 : 3 1 a true 2 b false 3 a a29b52 a < b? a : b b a31b15 a < b? a : b int 29 int 15 Fig.1C-5

12 241 ( 流図 ) 記号 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 25 端 (loop limit) Fig.1-8 Fig.1-9 a Fig.1-8 b 1-1 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-4 Fig.1-12 /* 1, 2,, nwhile*/ #include <stdio.h> int main(void) { int i, n; int sum; /* */ puts("1n"); printf("n"); scanf("%d", &n); sum = 0; i = 1; List 1-4 while (i <= n) { /* in */ sum += i; /* sumi */ i++; /* i */ printf("1%d%d\n", n, sum); return 0; ㆒ ㆓ chap01/sum_while.c 実行例 1n n5 Ÿ 1515 while 文繰返 repetitionloop while 4 while 0 while ( )

15 27 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 281 for 文繰返 while for 1 n for List 1-5 List 1-5 /* 1, 2,, nfor*/ #include <stdio.h> int main(void) { int i, n; int sum; /* */ puts("1n"); printf("n"); scanf("%d", &n); sum = 0; for (i = 1; i <= n; i++) { /* i = 1, 2,, n */ sum += i; /* sumi */ printf("1%d%d\n", n, sum); chap01/sum_for.c 実行例 1n n5 Ÿ 1515 return 0; 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 29for for ( 1 ; 2 ; 3 ) for while /*--- for ---*/ /*--- while ---*/ for ( 1 ; 2 ; 3 ) 1 ; while ( 2 ) { 3 ; for List 1-5 n = (1 + 10) * 5 1 n 1-9 a, b int sumof(int a, int b); a b a 3 b 5 12 a 6 b 4 15 Column 1-6 非真偽 Column 1-2p.17 int 1 int if (a) printf("abc"); a ABC

18 301 正値読込 List 1-5 n n List 1-6 /* 1, 2,, ndon*/ #include <stdio.h> int main(void) { int i, n; int sum; /* */ List 1-6 puts("1n"); do { printf("n"); n scanf("%d", &n); while (n <= 0); sum = 0; for (i = 1; i <= n; i++) { /* i = 1, 2,, n */ sum += i; /* sumi */ printf("1%d%d\n", n, sum); return 0; chap01/sum_for_pos.c 実行例 1n n-6 Ÿ n0 Ÿ n10 Ÿ n 0 n do do while ( ); while for ; do 4 ( ) Fig.1-14

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

20 321 構造化 structured programming Column 1-7 論理演算法則 p.30list 1-6 List 1C-2 List 1C-2 /* 1099 */ #include <stdio.h> int main(void) { int no; chap01/dbl_digits.c 実行例 5 Ÿ 105 Ÿ 57 Ÿ no57 printf("\n"); do { printf(""); scanf("%d", &no); while (no < 10 no > 99); printf("no%d\n", no); return 0; do List 1-6 no && Fig.1C-6 a x y x && y b x y x y Fig.1C-6

21 33 no 5 no < 10 1 no > 99 no < 10 no > 99 1 x y 0 x y 1 1 && short circuit evaluation 1-2! !(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-7 do { /* no */ while (no < 10 no > 99); do { /* no */ while (!(no >= 10 && no <= 99)); ㆒ ㆓ Yes! Yes No No Fig.1C-7

22 341 多重九九表 List 1-7 List 1-7 /* */ #include <stdio.h> int main(void) { int i, j; printf(" \n"); for (i = 1; i <= 9; i++) { for (j = 1; j <= 9; j++) printf("%3d", i * j); putchar('\n'); return 0; chap01/multi99table.c 実行結果 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 35 i : 1, 1, 9 i j i j j : 1, 1, 9 i * j Fig ' ' '-' '+' * 1-15 * 4 Ÿ **** **** **** **** 3 Ÿ 7 Ÿ ******* ******* *******

24 361 直角二等辺三角形表示 List 1-8 List 1-8 do n /* */ #include <stdio.h> int main(void) { int i, j, n; do { printf(""); scanf("%d", &n); while (n <= 0); for (i = 1; i <= n; i++) { for (j = 1; j <= i; j++) putchar('*'); putchar('\n'); return 0; chap01/trianglelb.c 実行例 5 Ÿ * ** *** **** ***** 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 * ***** 1 n i i '*' n n '*'

25 37 i : 1, 1, n i j n 5 i j j : 1, 1, i * Fig void trianglelb(int n); /* */ void trianglelu(int n); /* */ void triangleru(int n); /* */ void trianglerb(int n); /* */ 1-17 n 4 void spira(int n); i (i - 1) * '*' n (n - 1) * '*' * *** ***** ******* 1-18 n void nrpira(int n); i i %

26 381 章末問題 p 処理条件処理条件処理条件処理処理処理 while 条件処理条件条件処理処理条件処理処理処理条件処理処理処理処理

27 a データ ( 入出力 ) b 内部記憶 e 判断 f 定義済み処理 ( サブルーチン ) 1 c 処理 g ループ端 ( 繰返し ) d 並列処理 h 結合子 i 端子 a a NN 11 2 N x a 開始 0 x 1 i a No x + i x i + 1 i Yes 終了 i N i N i N x N

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

新・明解Javaで学ぶアルゴリズムとデータ構造第 1 章基本的 1 n 21 1-1 三値最大値 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("");