1 T HE U NIVERSITY OF T OKYO D EPARTMENT OF M ATHEMATICAL I NFORMATICS 数理情報工学演習第一Ｃ プログラミング演習 ( 第１回 ) 2015/04/06

2 T HE U NIVERSITY OF T OKYO  担当： – 担当教員： 定兼（数理 2 研） – 補佐：松島 （数理 6 研） – 学生アシスタント：宮口，呉，鈴木  担当へのコンタクト e メールアドレス （演習についての一般的な相談）：  資料 の資料公開 担当メンバー :

3 T HE U NIVERSITY OF T OKYO  PC はリース品です、扱いには十分に注意 – 原状復帰可能な形で返却 ステッカー等を貼らない （情報理工マークを隠さない） 「キレイに」使う – 最悪、実費負担の可能性もあります – 原則、構内での使用  セキュリティ／コンプライアンスに十分な注意を – P2P （危険度にかかわらず）全面禁止 情報理工ネットワーク、貸与 PC の両方において – ソフトウェアライセンスのないものは絶対に使わない – 無線 LAN のキーは部外者に教えない PC の扱いについての注意 :

4 T HE U NIVERSITY OF T OKYO  評価基準 – 提出課題 – 出席 （指示のないかぎり 13:00-16:00 の間は在室する） – 出席態度 評価 :

5 T HE U NIVERSITY OF T OKYO  狙い：プログラミングに親しむ – 卒論や実験等にむけたプログラミングの練習  初心者：プログラミングに慣れてもらう – 本演習はこちらを主に想定  中上級者： 別途上級の課題を用意 演習のねらい :

6 T HE U NIVERSITY OF T OKYO  前半にその回の基礎的な内容を説明 – プログラミング言語そのものの説明はしない  後半は実際に貸与 PC を用いてプログラミング – 使用言語は C – 個人の PC を用いても構わない  課題の提出 演習の形式 :

7 T HE U NIVERSITY OF T OKYO  電源を入れる  Ubuntu を選択（一番上の選択肢）  ログイン  ネットワークへの接続  ソフトウェアの更新 さわってみよう :

8 T HE U NIVERSITY OF T OKYO  テキストエディタ – Dash ホームにあるものを使う（他のものでも可）  コンパイラ – gcc （インストール済）  デバッガ – gdb （インストール済） – valgrind (Ubuntu ソフトウェアセンターからインストール ) – valkyrie (valgrind の詳細情報から ) ソフトウェア :

9 T HE U NIVERSITY OF T OKYO  デスクトップの “ 端末 ” を起動  ホームディレクトリ： /home/mistpc/ – 画面左上の “ ホームフォルダ ” でもアクセス可能 端末の起動 :

10 T HE U NIVERSITY OF T OKYO  ディレクトリ（フォルダ）を作る – mkdir 1 ( 今回の作業フォルダをつくる ) – cd 1 ( 「 1 」ディレクトリに移動 )  テキストエディタで新規作成して test.c という名前で保存 – 保存場所はホームの 1 というディレクトリ ファイルの作成 :

11 T HE U NIVERSITY OF T OKYO  「 test.c 」を入力  入力後、保存（ Ctrl+S ） プログラムの入力 : /* test.c */ #include int main() { printf("Hello.  ∖ n I am. ∖ n ”) ; return 0; } 名前 入出力関連ヘッダの読み込み コメント 本体 画面に文字列を 表示 改行 ∖ はバックスラッシュ ( キーボードの右下 ) ． \ では駄目 行の終わり 正常終了時には 0 を返す

12 T HE U NIVERSITY OF T OKYO プログラムの書き方の作法  プログラムは基本的に入れ子 (nested) 構造をしている  入れ子のレベルに従って字下げ ( インデント ) をする #include int main() { int i, j, x; x = 0; for (i=0; i<100000; i++) { for (j=0; j<100000; j++) { x += j; } インデント i のループの中 j のループの中 j のループの終わり i のループの終わり main関数の終わり

