プログラミング言語Ⅰ(実習を含む。), 計算機言語Ⅰ・計算機言語演習Ⅰ, 情報処理言語Ⅰ(実習を含む。)

Presentation on theme: "プログラミング言語Ⅰ(実習を含む。), 計算機言語Ⅰ・計算機言語演習Ⅰ, 情報処理言語Ⅰ(実習を含む。)"— Presentation transcript:

1 プログラミング言語Ⅰ(実習を含む。), 計算機言語Ⅰ・計算機言語演習Ⅰ, 情報処理言語Ⅰ(実習を含む。)
C言語入門 第9週 プログラミング言語Ⅰ(実習を含む。), 計算機言語Ⅰ・計算機言語演習Ⅰ, 情報処理言語Ⅰ(実習を含む。)

2 関数

3 関数 関数の定義の書式: 第4週資料pp.33-41,48-49. 関数の宣言 戻り値の型 関数名(引数の宣言, ...);
.h ファイルへ書き出す 関数の定義 戻り値の型 関数名(引数の宣言, ...) { // 関数に行わせる処理 // ... return 戻り値; // 戻り値の型がvoidの場合は不要 } .c ファイルへ書き出す 関数の利用 変数名 = 関数名(引数, ...); 適宜呼び出す

4 関数の引数(値渡し、参照渡し) 変数のスコープ(有効範囲) $ gcc scopetest.c && ./a
第4週資料pp 関数の引数(値渡し、参照渡し) 変数のスコープ(有効範囲) scopetest.c 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 int gl = 100; void sub(int lo) { int lo = 400; printf("%-4s : %3d: gl=%d, lo=%d\n", __func__, __LINE__, ++gl, ++lo); } int main() int lo = 200; sub(300); return EXIT_SUCCESS; 関数の引数は呼び出し元とは別の変数になっていた mintty + bash + GNU C $ gcc scopetest.c && ./a sub : 14: gl=101, lo=401 sub : 16: gl=102, lo=301 main : 23: gl=103, lo=201

5 関数の引数(値渡し、参照渡し) 値渡し: 呼出し元の値のコピーを渡す $ g++ call_by_value.c && ./a lo=100
第4週資料pp 教科書p.171. 関数の引数(値渡し、参照渡し) 値渡し: 呼出し元の値のコピーを渡す call_by_value.c 8 9 10 11 12 13 14 15 16 17 18 19 20 void sub(int lo) { lo = 200; } int main() int lo = 100; sub(lo); printf("lo=%d\n", lo); return EXIT_SUCCESS; 引数で受け取った変数を変更しても 呼び出し元には反映されない mintty + bash + GNU C $ g++ call_by_value.c && ./a lo=100

6 関数の引数(値渡し、参照渡し) 参照渡し: 呼出し元の値の格納場所を渡す $ g++ call_by_pointer.c && ./a
第4週資料pp 教科書p.171. 関数の引数(値渡し、参照渡し) 参照渡し: 呼出し元の値の格納場所を渡す call_by_pointer.c これは正確には ポインタ渡しと言う 8 9 10 11 12 13 14 15 16 17 18 19 20 void sub(int *lo) { *lo = 200; } int main() int lo = 100; sub(&lo); printf("lo=%d\n", lo); return EXIT_SUCCESS; 引数で受け取った変数を変更すると 呼び出し元にも反映される scanf で見たことがある書き方！ &: アドレス演算子 変数loのアドレスを 渡している mintty + bash + GNU C $ g++ call_by_pointer.c && ./a lo=200

7 関数の引数(値渡し、参照渡し) C++における参照渡し $ g++ call_by_reference.cpp && ./a lo=200
参考 関数の引数(値渡し、参照渡し) C++における参照渡し call_by_reference.cpp C++では 本物の参照渡しが 可能になった 4 5 6 7 8 9 10 11 12 13 14 15 16 void sub(int &lo) { lo = 200; } int main() int lo = 100; sub(lo); printf("lo=%d\n", lo); return EXIT_SUCCESS; 引数で受け取った変数を変更すると 呼び出し元にも反映される 値が変化することが 分かり難いという デメリットもある C++の参照渡しでは アドレス演算子「&」が不要 mintty + bash + GNU C++ $ g++ call_by_reference.cpp && ./a lo=200

8 ポインタ変数 メモリ上のアドレスを指し示すための変数 ポインタ型のサイズはアドレス空間のビット数
教科書pp ポインタ変数 pointer: 指し示す者 メモリ上のアドレスを指し示すための変数 char * 型: char 型の変数へのポインタ int * 型: int 型の変数へのポインタ 要はアドレスを格納するための変数 ポインタ型のサイズはアドレス空間のビット数 32ビットアドレス空間なら4バイト 64ビットアドレス空間なら8バイト sizeof(char *)もsizeof(int *)も同じ

9 メモリの構成 1byte単位でアドレスが振られている つまり各アドレスには1byteの値を格納出来る 教科書 pp.52-56.
32bitのOSは32bitのアドレス空間 最大 2 32 Bytes=4GiB 64bitのOSは64bitのアドレス空間 最大 2 64 Bytes=16EiB 0x00 0x 0x 0x 0x 0xffffffff : 0x00 0x 0x 0x 0x 0xffffffffffffffff : ポインタ変数には これらの値が入る アドレス 格納値 アドレス 格納値

10 ポインタ変数 例: 16bit short型little endianの場合 short a = 0x1234;
教科書pp ポインタ変数 宣言時に*を付けると ポインタ変数になる 要はリンク みたいなもの 例: 16bit short型little endianの場合 : short a = 0x1234; short *p = &a; &a 0x34 0x～00 a 0x12 0x～01 p に &a を入れておくと *p は a への 参照として機能する C言語ではこれを ポインタと言う 0x?? 0x～02 &aは 変数aの メモリ上の 先頭アドレス a 0x1234 0x?? 0x～03 0x～00 0x?? 0x～04 0x?? 0x～05 *p 0x1234 0x?? 0x～06 *pはアドレスpに 置かれた変数(ここではa) への参照 0x～00 0x?? 0x～07 0x?? 0x～08 p 0x～00 実際に存在している変数はpで中にはアドレスが格納されている : pは変数*pの アドレスを指し示す

11 ポインタ変数 変数が配置されたアドレスを扱うための変数 $ gcc pointertest1.c && ./a a=2
教科書pp ポインタ変数 変数が配置されたアドレスを扱うための変数 pointertest1.c 変数の宣言で 変数名の前にポインタ宣言子「*」を付けると ポインタ変数になる。 この場合、 int 型の変数 *p を宣言した結果、 実際には int 型変数へのポインタである int * 型変数 p が宣言されると 理解しておくとスッキリする。 4 5 6 7 8 9 10 11 12 13 14 15 int main() { int a = 1; int *p; p = &a; *p = 2; printf("a=%d\n", a); return EXIT_SUCCESS; } mintty + bash + GNU C $ gcc pointertest1.c && ./a a=2

12 ポインタ変数 変数が配置されたアドレスを扱うための変数 $ gcc pointertest1.c && ./a a=2
教科書pp ポインタ変数 変数が配置されたアドレスを扱うための変数 pointertest1.c 4 5 6 7 8 9 10 11 12 13 14 15 int main() { int a = 1; int *p; p = &a; *p = 2; printf("a=%d\n", a); return EXIT_SUCCESS; } アドレス演算子「&」を用いて int 型変数 a のアドレス &a を int 型の変数へのポインタ p に代入する a 1 0x～ mintty + bash + GNU C &a $ gcc pointertest1.c && ./a a=2 p 0x～

13 ポインタ変数 変数が配置されたアドレスを扱うための変数 $ gcc pointertest1.c && ./a a=2
教科書pp ポインタ変数 変数が配置されたアドレスを扱うための変数 pointertest1.c int 型の変数へのポインタ p の前に 間接演算子「*」を付けると ポインタ変数 p が指し示すアドレスを int 型の変数としてアクセス出来る。 今 p に変数 a のアドレス &a が 入っているので、 *p に対するあらゆる操作は 変数 a に対する操作と同義となる。 実際 *p を書き変えることで a が 書き変えられていることが確認出来る。 4 5 6 7 8 9 10 11 12 13 14 15 int main() { int a = 1; int *p; p = &a; *p = 2; printf("a=%d\n", a); return EXIT_SUCCESS; } a 2 0x～ mintty + bash + GNU C *p $ gcc pointertest1.c && ./a a=2 p 0x～

14 ポインタ変数の宣言と代入 「*」と「=」の使い方は要注意 同じ「*」だが宣言時とそれ以外で意味が異なる
教科書pp , [1] pp.250, ポインタ変数の宣言と代入 「*」と「=」の使い方は要注意 同じ「*」だが宣言時とそれ以外で意味が異なる 宣言時 それ以外 *p pをポインタとして宣言 pが指すアドレスの格納値 *p=x pにxを代入 *pにxを代入 *は間接演算子 indirection operator または間接参照演算子 dereference operator ポインタ変数pが指すアドレス (言い換えると、ある型の変数*p)に 値xを代入する ポインタ変数pを宣言 (言い換えると、ある型の変数*pを宣言)し 宣言した変数pに アドレスxを代入する *はポインタ宣言子 pointer declarator 要注意

15 ポインタ変数の宣言と代入 「*」と「=」の使い方は要注意 $ gcc pointertest2.c && ./a sizeof(p1)=8
教科書pp ポインタ変数の宣言と代入 「*」と「=」の使い方は要注意 pointertest2.cpp mintty + bash + GNU C 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int a = 1; int *p1, b; int *p2 = &a; p1 = &a; printf("sizeof(p1)=%d\n", sizeof(p1)); printf("sizeof(b)=%d\n", sizeof(b)); printf("&a=%#0*p\n", sizeof(&a)*2+2, &a); printf("p1=%#0*p\n", sizeof(p1)*2+2, p1); printf("p2=%#0*p\n", sizeof(p2)*2+2, p2); printf("a=%d\n", a); printf("*p1=%d\n", *p1); printf("*p2=%d\n", *p2); $ gcc pointertest2.c && ./a sizeof(p1)=8 sizeof(b)=4 &a=0x aabc p1=0x aabc p2=0x aabc a=1 *p1=1 *p2=1 要注意

16 ポインタ変数の宣言と代入 「*」と「=」の使い方は要注意 $ gcc pointertest2.c && ./a sizeof(p1)=8
教科書pp ポインタ変数の宣言と代入 宣言時は「*」が間接演算子ではなく ポインタ宣言子として働いている 宣言時に初期化すると *p2 ではなく p2 に &a が代入される点が紛らわしい 要注意 「*」と「=」の使い方は要注意 pointertest2.cpp mintty + bash + GNU C 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int a = 1; int *p1, b; int *p2 = &a; p1 = &a; printf("sizeof(p1)=%d\n", sizeof(p1)); printf("sizeof(b)=%d\n", sizeof(b)); printf("&a=%#0*p\n", sizeof(&a)*2+2, &a); printf("p1=%#0*p\n", sizeof(p1)*2+2, p1); printf("p2=%#0*p\n", sizeof(p2)*2+2, p2); printf("a=%d\n", a); printf("*p1=%d\n", *p1); printf("*p2=%d\n", *p2); $ gcc pointertest2.c && ./a sizeof(p1)=8 sizeof(b)=4 &a=0x aabc p1=0x aabc p2=0x aabc a=1 *p1=1 *p2=1 p1 に &a を代入している 宣言時以外は*は関節演算子として働く ポインタの前に*が付くと、指し示す アドレスに格納されている値を操作する 要注意

17 ポインタ変数の宣言と代入 「*」と「=」の使い方は要注意 $ gcc pointertest2.c && ./a sizeof(p1)=8
教科書pp ポインタ変数の宣言と代入 「*」と「=」の使い方は要注意 pointertest2.cpp mintty + bash + GNU C 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int a = 1; int *p1, b; int *p2 = &a; p1 = &a; printf("sizeof(p1)=%d\n", sizeof(p1)); printf("sizeof(b)=%d\n", sizeof(b)); printf("&a=%#0*p\n", sizeof(&a)*2+2, &a); printf("p1=%#0*p\n", sizeof(p1)*2+2, p1); printf("p2=%#0*p\n", sizeof(p2)*2+2, p2); printf("a=%d\n", a); printf("*p1=%d\n", *p1); printf("*p2=%d\n", *p2); $ gcc pointertest2.c && ./a sizeof(p1)=8 sizeof(b)=4 &a=0x aabc p1=0x aabc p2=0x aabc a=1 *p1=1 *p2=1 「int *」型の宣言ではなく、 「int」型の宣言である点も紛らわしい。 p1 はポインタ変数だが b は通常のint型変数 複数の変数を宣言する場合 変数名の前に ポインタ宣言子「*」を付けた変数だけが ポインタ変数になる 要注意 要注意

18 ポインタの表示 %p void *;ポインタとして印字(処理系依存) 第3週資料pp.24-33. 例
mintty + bash + GNU C printf("&a=%#0*p\n", sizeof(&a)*2+2, &a); $ gcc hoge.c && ./a &a=0x aabc %*pによる最小フィールド幅指定 1バイト=16進数2桁 先頭の0xで更に2桁 #: 16進表示が0でない場合、先頭を0xにする 0: フィールド幅いっぱいに左側から0を詰める *: 最小フィールド幅を引数で指定 p: void *;ポインタとして印字

19 1次元配列とポインタ 機能としてはほぼ同じ ポインタはアドレスを変更可能(少し柔軟) 教科書pp.207-272.
配列は1要素のバイト数×要素数 ポインタはアドレス空間のビット数/8 機能としてはほぼ同じ ポインタはアドレスを変更可能(少し柔軟) 配列 int p[N]; ポインタ int *p; sizeof(p) ○ 変数pの割り当てバイト数 &p △ 変数pのアドレス(配列はpと同じ) p アドレスp(p[0]のアドレス) *p アドレスpの格納値 p[x] アドレスpを先頭にしてx個目の要素の格納値 *(p+x) アドレスpを先頭にしてx個目の要素(p[x])の格納値 &p[x] アドレスpを先頭にしてx個目の要素(p[x])のアドレス p+x p+=x ×

20 ポインタ変数とアドレス演算 例: 16bit short型little endianの場合 short a = 0x1234;
教科書pp ポインタ変数とアドレス演算 例: 16bit short型little endianの場合 : short a = 0x1234; short *pa = &a; pa 0x34 0x～00 *pa 0x12 0x～01 pa+1 0x?? 0x～02 *(pa+1) ±1するとsizeof(*pa)単位で アドレスが増減する つまり short 型配列の 0要素目、1要素目、... という意味になる 0x?? 0x～03 pa+2 0x?? 0x～04 *(pa+2) 0x?? 0x～05 pa+3 0x?? 0x～06 *(pa+3) 0x?? 0x～07 0x?? 0x～08 : 要注意

21 ポインタ変数とアドレス演算 例: 32bit int型little endianの場合 int a = 0x12345678;
教科書pp ポインタ変数とアドレス演算 例: 32bit int型little endianの場合 : int a = 0x ; int *pa = &a; pa 0x78 0x～00 0x56 0x～01 *pa 0x34 0x～02 ±1するとsizeof(*pa)単位で アドレスが増減する つまり int 型配列の 0要素目、1要素目、... という意味になる 0x12 0x～03 pa+1 0x?? 0x～04 0x?? 0x～05 *(pa+1) 0x?? 0x～06 0x?? 0x～07 0x?? 0x～08 : 要注意

22 ポインタ変数の配列的利用法 例: 16bit short型little endianの場合 short a = 0x1234;
教科書pp ポインタ変数の配列的利用法 例: 16bit short型little endianの場合 : short a = 0x1234; short *pa = &a; &pa[0] 0x34 0x～00 pa[0] 0x12 0x～01 &pa[1] 0x?? 0x～02 pa[1] 配列同様[x]で先頭x個目の 要素にアクセス出来る 要素の頭に&を付けると アドレスが得られる 0x?? 0x～03 &pa[2] 0x?? 0x～04 pa[2] 0x?? 0x～05 &pa[3] 0x?? 0x～06 pa[3] 0x?? 0x～07 0x?? 0x～08 :

23 ポインタ変数の配列的利用法 例: 32bit int型little endianの場合 int a = 0x12345678;
教科書pp ポインタ変数の配列的利用法 例: 32bit int型little endianの場合 : int a = 0x ; int *pa = &a; &pa[0] 0x78 0x～00 0x56 0x～01 pa[0] 0x34 0x～02 配列同様[x]で先頭x個目の 要素にアクセス出来る 要素の頭に&を付けると アドレスが得られる 0x12 0x～03 &pa[1] 0x?? 0x～04 0x?? 0x～05 pa[1] 0x?? 0x～06 0x?? 0x～07 0x?? 0x～08 :

24 1次元配列とポインタ 教科書pp.207-272. pointertest3.c
cygwin64 + mintty + bash + GNU C 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 int x; int a[] = {0,1,2,3,4,5,6,7,8,9}; int *p = a; fprintf(stderr, "x = ? "); scanf("%d", &x); printf("sizeof(a) = %p\n", sizeof(a)); printf("sizeof(p) = %p\n", sizeof(p)); printf("&a = %p\n", &a); printf("&p = %p\n", &p); printf("a = %p\n", a); printf("p = %p\n", p); printf("*a = %d\n", *a); printf("*p = %d\n", *p); printf("a[x] = %d\n", a[x]); printf("p[x] = %d\n", p[x]); printf("*(a+x) = %d\n", *(a+x)); printf("*(p+x) = %d\n", *(p+x)); printf("&a[x] = %p\n", &a[x]); printf("&p[x] = %p\n", &p[x]); printf("a+x = %p\n", a+x); printf("p+x = %p\n", p+x); //printf("a+=x = %p\n", a+=x); // Address of array variable can not be modified. printf("p+=x = %p\n", p+=x); $ gcc pointertest3.c && ./a x = ? 1 sizeof(a) = 0x28 sizeof(p) = 0x8 &a = 0x22aaa0 &p = 0x22aa98 a = 0x22aaa0 p = 0x22aaa0 *a = 0 *p = 0 a[x] = 1 p[x] = 1 *(a+x) = 1 *(p+x) = 1 &a[x] = 0x22aaa4 &p[x] = 0x22aaa4 a+x = 0x22aaa4 p+x = 0x22aaa4 p+=x = 0x22aaa4 pに1を足しているのに 結果が4増えていることが 確認出来る

25 1次元配列とポインタ 教科書pp.207-272. pointertest3.c
cygwin64 + mintty + bash + GNU C 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int x; int a[] = {0,1,2,3,4,5,6,7,8,9}; int *p = a; fprintf(stderr, "x = ? "); scanf("%d", &x); printf("sizeof(a) = %p\n", sizeof(a)); printf("sizeof(p) = %p\n", sizeof(p)); printf("&a = %p\n", &a); printf("&p = %p\n", &p); printf("a = %p\n", a); printf("p = %p\n", p); $ gcc pointertest3.c && ./a x = ? 1 sizeof(a) = 0x28 sizeof(p) = 0x8 &a = 0x22aaa0 &p = 0x22aa98 a = 0x22aaa0 p = 0x22aaa0 <以下略> 配列変数aはメモリに配置されたアドレス 配列変数aのアドレス&aはつまりaと同じ ポインタ変数pは メモリ上のどこかに確保されており &pはそのアドレス pはそのアドレス&pに格納されたアドレス この例では&a *pはそのアドレスpに格納されたデータ

26 1次元配列とポインタ 例: 32bitOSで8bit char型little endianの場合 char a[] = {0,1,2,3};
教科書pp 1次元配列とポインタ 例: 32bitOSで8bit char型little endianの場合 : char a[] = {0,1,2,3}; char *p = &a; &a =a =p 0x00 0x～00 0x01 0x～01 a これ全体が配列aであり aはその先頭アドレス 0x02 0x～02 0x03 0x～03 &p 0x00 0x～04 配列変数aはメモリに配置されたアドレス 配列変数aのアドレス&aはつまりaと同じ ポインタ変数pは メモリ上のどこかに確保されており &pはそのアドレス pはそのアドレス&pに格納されたアドレス この例では&a *pはそのアドレスpに格納されたデータ 0x~~ 0x～05 p 0x~~ 0x～06 0x~~ 0x～07 0x?? 0x～08 :

27 1次元配列とポインタ 例: 32bitOSで8bit char型little endianの場合 char a[] = {0,1,2,3};
教科書pp 1次元配列とポインタ 例: 32bitOSで8bit char型little endianの場合 : char a[] = {0,1,2,3}; char *p = &a; &a =a =p 0x00 0x～00 0x01 0x～01 a sizeof(a) は aの1要素辺りのバイト数×要素数 つまりsizeof(char)*N 0x02 0x～02 0x03 0x～03 &p 0x00 0x～04 sizeof(p) は OSのアドレス空間のビット数/8 つまりsizeof(char *) 0x~~ 0x～05 p 0x~~ 0x～06 0x~~ 0x～07 0x?? 0x～08 :

28 ポインタ変数 教科書pp.207-272. pointertest4.c Cygwin64+mintty+bash+GNU C
8 9 10 11 12 13 14 15 16 17 18 int i, *p, a[] = {0,1,2,3,4,5,6,7,8,9}; printf("&a[0]=%#0*p\n", sizeof(&a[0])*2+2, &a[0]); printf("p = ? "); scanf("%p", &p); printf("*p="); scanf("%i", p); for (i = 0; i < sizeof(a) / sizeof(*a); i++) { printf("a[%d]=%#0*x\n", i, sizeof(*a)*2+2, a[i]); } $ gcc pointertest4.c && ./a &a[0]=0x aa90 p = ? 0x aa98 *p=0x a[0]= a[1]=0x a[2]=0x a[3]=0x a[4]=0x a[5]=0x a[6]=0x a[7]=0x a[8]=0x a[9]=0x 結果がどうなるかは別として アドレス演算子を使って 変数のアドレスを入れなくても 適当な値を入れても動く。

29 ポインタ変数 教科書pp.207-272. pointertest4.c Cygwin64+mintty+bash+GNU C
8 9 10 11 12 13 14 15 16 17 18 int i, *p, a[] = {0,1,2,3,4,5,6,7,8,9}; printf("&a[0]=%#0*p\n", sizeof(&a[0])*2+2, &a[0]); printf("p="); scanf("%p", &p); printf("*p="); scanf("%i", p); for (i = 0; i < sizeof(a) / sizeof(*a); i++) { printf("a[%d]=%#0*x\n", i, sizeof(*a)*2+2, a[i]); } $ gcc pointertest4.c && ./a &a[0]=0x aa90 p=0x aa92 *p=0x a[0]=0x a[1]=0x a[2]=0x a[3]=0x a[4]=0x a[5]=0x a[6]=0x a[7]=0x a[8]=0x a[9]=0x 結果が正しいかどうかは別として 配列の途中のアドレスを ポインタに入れることも出来る

30 プログラムの実行時に 配列のサイズを適宜に決める事が必要
動的配列 多くの問題では 配列のサイズを事前に (コンパイルの段階では) 決められない。 実行時、プログラムに 与えるデータや パラメータによって 配列のサイズは決まる。 ＝ プログラムの実行時に 配列のサイズを適宜に決める事が必要 malloc, calloc, realloc, free 関数

31 malloc 関数 void *malloc(site_t size); 引数: 戻り値 動的にメモリを確保する
確保したメモリへのポインタを返す 確保したメモリの内容は初期化されない エラーの場合は NULL を返す JM: malloc (3)

32 calloc 関数 void *calloc(site_t nobj, site_t size); 引数: 戻り値 動的にメモリを確保する
確保したメモリへのポインタを返す 確保したメモリの内容は0で初期化される エラーの場合は NULL を返す JM: malloc (3)

33 realloc 関数 void *realloc(void *p, site_t size); 引数: 戻り値
動的に確保したメモリのサイズを変更する 引数: p: サイズを変更するメモリへのポインタ size: 変更後のバイト数 戻り値 確保したメモリへのポインタを返す サイズ変更前後で小さい方のサイズまでは 前の内容が維持される 増加した部分のメモリの内容は初期化されない エラーの場合は NULL を返す 元のブロックは維持される JM: malloc (3)

34 free 関数 void free(void *p); 引数: 動的に確保したメモリを解放する p: 解放するメモリへのポインタ
JM: malloc (3)

35 関数の作成 演習

36 演習: is_leap_year～.c の関数化

37 演習: is_odd.c print_evenodd.c を参考に以下の関数を作りなさい int is_odd(int i); 引数 戻り値
奇数かどうか判定する 引数 i: 判定する整数 戻り値 奇数なら1、奇数でなければ0を返す is_odd_test.c と共にコンパイルして動作を確認すること 追加 Cygwin64+mintty+bash+GNU C $ gcc is_odd_test.c is_odd.c && ./a i = ? 1 odd number

38 演習: is_even.c print_evenodd.c を参考に以下の関数を作りなさい int is_even(int i); 引数
偶数かどうか判定する 引数 i: 判定する整数 戻り値 偶数なら1、偶数でなければ0を返す is_even_test.c と共にコンパイルして動作を確認すること 追加 Cygwin64+mintty+bash+GNU C $ gcc is_even_test.c is_even.c && ./a i = ? 2 even number

39 演習: is_prime.c print_isprime.c を参考に以下の関数を作りなさい int is_prime(int i); 引数
素数かどうか判定する 引数 i: 判定する整数 戻り値 素数なら1、素数でなければ0を返す is_prime_test.c と共にコンパイルして動作を確認すること 追加 Cygwin64+mintty+bash+GNU C $ gcc is_prime_test.c is_prime.c && ./a i = ? 7 prime number

40 演習: swapi.c 以下の関数を作りなさい void swapi(int *a, int *b); 引数
引数で与えた変数の値を交換する 引数 a, b: 値を交換する変数へのポインタ swapi_test.c と共にコンパイルして動作を確認すること 追加 Cygwin64+mintty+bash+GNU C $ gcc swapi_test.c swapi.c && ./a a = ? 1 b = ? 2 a = 2 b = 1 ヒント 第6週資料pp 本資料 p.6. を参考にせよ

41 演習: ヘッダファイルの作成 ここまでに作った is_odd, is_even, is_prime, swapi 関数のプロトタイプ宣言を myfunc.h というファイルにまとめよ。 第4週資料p.38.のis_leap_year_func.hを参考にせよ。 include ガードの識別子は MYFUNC_H とせよ。 誤:3週資料 正:4週資料

42 エラトステネスのふるい N以下の整数について既知の素数とその倍数をふるい落とすことで素数を判定するアルゴリズム 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

43 エラトステネスのふるい 𝑁以下の素数の探索 2以上𝑁以下の整数を探索リストに入れる
検索リストの先頭の数𝑥 (これは素数)が𝑥≤ 𝑁 なら ステップ3 そうでなければステップ4へ 𝑥を素数リストに移し 𝑥の倍数を探索リストから ふるい落とした後 ステップ2に戻る 探索リストに残った数を 素数リストに移動 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

44 エラトステネスのふるい 𝑁以下の素数の探索 2以上𝑁以下の整数を探索リストに入れる
探索リスト先頭の数は素数 先頭の2を素数と判定し 2の倍数を探索リストから削除する 𝑁以下の素数の探索 2以上𝑁以下の整数を探索リストに入れる 検索リストの先頭の数𝑥 (これは素数)が𝑥≤ 𝑁 なら ステップ3 そうでなければステップ4へ 𝑥を素数リストに移し 𝑥の倍数を探索リストから ふるい落とした後 ステップ2に戻る 探索リストに残った数を 素数リストに移動 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

45 エラトステネスのふるい 𝑁以下の素数の探索 2以上𝑁以下の整数を探索リストに入れる
探索リスト先頭の数は素数 先頭の3を素数と判定し 3の倍数を探索リストから削除する 𝑁以下の素数の探索 2以上𝑁以下の整数を探索リストに入れる 検索リストの先頭の数𝑥 (これは素数)が𝑥≤ 𝑁 なら ステップ3 そうでなければステップ4へ 𝑥を素数リストに移し 𝑥の倍数を探索リストから ふるい落とした後 ステップ2に戻る 探索リストに残った数を 素数リストに移動 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

46 エラトステネスのふるい 𝑁以下の素数の探索 2以上𝑁以下の整数を探索リストに入れる
探索リスト先頭の数は素数 先頭の5を素数と判定し 5の倍数を探索リストから削除する 𝑁以下の素数の探索 2以上𝑁以下の整数を探索リストに入れる 検索リストの先頭の数𝑥 (これは素数)が𝑥≤ 𝑁 なら ステップ3 そうでなければステップ4へ 𝑥を素数リストに移し 𝑥の倍数を探索リストから ふるい落とした後 ステップ2に戻る 探索リストに残った数を 素数リストに移動 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

47 エラトステネスのふるい 𝑁以下の素数の探索 2以上𝑁以下の整数を探索リストに入れる
探索リスト先頭の数は素数 先頭の7を素数と判定し 7の倍数を探索リストから削除する 𝑁以下の素数の探索 2以上𝑁以下の整数を探索リストに入れる 検索リストの先頭の数𝑥 (これは素数)が𝑥≤ 𝑁 なら ステップ3 そうでなければステップ4へ 𝑥を素数リストに移し 𝑥の倍数を探索リストから ふるい落とした後 ステップ2に戻る 探索リストに残った数を 素数リストに移動 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

48 エラトステネスのふるい 𝑁以下の素数の探索 2以上𝑁以下の数を探索リストに入れる
先頭の11は≤ 100 でないので 探索リストに残った数を素数と判定 𝑁以下の素数の探索 2以上𝑁以下の数を探索リストに入れる 検索リストの先頭の数𝑥 (これは素数)が𝑥≤ 𝑁 なら ステップ3 そうでなければステップ4へ 𝑥を素数リストに移し 𝑥の倍数を探索リストから ふるい落とした後 ステップ2に戻る 探索リストに残った数を 素数リストに移動 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

49 エラトステネスのふるい 通常の配列による探索リスト
メモリ上のイメージ 添字 探索リストの初期化 2 #define N 100 int i, j = 2, n = N; // n は探索リストの件数 int slist[N-2]; for (i = 0; i < n; i++) { slist[i] = j++; } 3 1 4 2 5 3 6 4 7 5 8 6 訂正 誤:slist[N-1] 正:slist[N-2] 訂正 誤:n = N 正:n = N - 2 : n-1 100 98

50 エラトステネスのふるい 通常の配列による探索リスト
値の削除 添字 添字 2 2 普通の配列だと 値を削除して 詰める処理に 時間がかかる 3 1 3 1 4 2 5 2 4を削除 5 3 6 3 6 4 7 4 7 5 8 5 8 6 : : n-1 100 97 n-1 100 98 100 98

51 エラトステネスのふるい 通常の配列による探索リスト
探索リストの消費メモリ 2以上N以下の数を配列に保存すると Nが32bitで表現可能な整数と仮定して 初期状態で(N-1)*4バイト必要 普通の配列だと 値を削除して 詰める処理に 時間がかかる 探索リストの初期化 探索リストから値xの削除 #define N 100 int i, j = 2, n = N-2; // n は探索リストの件数 int slist[N-2]; for (i = 0; i < n; i++) { slist[i] = j++; } for (i = 0; i < n; i++) { if (slist[i] == x) { for (j = 0; i + j + 1 < n; j++) { slist[i + j] = slist[i + j + 1]; // ↑ 探索リストから x を削除し // ↑ 以降の値を１つずつずらして詰める } n--; // 探索リストの件数をxを削除した分減らす break; 訂正あり p.49.参照

52 エラトステネスのふるい 通常の配列による探索リスト
探索リストの消費メモリ 2以上N以下の数を配列に保存すると Nが32bitで表現可能な整数と仮定して 初期状態で(N-1)*4バイト必要 探索リストで値xの判定 for (i = 0; i < n; i++) { if (slist[i] == x) { // x が探索リストにある場合の処理 break; }

53 エラトステネスのふるい 通常の配列による探索リスト
値の削除を工夫 添字 添字 使ってない値を マイナスにして 検索時に 無視すると 削除は速くなるが 値の検索でごみ になった-1も 処理しなければ いけなくなる 2 2 3 1 3 1 4 2 -1 2 4を削除 5 3 5 3 6 4 6 4 7 5 7 5 8 6 8 6 : : マイナス値も 扱う場合は 使えない方法 n-1 100 98 n-1 100 98

54 エラトステネスのふるい 通常の配列による探索リスト
探索リストの消費メモリ 2以上N以下の数を配列に保存すると Nが32bitで表現可能な整数と仮定して 初期状態で(N-1)*4バイト必要 削除は速いが 検索時にゴミも 検索するので 検索が遅くなる 探索リストの初期化 探索リストから値xの削除 #define N 100 int i, j = 2, n = N-2; // n は探索リストの件数 int slist[N-2]; for (i = 0; i < n; i++) { slist[i] = j++; } for (i = 0; i < n; i++) { if (slist[i] == x) { slist[i] = -1; // ↑ 探索リストから x を削除 break; } 訂正 誤:slist[i+j] 正:slist[i] 訂正あり p.49.参照

55 エラトステネスのふるい 通常の配列による探索リスト
探索リストの消費メモリ 2以上N以下の数を配列に保存すると Nが32bitで表現可能な整数と仮定して 初期状態で(N-1)*4バイト必要 探索リストで値xの判定 for (i = 0; i < n; i++) { if (slist[i] == x) { // x が探索リストにある場合の処理 break; }

56 エラトステネスのふるい 1方向リストによる探索リスト
訂正 誤:slist[N][2] 正:slist[N-1][2] メモリ上のイメージ 探索リストの初期化 添字 #define N 100 int i, j = 2; int slist[N-1][2]; for (i = 0; i < N - 2; i++) { slist[i][0] = j++; slist[i][1] = i+1; // 次の値の格納位置 } slist[i][1] = -1; // 終端記号 訂正 誤:i<N-1でしたが 正:i<N-2の誤りでした 2 [0][0] 1 [0][1] 3 [1][0] 2 [1][1] 4 [2][0] 訂正 誤:slist[i][0] 正:slist[i][1] 3 [2][1] 5 [3][0] 2つの値をペアとして扱い 1つ目を次の値の格納場所の添え字 2つ目を格納値 として利用している 1つ目の値を ポインターっぽく 使っている : 99 [98][1] ? [99][0] マイナスの値を次の値がない目印 つまり終端記号として用いている N-1 -1 [99][1]

57 エラトステネスのふるい 1方向リストによる探索リスト
値の削除 添字 2 [0][0] 2 3 4 1 [0][1] 3 [1][0] 5 100 ? × 2 [1][1] 5 [2][0] 4を削除 4 [2][1] 5 [3][0] 2 3 5 : 99 [98][1] 5 100 ? × ? [99][0] N-1 -1 [99][1]

58 エラトステネスのふるい 1方向リストによる探索リスト
探索リストの消費メモリ 2以上N以下の数を配列に保存すると Nが32bitで表現可能な整数と仮定して 初期状態で(N)*4*2バイト必要 使わなくなった メモリは 無駄になるが 削除が高速 探索リストの初期化 探索リストから値xの削除 メモリが通常の配列の 倍必要 #define N 100 int i, j = 2; int slist[N-1][2]; for (i = 0; i < N - 2; i++) { slist[i][0] = j++; slist[i][1] = i+1; // 次の値の格納位置 } slist[i][0] = -1; // 終端記号 for (i = 0; 0 <= slist[i][1]; i=slist[i][1]) { if (slist[i][0] == x) { j = slist[i][1]; slist[i][0] = slist[j][0]; slist[i][1] = slist[j][1]; // ↑ 探索リストの x が格納されている要素を // ↑ 次の要素で上書き break; } 訂正あり p.56.参照

59 エラトステネスのふるい 1方向リストによる探索リスト
探索リストの消費メモリ 2以上N以下の数を配列に保存すると Nが32bitで表現可能な整数と仮定して 初期状態で(N)*4*2バイト必要 探索リストで値xの判定 for (i = 0; 0 <= slist[i][1]; i=slist[i][1]) { if (slist[i][0] == x) { // x が探索リストにある場合の処理 break; }

60 エラトステネスのふるい フラグ配列による探索リスト(int版)
メモリ上のイメージ 添字 探索リストの初期化 #define N 100 int slist[N+1] = {0}; 1 2 3 4 5 6 添え字をxとして考え 格納値がゼロなら有効 格納値が非ゼロなら無効 と考える : N 100

61 エラトステネスのふるい フラグ配列による探索リスト(int版)
値の削除 添字 添字 1 1 2 2 使ってない値を 非ゼロ 削除は速い 検索はごみも 検索するので あまり速くない 4を削除 3 3 4 1 4 5 5 6 6 : : N 100 N 100

62 エラトステネスのふるい フラグ配列による探索リスト(int版)
探索リストの消費メモリ 2以上N以下の数を配列に保存すると Nが32bitで表現可能な整数と仮定して 初期状態で(N+1)*4バイト必要 こんなに必要？ 探索リストの初期化 探索リストから値xの削除 検索しなくて良いので 削除は高速 #define N 100 int slist[N] = {0}; slist[x] = 1; 探索リストで値xの判定 if (!slist[x]) { // x が 0 の時の処理 // x が探索リストにある場合の処理 }

63 エラトステネスのふるい フラグ配列による探索リスト(char版)
探索リストの消費メモリ 2以上N以下の数を配列に保存すると 初期状態で(N+1)バイト必要 char で十分 必要メモリが 1/4になった もっと減 らせるのでは？ 探索リストの初期化 探索リストから値xの削除 検索しなくて良いので 削除は高速 #define N 100 char slist[N] = {0}; slist[x] = 1; 探索リストで値xの判定 if (!slist[x]) { // x が 0 の時の処理 // x が探索リストにある場合の処理 }

64 エラトステネスのふるい フラグ配列による探索リスト(1bit版)
探索リストの消費メモリ 2以上N以下の数を配列に保存すると 初期状態で(N+8)/8バイト必要 1bitでも十分 charの場合から 更に1/8になった 探索リストの初期化 探索リストから値xの削除 検索しなくて良いので 削除は高速 #define N 100 char slist[(N+8)/8] = {0}; slist[x/8] |= 1<<(x%8); 訂正 誤:slist[x/7] 正:slist[x/8] bit毎のOR演算による bitマスクを用いて 狙ったビットをONにする 探索リストで値xの判定 if (!(slist[x/8] & (1<<(x%8)))) { // x が 0 の時の処理 // x が探索リストにある場合の処理 } bit毎のAND演算による bitマスクを用いて 狙ったビットのON/OFFを調べる

65 演習: print_prime_lt～.c エラストテネスのふるいによりN未満の素数を小さい順に全て表示せよ
print_prime_lt_a1.c 通常の配列版(削除した値を詰めた場合) print_prime_lt_a2.c 通常の配列版(削除値を-1にした場合) print_prime_lt_b.c 一方向リスト版 print_prime_lt_c1.c フラグ配列int版 print_prime_lt_c2.c フラグ配列char版 print_prime_lt_c3.c フラグ配列1bit版

66 演習: print_prime_lt～.c 前頁で作成したプログラムについて速度を比較してみましょう
Cygwin の場合 time コマンドを用いると実行実感が計測出来ます。例えば ./a の実行時間を計測するには以下のようにします。 mintty+bash+GNU C $ time ./a

67 参考文献 [1] B.W.カーニハン/D.M.リッチー著 石田晴久 訳、プログラミング言語C 第2版 ANSI 規格準拠、共立出版(1989)