プログラミング論 I 2008年07月03日 2008年07月10日 2008年7月11日 関数，再帰

Presentation on theme: "プログラミング論 I 2008年07月03日 2008年07月10日 2008年7月11日 関数，再帰"— Presentation transcript:

1 プログラミング論 I 2008年07月03日 2008年07月10日 2008年7月11日 関数，再帰

2 FAQ： #defineとは？ 文字列を定義して，それ以降置換する． 置換 置換 置換 #define MAX 10
void main(){ int i=MAX; printf("%d\n", i); } void main(){ int i=10; printf("%d\n", i); } 置換 10/2*5は， 25です． 左から順に 計算 #define MAX 2*5 void main(){ int i=10/MAX; printf("%d\n", i); } void main(){ int i=10/2*5; printf("%d\n", i); } 置換 #define MAX (2*5) void main(){ int i=10/MAX; printf("%d\n", i); } void main(){ int i=10/(2*5); printf("%d\n", i); } 置換

3 インデントとフリーフォーマット 対応のわかりやすい ソースコードを記述 すること！！！！！ プログラム内の 空白，TAB文字，改行は
#include <stdio.h> void main(){ int i; for(i=0; i<5; i++){ printf(”i=%d\n”, i); } プログラム内の 空白，TAB文字，改行は 無視される． よって，どのように 書いても問題ない． 当然，見やすく書くことが 好ましい． #include <stdio.h> void main(){ int i; for(i=0; i<5; i++){ printf(”i=%d\n”, i); } #include <stdio.h> void main(){ int i; for(i=0; i<5; i++){ printf(”i=%d\n”, i); } 対応のわかりやすい ソースコードを記述 すること！！！！！ ↑対応関係がわかりづらい． ↑対応関係が誤り． #include <stdio.h> void main(){　int i;　for(i=0; i<5; i++){　printf(”i=%d\n”, i);　}} ↑理解が困難．対応関係が分かりづらい．