13 T HE U NIVERSITY OF T OKYO  プログラムをコンピュータの実行形式に変換（コンパイル） – gcc test.c  ls ( 現在のフォルダの中身を見る ) すると、実行ファイル a.out ができているはず  「./a.out 」で実行 – 「. 」は現在のフォルダを表す – 「./a.out > out.txt 」も試してみる コンパイルと実行 : 標準出力の出力先を ファイルにする

14 T HE U NIVERSITY OF T OKYO  「 test2.c 」を入力  生成される実行ファイルの名前は変えられる – gcc –o test2.out test2.c printf の書式 : /* test2.c */ #include int main() { printf(”I am %s. ∖ n ”, ” ”) ; printf(”I was born in %d. ∖ n ”, ) ; return 0; } 文字列の書式 名前 年 整数の書式 文字列 整数

15 T HE U NIVERSITY OF T OKYO  「 test3.c 」を入力 変数を使用する : /* test3.c */ #include int main() { int year = ; char name[] = ” ”; printf(”I am %s.\n ”,name) ; printf(”I was born in %d.\n ”,year ) ; return 0; } 整数型変数の宣言 名前 年 変数名 文字型 配列

16 T HE U NIVERSITY OF T OKYO コンパイルの最適化  -O オプションをつける – gcc –O3 test.c – 数字は最適化レベル．大きいほど実行速度が速くなる． -O0 ( ゼロ ) は最適化無し  プログラムの実行時間を測定するときは必ず最適化し たものを使う – –O3 をつける

17 T HE U NIVERSITY OF T OKYO デバッグの仕方 :  コンパイル時に –g をつける – gcc test.c –g  デバッグ時は最適化をしない方がいい – 最適化により不要な命令が消去されることがある – ステップ実行をしにくい – （最適化したときのみバグが発生することもあるので難しい）  デバッグ実行には gdb を用いる  gdb では分からないエラーを見つけるには valgrind を使う

18 T HE U NIVERSITY OF T OKYO デバッグ実行 :  gdb./a.out  ソースの表示 : list [ 行番号 ]  実行 : run  ブレイクポイントの設定 : break [ 行番号 ]  ステップ実行 : step, next – step は関数の中も 1 行ずつ実行 – next は関数の実行後に停止  変数の表示 : print [ 変数名 ]

19 T HE U NIVERSITY OF T OKYO  「 test32.c 」を入力 どこにバグがあるでしょう : /* test32.c */ #include int main() { int year = ; char name[] = ” ”; printf(”I am %s.\n ”,year) ; printf(”I was born in %d.\n ”,name ) ; return 0; } 名前 年

20 T HE U NIVERSITY OF T OKYO gdb でステップ実行してみる  gdb./a.out  break 7 ( ７行目で一旦停止 )  run (a.out を実行 )  step で１行ずつ実行すると，どこで異常終了するか分かる  最初から１行ずつ実行すると時間がかかるので，バグが発生する 条件が分かっているならそこまでは通常実行する if (i > 10000) { printf(“break ∖ n”); ← ここにブレイクポイントを設定 }

21 T HE U NIVERSITY OF T OKYO 配列  整数の配列： int A[10];  実数の配列： double R[10];  配列の添え字は 0 から 9 (Fortran は 1 から )  for (i=0; i<10; i++) { printf(“R[%d] = %lf ∖ n”, i, R[i]); }  内積の計算 実数の表示には %lf x = 0.0; for (i=0; i<10; i++) { x += A[i] * B[i]; }

22 T HE U NIVERSITY OF T OKYO 関数の引数に配列 #include double inner_vector(double A[10], double B[10]) { double x; int i; x = 0.0; for (i=0; i<10; i++) x += A[i] * B[i]; return x; // 計算結果を返す } int main() { double A[10], B[10]; double x; int i; for (i=0; i<10; i++) { A[i] = (double)i; // 実数へ変換 B[i] = (double)(i+1); } x = inner_vector(A, B); printf("%lf ∖ n", x); } 実数を返す関数 関数の引数は実数の配列

23 T HE U NIVERSITY OF T OKYO  実は，引数の配列の長さは書かなくても同じ – 配列の長さはプログラマが把握  右のソースは，コンパイルはできるが異常終了 – 関数内で，配列の範囲外をアクセス #include double inner_vector(double A[], double B[]) { double x; int i; x = 0.0; for (i=0; i<10000; i++) x += A[i] * B[i]; return x; } int main() { double A[5], B[5]; double x; int i; for (i=0; i<5; i++) { A[i] = (double)i; B[i] = (double)(i+1); } x = inner_vector(A, B); printf("%lf ∖ n", x); }

24 T HE U NIVERSITY OF T OKYO 配列の長さ  C 言語では，配列の長さは分からない – 意味：実行時に長さを取得できない  汎用的な（配列の長さを変えられる）関数にするには，配列の長さ n も 引数に入れる double inner_vector(int n, double A[], double B[]) { double x; int i; x = 0.0; for (i=0; i<n; i++) x += A[i] * B[i]; return x; }

25 T HE U NIVERSITY OF T OKYO ポインタの使い方  計算機のメモリは単なる配列とみなせる – Mem(1), Mem(2),…, Mem(M) – メモリの添字は赤色で表すとする Mem

26 T HE U NIVERSITY OF T OKYO 通常の変数の宣言  C 言語 – int x, y;  実際に行われること – 変数の値を格納するメモリの領域を確保する – addr[x] = 1; addr[y] = 2 – 注：これはコンパイル時に行われ， addr[x], addr[y] は実行時には定数 となり変更できない Mem x y 変数名 addr x1 y2

27 T HE U NIVERSITY OF T OKYO 変数への代入  C 言語 – x = 10; y = 20;  実際に行われること – Mem[addr[x]] = Mem x y 変数名 addr x1 y2 変数名からアドレス への変換表

28 T HE U NIVERSITY OF T OKYO ポインタ変数の定義  C 言語 – int x; – int *p;  実際に行われること – ポインタの値を格納するメモリの 領域を確保する – addr[p] = 3 – 注 : addr[p] は実行中に変更不可 Mem x y 変数名 addr x1 y2 p3 p 20

29 T HE U NIVERSITY OF T OKYO ポインタへの代入  C 言語 – p = &x;  実際に行われること – p が x のアドレスを指すようにする – Mem[addr[p]] = addr[x] – (Mem[3] = 1) – 注 : addr[p] = 3 は実行中に変更不可 Mem[3] は実行中に変更可 Mem x yp 変数名 addr x1 y2 p3 20

30 T HE U NIVERSITY OF T OKYO ポインタで表された変数への代入  C 言語 – *p = y  実際に行われること – メモリから p の値を読み，その番地に書き込む – Mem[Mem[addr[p]]] = Mem[addr[y]] – (Mem[Mem[3]] = Mem[2]) – (Mem[1] = 20) Mem x yp 変数名 addr x1 y2 p3 20

31 T HE U NIVERSITY OF T OKYO 変数の動的な割り当て  C 言語 – p = malloc(sizeof(int));  実際に行われること – 未使用のメモリ領域が確保され， そのアドレスが p に入る Mem[addr[p]] = 4 – それまで p で指されていた領域 (1) は，他のポインタから指されていなけ れば，もう使えない ( メモリリーク ) Mem x yp 20 変数名 addr x1 y2 p3

32 T HE U NIVERSITY OF T OKYO 長さ既知の配列の定義  C 言語 – int a[3];  実際に行われること – 指定された長さのメモリ領域を確保 – addr[a] = 4..6 – (C 言語では配列の長さは参照不可 ) Mem x yp 20 変数名 addr x1 y2 p3 a4..6 a

33 T HE U NIVERSITY OF T OKYO 配列への代入  C 言語 – a[1] = 10; – ( 添字は 0 から )  実際に行われること – Mem[addr[a]+1] = 10 – (Mem[4+1] = 10) Mem x yp 20 変数名 addr x1 y2 p3 a4..6 a

34 T HE U NIVERSITY OF T OKYO 長さ未定の配列の定義  C 言語 – int *a; – int b[3]; – a = b; // a は 5..7 – a = malloc(3*sizeof(int)); // a は Mem p 20 変数名 addr x1 y2 p3 a4 b a 5 a b