4 見やすい例 #include <stdio.h> void main(){ int i, j;
for(i=0; i<10; i++){ for(j=0; j<10; j++){ if( (i + j) % 10 == 0 ){ printf("***\n"); } else { printf("%d %d\n", i, j); }

5 見づらい例 これは，私(山口)には 理解できません． #include <stdio.h> void main(){
int i, j; for(i=0; i<10; i++){ for(j=0; j<10; j++){ if( (i + j) % 10 == 0 ){ printf("***\n"); } else { printf("%d %d\n", i, j); } これは，私(山口)には 理解できません． 詳しくは,下記を参照. プログラミング演習のページから「その他,C言語注意事項」のリンクでたどれる.

6 概要 関数の作り方を学ぶ 関数を再帰的に使用する 結構難しいです．

7 関数

8 関数の概要 1/3 関数とは，“複数の処理をひとまとめにしたもの”． 関数は“引数”を受け取り，“戻り値”を返すことができる．
同じ処理/似た処理を 何度も記述するような場合に便利． 関数は“引数”を受け取り，“戻り値”を返すことができる． 実は，printf() も main() も関数．

9 関数の概要 2/3 この3行まとめて， 1個のグループに したい． 実行結果 1 #include <stdio.h>
2 void main(){ 3 printf("Hello,"); 4 printf("World"); 5 printf("!!!!\n"); 6 printf(" \n"); 7 printf("Hello,"); 8 printf("World"); 9 printf("!!!!\n"); printf("############\n"); printf("Hello,"); printf("World"); printf("!!!!\n"); 14 } この3行まとめて， 1個のグループに したい． Hello,World!!!! ############ 実行結果

10 関数の概要 3/3 正しくは，グループ ではなく“関数”と呼ぶ 関数を“呼び出す”と言う． この3行が1個の グループになった．
1 #include <stdio.h> 2 3 void printHW(){ printf("Hello,"); printf("World"); printf("!!!!\n"); 7 } 8 9 void main(){ printHW(); printf(" \n"); printHW(); printf("############\n"); printHW(); 15 } この3行が1個の グループになった． グループ名は printHW printHW();で， printHWグループを 一括して実行できる． プログラムはmain()から始まる． 正しくは，グループ ではなく“関数”と呼ぶ 関数を“呼び出す”と言う．

11 関数の動作 1/2 3 void printHW(){ 4 printf("Hello,"); ④ 5 printf("World");
6 printf("!!!!\n"); 7 } ④ ① ⑤ 9 void main(){ printHW(); printf(" \n"); printHW(); printf("############\n"); printHW(); 15 } ③ ② ⑥

12 関数の動作 2/2 3 void printHW(){ 4 printf("Hello,"); ⑨ 5 printf("World");
6 printf("!!!!\n"); 7 } ⑨ ⑩ 9 void main(){ printHW(); printf(" \n"); printHW(); printf("############\n"); printHW(); 15 } ⑦ ⑧ ⑪

13 関数の作り方 3 void printHW (){ 4 printf("Hello,"); 5 printf("World");
戻り値(後述) この例では， “void”である． 関数名(後述) この例では， “printHW”である． 引数(後述) この例では， 空である． 3 void printHW (){ 4 printf("Hello,"); 5 printf("World"); 6 printf("!!!!\n"); 7 } 関数の中身 main() の書き方と同じである．main() も関数である．

14 関数の作り方 (例) 関数名に数字も使用可． ただし，数字から 始まる関数名はNG． 例：“10pHW”はNG 関数の中で
#include <stdio.h> void printHW(){ printf("Hello,"); printf("World"); printf("!!!!\n"); } void pHW10(){ int i; for(i=0; i<10; i++){ printf("Hello,World!\n"); void main(){ printHW(); pHW10(); 関数名に数字も使用可． ただし，数字から 始まる関数名はNG． 例：“10pHW”はNG 関数の中で 変数を使うことも可能． この変数はpHW10の 中でしか使えない． これはローカル変数. (後述)

15 関数の作り方 (例) 実行結果 この1行で， sankaku() の 全てが一括して 実行される．
1 #include <stdio.h> 2 void sankaku(){ 3 printf("*\n"); 4 printf("**\n"); 5 printf("***\n"); 6 printf("****\n"); 7 } 8 void gyaku_sankaku(){ 9 printf("****\n"); printf("***\n"); printf("**\n"); printf("*\n"); 13 } 14 void main(){ sankaku(); gyaku_sankaku(); sankaku(); sankaku(); gyaku_sankaku(); 20 } 関数の作り方 (例) * ** *** **** 実行結果 この1行で， sankaku() の 全てが一括して 実行される．

16 練習 G-0 printf("Hello,\n"); printf("World!\n"); を行う関数を作成し,
それをmain関数から呼び出すプログラムを記述せよ. 関数名はpr_hl_wld()とせよ.

17 解答 G-0 #include <stdio.h> void pr_hl_wld(){ printf("Hello,\n");
printf("World!\n"); } void main(){ pr_hl_wld();

18 関数の作り方 (引数) 引数とは，関数に与える情報． 関数に情報を与えることが可能． 関数では，与えられた情報を使用して処理することが可能．
“情報”とは，int型の値，double型の値などである． 引数は，何個でも用意できる．

19 関数の作り方 (引数) 3 void printHW (){ 4 printf("Hello,"); 5 printf("World");
この部分に，引数について記述する． この例では引数は なし(空，void)． 3 void printHW (){ 4 printf("Hello,"); 5 printf("World"); 6 printf("!!!!\n"); 7 }

20 関数の作り方 (引数) 引数を受け取る関数． void print_int (int i){ printf("i=%d\n", i); }
戻り値(後述) この例では， “void”である． 引数． この例では，int型変数1個． それを i とする． 厳密には仮引数と言う． 関数名． この例では， “print_int”． void print_int (int i){ printf("i=%d\n", i); }

21 関数の作り方 (引数) 関数に引数を渡す． void main(){ print_int(3); }
与えて関数呼び出し． void main(){ print_int(3); } void print_int (int i){ printf("i=%d\n", i); } 変数 i が宣言 されており， i を使用可能． i = 3 として関数が 始まる． 実行結果 i=3

22 関数の作り方 (引数) 呼び出される関数と，呼出し処理をまとめると， #include <stdio.h>
print_int()を 呼び出すには， 呼び出すよりも前に print_int()が 宣言(記述)されて いなくてはならない． (あるいは，宣言されている ことが推奨される． C言語では推奨． C++では必須．) ただし，プロトタイプ宣言を 行えばこの限りでない． #include <stdio.h> void print_int (int i){ printf("i=%d\n", i); } void main(){ print_int(3); プログラムは，必ずmain() から始まる．

23 関数の作り方 (引数の例) 実行結果 Hello,World!!!! Hello,World!!!!!!! for文を使う例
#include <stdio.h> void printHW_n(int n){ int i; printf("Hello,World"); for(i=0; i<n; i++){ printf("!"); } /* n個の ! を表示 */ printf("\n"); } void main(){ printHW_n(4); printHW_n(7); for文を使う例 実行結果 Hello,World!!!! Hello,World!!!!!!!

24 関数の作り方 (引数の例) 実行結果 3 + 7 = 10 引数2個の例 引数2個の例． ，(カンマ)で区切る
#include <stdio.h> void print_sum(int a, int b){ printf("%d + %d = %d\n", a, b, (a+b)); } void main(){ int x=3, y=7; print_sum(x,y); 実引数に， 変数を使った例． 実行結果 3 + 7 = 10

25 関数の作り方 (引数の例) 実行結果 ******* #include <stdio.h>
void print_nchar(char c, int n){ int i=0; for(i=0; i<n; i++){ printf("%c", c); } printf("\n"); void main(){ char ch = '*'; int x = 7; print_nchar(ch,x); char型とint型を 受け取った例． char型は「文字」型． 文字1個を表す． 引数は，char型と，int型なので， char型の値と，int型の値を入れて 呼び出す 実行結果 *******

26 関数の作り方 (戻り値) 戻り値とは，「関数が呼び出しもとに返す情報」． 関数から，関数の呼び出しもとに情報を返すことが可能．
戻り値は，関数の終了時に返される． “情報”とは，int型の値，double型の値などである． 戻り値は，最大でも1個． void なら，0個．

27 関数の作り方 (戻り値) 3 void printHW (){ 4 printf("Hello,"); 5 printf("World");
この部分に，戻り値について記述する． この例では引数は なし(空，void)． 3 void printHW (){ 4 printf("Hello,"); 5 printf("World"); 6 printf("!!!!\n"); 7 }

28 関数の作り方 (戻り値) 戻り値を返す関数． 戻り値． この例では， “int”である． 関数名． この例では， “square”． 引数．
int square(int n){ int sq; sq = n*n; printf("%d^2 = %d\n", n, sq); return sq; }

29 関数の作り方 (戻り値) 戻り値を返す関数． ②i=5 int square(int n){ int sq; sq = n*n;
printf("%d^2 = %d\n", n, sq); return sq; } ③sq=25 ① 引数 5 ④ 戻り値 25 戻り値が"25"なので， square(5) が 25となる． よって， s = 25; void main(){ int s; s = square(5); printf("square=%d\n", s); }

30 関数の作り方 (戻り値の例) 実行結果 5^2 = 25 square=25 1 #include <stdio.h>
2 int square(int n){ int sq; sq = n*n; printf("%d^2 = %d\n", n, sq); return sq; 7 } 8 9 void main(){ int s; s = square(5); printf("square=%d\n", s); 13 } 実行結果 5^2 = 25 square=25

31 関数の作り方 (戻り値の例) 実行結果 1 #include <stdio.h>
2 double double_square(double d){ double sq; sq = d*d; printf("%lf^2 = %lf\n", d, sq); return sq; 7 } 8 9 void main(){ double s; s = double_square(1.5); printf("square=%lf\n", s); 13 } 引数がdouble型1個なら， double型の値1個を 入れて，呼び出す． 実行結果 ^2 = square=

32 関数の作り方 (戻り値の例) 実行結果 1 #include <stdio.h>
2 double double_square(double d){ double sq; sq = d*d; printf("%lf^2 = %lf\n", d, sq); return sq; 7 } 8 9 void main(){ double s; s = double_square(1.5); printf("square=%lf\n", s); 13 } 戻り値がdouble型なら， double型の値を return する． 実行結果 ^2 = square=

33 関数の作り方 (戻り値の例) 実行結果 i=1, j=2, k=3 1 #include <stdio.h>
2 int one(){ return 1; 4 } 5 int two(){ return 2; 7 } 8 int three(){ return 3; 10 } 11 void main(){ int i, j, k; i = one(); j = two(); k = three(); printf("i=%d, j=%d, k=%d\n", i, j, k); 17 } 実行結果 i=1, j=2, k=3

34 関数の作り方 (戻り値の例) 実行結果 i=1, j=2, k=3 printf()の中に直接記述してもOK.
1 #include <stdio.h> 2 int one(){ return 1; 4 } 5 int two(){ return 2; 7 } 8 int three(){ return 3; 10 } 11 void main(){ printf("i=%d, j=%d, k=%d\n", one(), two(), three()); 13 } 実行結果 i=1, j=2, k=3 printf()の中に直接記述してもOK. one() が"1"，two()が"2"と思えば良い．

35 関数の作り方 (まとめ) 戻り値の型 関数名(引数の型 変数名,…){ 関数の中身... (変数の宣言なども可能)
return ○; (←戻り値がvoidなら，省略可) }

36 関数：戻り値を捨てる double d_sq(double d){ double sq = d*d;
printf("%lf^2 = %lf\n", d, sq); return sq; } void main(){ double x; x = d_sq(1.2); d_sq(3.4); 実行結果 ^2 = ^2 = 戻り値を受け止めて，xに代入． 戻り値を受け止めずに， 捨てる．特に問題ない． 戻り値情報は失われるが， 関数は正しく実行される．

37 関数：複数のreturn 関数内に return が 何個あってもよい． 実行結果 x=3 |x|=3 x=-4 |x|=4
1 #include <stdio.h> 2 int zettaichi(int n){ 3 if( n<0 ){ return (-n); 5 } else { return n; 7 } 8 } 9 void main(){ int x, z; x = 3; z = zettaichi(x); printf("x=%d |x|=%d\n", x, z); x = -4; z = zettaichi(x); printf("x=%d |x|=%d\n", x, z); 17 } 関数内に return が 何個あってもよい． 実行結果 x=3 |x|=3 x=-4 |x|=4

38 関数：return return により， 関数は強制的に 終了する． 実行結果 1 #include <stdio.h> 2
3 void funct(){ 4 printf("AAAA\n"); 5 printf("BBBB\n"); 6 return; 7 printf("CCCC\n"); 8 } 9 10 void main(){ 11 funct(); 12 } 実行結果 AAAA BBBB 戻り値が無いときは， 単に return; と記述

39 関数：ローカル変数 1 void funct(){ 2 int x; 3 x = 3; 4 abcd = 4; 5 }
ブロックの外で 使おうとしている． これは，NG． コンパイルエラーとなる． 1 void funct(){ 2 int x; 3 x = 3; 4 abcd = 4; 5 } 6 void main(){ 7 int abcd; 8 abcd = 5; 9 funct(); 10 } int abcd は， このブロック内で 宣言されているため， このブロックの中でしか 使用できない． ブロック内の変数を ローカル変数という． ブロックの範囲

40 関数：仮引数と実引数 実行結果 i=5 mainのiと，func0のxは 別の変数． mainのiの値が，func0のxに
代入(コピー)される． func0のxを変更しても， mainのiには影響なし． 1 void func0(int x){ 2 x = 3; 3 } 4 void func1(int i){ 5 i = 3; 6 } 7 void main(){ 8 int i = 5; 9 printf("i=%d\n", i); func0(i); printf("i=%d\n", i); func1(i); printf("i=%d\n", i); 14 } xが仮引数 mainのiと，func1のiは 別の変数． 名前が同じ別の変数． mainのiの値が，func1のiに 代入(コピー)される． func1のiを変更しても， mainのiには影響なし． iが実引数 i=5 実行結果

41 関数の多段呼び出し 1/3 実行結果 main() func0() func0() func0 start! func0 end!
1 void func0(){ 2 printf("func0 start!\n"); 3 printf("func0 end!\n"); 4 } 10 void main(){ func0(); 12 } main() func0() 実行結果 func0() func0 start! func0 end!

42 関数の多段呼び出し 2/3 実行結果 1 void func0(){ 2 printf("func0 start!\n");
3 printf("func0 end!\n"); 4 } 5 void func1(){ 6 printf("func1 start!\n"); 7 func0(); 8 printf("func1 end!\n"); 9 } 10 void main(){ func1(); 12 } 実行結果 func1 start! func0 start! func0 end! func1 end!

43 関数の多段呼び出し 3/3 func0() func0() func1() func1() main()

44 関数の再帰呼び出し ある関数から，自分自身を呼び出すことを再帰呼び出しという．
例えば，関数funct() の中で，funct() を呼び出すなど． 使い方を間違えると，永遠に終了しないプログラムになりやすいので注意．

45 関数の再帰呼び出し 1 void pr_hl(){ 2 printf("Hello!start\n"); 3 pr_hl();
4 printf("Hello!end\n"); 5 } 6 void main(){ 7 pr_hl(); 8 } 動作の解説は次ページ 注意！これは失敗例です．

46 呼び出しを永遠に続け， このプログラムは 終わらない． main() pr_hl()が 呼ばれたので， pr_hl()に移動．

47 再帰：nの階乗 1/5 nの階乗を，n!と記述する． n! は，n×(n-1)×(n-2)×…×2×1 n! は，n × (n-1)!
5! は，5×4×3×2×1 5! は，5×4!

48 再帰：nの階乗 2/5 nの階乗は もし n == 1 なら， 答えは，1 もし n > 1 なら， 答えは，n×(n-1)!

49 再帰：nの階乗 3/5 1 int kaijoh(int x){ 2 int r; 3 if( x == 1 ){ 4 return 1;
5 } else { r = x * kaijoh(x-1); return r; 8 } 9 } 10 void main(){ int n, k; n = 5; k = kaijoh( n ); printf("%d! = %d\n", n, k); 15 }

50 再帰：nの階乗 4/5 main() kaijoh(3) kaijoh(3)は，3*kaijoh(2) kaijoh(2)
これ以上再帰呼び出ししない． これがないと 無限に続く kaijoh(2)=2 kaijoh(3)は，3*2 kaijoh(3)=6

51 再帰：nの階乗 5/5 kaijoh( 4 ) =4* kaijoh( 3 ) =4* (3* kaijoh( 2 ) )
=4* (3* (2* ) ) =4* (3* ( ) ) =4* ( ) =24

52 失敗例 1 int kaijoh(int x){ 2 int r; 3 r = x * kaijoh(x-1); 4 return r;
↓ kaijoh(4)を呼び出し kaijoh(3)を呼び出し kaijoh(2)を呼び出し kaijoh(1)を呼び出し kaijoh(0)を呼び出し kaijoh(-1)を呼び出し kaijoh(-2)を呼び出し kaijoh(-3)を呼び出し 無限に続く 1 int kaijoh(int x){ 2 int r; 3 r = x * kaijoh(x-1); 4 return r; 5 } 6 void main(){ 7 int n, k; 8 n = 5; 9 k = kaijoh( n ); printf("%d! = %d\n", n, k); 11 }

53 再帰：組み合わせ nCr 組み合わせ(Conbination) nCr は， r>1なら， nCr=n-1Cr-1 * n / r

54 練習 G-1 3次元配列の int x[3][4][5]; を全て表示するプログラムを作成せよ．

55 解答 G-1 int i, j, k; for(i=0; i<3; i++){ for(j=0; j<4; j++){
for(k=0; k<5; k++){ printf("%d\n", x[i][j][k]); } x[i][j][k]の全ての場合を 網羅して printf を行えば良い. i=0～2 j=0～3 k=0～4

56 再帰：ハノイの塔 ハノイの塔というパズル 引用 奥野かるた店より

57 再帰：ハノイの塔 ルール 円盤置き場が3カ所ある． 円盤がn枚あり，全て大きさが異なる． 小さい円盤の上に大きな円盤は置けない．
通常，円盤の中心に穴があり， 円盤置き場には杭が立っている． 円盤がn枚あり，全て大きさが異なる． 小さい円盤の上に大きな円盤は置けない． 円盤置き場の1番上の1枚を別の円盤置き場に移動することができる．

58 再帰：ハノイの塔 目的 解法 n枚の円盤を，ある円盤置き場から別の円盤置き場に移動する． できるだけ少ない円盤移動が好ましい． 最適解は，
円盤がn枚の場合，2n-1回の円盤移動． プログラミングでは，再帰的手法で解ける．

59 ハノイの塔：2枚の例 円盤 1 2 円盤置き場 ↓開始！(円盤2枚を左から中央に) 1 2 1回目の移動． 円盤1を左から右に． 2 1

60 ハノイの塔：2枚の例 2 1 2回目の移動． 円盤2を左から中央に． 2 1 2 1 3回目の移動． 円盤1を右から中央に．
22-1=3回で終了． 1 2 完了！

61 ハノイの塔：3枚の例 1 2 1回目の移動． 円盤1を左から中央に． 3 2 2回目の移動． 円盤2を左から右に． 円盤3の上が空に． 3
3回目の移動． 円盤1を中央から右に． 中央の円盤置き場が 空いた．円盤3を 中央に移動可能． 1 3 2

62 ハノイの塔：3枚の例 4回目の移動． 円盤3を左から中央に． ついに円盤3が移動！ 1 3 2 1 5回目の移動． 円盤1を左から右に． 3
6回目の移動． 円盤2を右から中央に． 1 3 2 2 7回目の移動． 円盤1を左から中央に． 1 3 1 2 3

63 ハノイの塔：4枚の例 24-1=15回の移動． 円盤3枚の移動方法(7回)は分かっている．．． ↓ 円盤3枚の移動方法を使えば，
円盤4枚の移動方法を導き出せる．

64 ハノイの塔：4枚の例 合計 7+1+7=15回 1 先ほどの方法で， 円盤3枚(1～3)を 左から右に移動． 7回の円盤移動． 2 3 4
円盤4を左から中央に． 1回の円盤移動． 4 3 1 先ほどの方法で， 円盤3枚(1～3)を 右から中央に移動． 7回の円盤移動． 2 4 3 1 2 3 合計 7+1+7=15回 4

65 ハノイの塔：n枚 n枚の移動方法が分かれば， それを用いて n+1枚の移動方法が分かる． 1枚の移動方法は分かる． ↓
任意の枚数の移動方法が分かる

66 ハノイの塔：n枚 合計 (2n-1-1)+1+(2n-1-1)=2n-1回 1 : n-1枚を左から右に 移動する．
移動回数1回． : n n-1 1 : n-1枚を右から中央に 移動する． 移動回数2n-1-1回． n n-1 1 : n-1 合計 (2n-1-1)+1+(2n-1-1)=2n-1回 n

67 ハノイの塔を解く関数 ハノイの塔の移動(移動枚数，移動元の円盤置場，移動先の円盤置場，待避円盤置場) もし，移動枚数が1なら，
1枚を「移動元」から「移動先」に移動する． もし，移動枚数が1より大きければ， (n-1)枚を「移動元」から「待避」に移動． n枚目を「移動元」から「移動先」に移動． (n-1)枚を「待避」から「移動先」に移動．

68 ハノイの塔を解く関数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <stdio.h> void hanoi(int n, int plFrom, int plTo, int plOther){ if( n == 1 ){ printf("move disk.%d ", n); printf("[%d -> %d]\n", plFrom, plTo); } else { hanoi(n-1, plFrom, plOther, plTo); hanoi(n-1, plOther, plTo, plFrom); } void main(){ hanoi(5, 0, 1, 2);

69 フィボナッチ数列 以下の数列がフィボナッチ数列 1,1,2,3,5,8,13,21,34,… an+an+1=an+2 となる．
ただし，a0=1,a1=1 fibo(n)=fibo(n-1)+fibo(n-2) という再帰的な発想で記述可能． ただし,for文で加算した方が短時間で計算可能

70 フィボナッチ数列 fibo(5) fibo(4) fibo(3) fibo(1) =1 fibo(2) fibo(3) fibo(2)
同じ処理を何度も 行っている． 大変に非効率的 fibo(0) =1 fibo(1) =1 fibo(0) =1 fibo(1) =1

71 計算量/計算時間 n枚のハノイの塔 n個の数字をバブルソートで並び替える． n個の数字をクイックソートで並び替える
n×log(n) に比例する計算量/時間 n個の数字をバケツソートで並び替える n に比例する計算量/時間

72 練習 G-2 fibo(n)=fibo(n-1)+fibo(n-2) という 再帰的な考え方で,

73 解答 G-2 #include <stdio.h> int fibo(int n){ if( n <= 1 ){
return 1; } else { return fibo(n-1)+fibo(n-2); } void main(){ printf("%d\n", fibo(7)); これは例