35 T HE U NIVERSITY OF T OKYO 確保したメモリの解法  C 言語 – free(a)  実際に行われること – a で指されているメモリの番地から始まる，以前確保された領域 の使用を中止し，次に確保する際に使用できるようにする – 開放した後にそこに読み書きを行うとバグ（不具合）の原因になる

36 T HE U NIVERSITY OF T OKYO 引数の値渡しと参照渡し  値渡し (call by value) – 値をコピーしてサブルーチンに渡す – サブルーチン内で値を変更しても元の値は変化しない  参照渡し (call by reference) – 変数へのポインタをサブルーチンに渡す – サブルーチン内で値を変更すると，元の値も変化する  C 言語は値渡し， Fortran は参照渡し

37 T HE U NIVERSITY OF T OKYO C 言語の場合 #include void sub_value(int x) { x = x + 1; printf("sub_value: x = %d ∖ n", x); } void main(void) { int x; x = 1; printf("main: x = %d ∖ n", x); sub_value(x); printf("main: x = %d ∖ n", x); } 実行結果 main: x = 1 sub_value: x = 2 main: x = 1

38 T HE U NIVERSITY OF T OKYO Fortran の場合 program main integer x x = 1 print *, "main: x =", x call sub(x) print *, "main: x =", x contains subroutine sub(x) integer x x = x + 1 print *, "sub: x =", x end subroutine end program main 実行結果 main: x = 1 sub: x = 2 main: x = 2

39 T HE U NIVERSITY OF T OKYO ポインタの中身を参照 引数がポインタの場合 void sub_reference(int *x) { *x = *x + 1; printf("sub_reference: x = %d ∖ n", *x); } void main(void) { int y; y = 1; printf("main: y = %d ∖ n", y); sub_reference(&y); printf("main: y = %d ∖ n", y); } x は整数変数へのポインタ y のアドレス 実行結果 main: y = 1 sub_reference: x = 2 main: y = 2

40 T HE U NIVERSITY OF T OKYO 引数が配列の場合  配列は参照渡しになる void sub_reference(int x[]) { x[0] = x[0] + 1; printf("sub_reference: x = %d ∖ n", x[0]); } void main(void) { int y[1]; y[0] = 1; printf("main: y = %d ∖ n", y[0]); sub_reference(y); printf("main: y = %d ∖ n", y[0]); } 実行結果 main: y = 1 sub_reference: x = 2 main: y = 2

41 T HE U NIVERSITY OF T OKYO メモリ確保  ポインタは宣言しただけではメモリは確保されず，初期値は不定  不定なアドレスを読み書きすると通常は segmentation fault で終了  たまたま動く場合も，他の変数の値を破壊することがある  malloc 関数で必要なサイズ ( 以上 ) の領域を確保する必要がある void main(void) { int *y; *y = 1; printf("main: y = %d ∖ n", *y); } y をポインタとして宣言 間違い void main(void) { int *y; y = malloc(sizeof(int)); *y = 1; free(y); } 正解 整数 1 つ分の 領域を確保 メモリのどこに書かれる か分からない

42 T HE U NIVERSITY OF T OKYO エラーチェック  malloc に必要なメモリが無い場合はエラー  返り値が NULL かどうかチェックする y = malloc(sizeof(int)); if (y == NULL) { printf(“Not enough memory. ∖ n”); exit(1); // プログラム終了 } *y = 1;

43 T HE U NIVERSITY OF T OKYO 長さ可変の配列・ポインタ  int A[n]; などは（基本的には）できないので，動的に確保する  int *A; // A は整数型へのポインタ  A = malloc(sizeof(int)*n); // 整数 n 個分の領域を確保してそのアドレス を A に代入  free(A); // 使わなくなった領域を開放する 整数 1 個が何バイトかを返す．通常は 4 バイト． for (i=0; i<n; i++) { A[i] = 0; }

44 T HE U NIVERSITY OF T OKYO ポインタの演算  整数へのポインタを 1 増やすと，アドレスが整数 1 個分増える  配列の要素は連続したアドレスに格納されるので，ポインタを 1 ずつ増やす と配列の要素に順番にアクセスできる  配列の長さを超えてもポインタは増やせるのでバグに注意 – コンパイルはできるが実行するとエラー int A[10]; for (i=0; i<10; i++) { A[i] = 0; } int *p, A[10]; p = A; for (i=0; i<10; i++) { *p = 0; p += 1; } *p++ = 0; とも書ける

45 T HE U NIVERSITY OF T OKYO 変数を格納するメモリ領域 /* test4.c */ #include int a[10]; // グローバル変数 ( どの関数からもアクセス可 ) int main() { int b[10]; // ローカル変数 ( この関数内からのみアクセス可 ) int *c; // 動的に確保する領域へのポインタ int i; printf("Address of a = %p, size of a[i] = %d bytes\n", a, (int)sizeof(a[0])); for (i=0; i<10; i++) printf("Address of a[%d] = %p\n", i, &a[i]); printf("Address of b = %p, size of b[i] = %d bytes\n", b, (int)sizeof(b[0])); for (i=0; i<10; i++) printf("Address of b[%d] = %p\n", i, &b[i]); c = (int *)malloc(10*sizeof(*c)); // ヒープにメモリを確保 printf("Address of c = %p, size of c[i] = %d bytes\n", c, (int)sizeof(c[0])); for (i=0; i<10; i++) printf("Address of c[%d] = %p\n", i, &c[i]); printf("Address of &a = %p, sizeof(&a) = %d bytes\n", &a, (int)sizeof(&a)); printf("Address of &b = %p, sizeof(&b) = %d bytes\n", &b, (int)sizeof(&b)); printf("Address of &c = %p, sizeof(&c) = %d bytes\n", &c, (int)sizeof(&c)); free(c); return 0; }

46 T HE U NIVERSITY OF T OKYO 実行例 %./a.out Address of a = 0x601060, size of a[i] = 4 bytes Address of a[0] = 0x Address of a[1] = 0x Address of b = 0x7fff0347a1a0, size of b[i] = 4 bytes Address of b[0] = 0x7fff0347a1a0 Address of b[1] = 0x7fff0347a1a4 Address of c = 0x143d010, size of c[i] = 4 bytes Address of c[0] = 0x143d010 Address of c[1] = 0x143d014 Address of &a = 0x601060, sizeof(&a) = 8 bytes Address of &b = 0x7fff0347a1a0, sizeof(&b) = 8 bytes Address of &c = 0x7fff0347a198, sizeof(&c) = 8 bytes a[0] a[1] 0x c[0] c[1] 0x143d010 b[0] b[1] 0x7fff0347a1a0 0x7fff0347a198 &c 実行前に確保される 領域（サイズ不変） 実行中に確保される 領域（サイズ可変） 実行中に確保される 領域（サイズ不変）

47 T HE U NIVERSITY OF T OKYO プログラミングの練習のできるサイト  Aizu Online Judge(AOJ) Aizu Online Judge(AOJ) – まずアカウントを作成する – 問題セットのところに各種演習問題がある – プログラムを入力すると正常に動作するかテストしてくれる  参考 「競技プログラミング入門」

48 T HE U NIVERSITY OF T OKYO 課題提出用サイト（構築中）   Login: 学生証番号 ( 数字 8 ケタ )  Password:  ログイン後に， problems の p1 (Hello World) を見てみる  注：大学内からのみアクセス可能

49 T HE U NIVERSITY OF T OKYO 第一回課題 : // プログラミング演習第 1 回課題 // 1 から 100 までを表示するプログラム // 実行するとどのようなバグが出るか試す // 正しく動作するように修正する #include int main() { int *a; int i; for (i=1; i<=100; i++) { a[i] = i; } for (i=0; i<100; i++) { printf("%d\n", a[i]); } return 0; }

50 T HE U NIVERSITY OF T OKYO  課題提出用サイトで問題 mipro1 の回答を提出する ( 必須では無い )  レポートを作成する – gdb, valgrind 等で実行するとどのようなエラーが出るか ( コンパイル時には –g をつけておく ) – 元のプログラムにどのようなバグがあったか – どのように修正したか  締切： 2015 年 4 月 6 日 ( 月 ) ( 本日 ) 第一回課題 : へメールする