情報処理 Ⅱ 2011 年 10 月
情報処理 Ⅱ について 担当は村川猛彦 (takehiko@sys.wakayama u.ac.jp) プログラミング基礎 Ⅱ ( 松田先生 ) と連携して実施 演習の疑問や誤解を講義で解説し, 講義で紹介する技法を演習で活用する. 成績評価は別々. 目標 : 情報処理 Ⅱ および プログラミング基礎 Ⅱ を通じて, Cで数十行程度のプログラムが自在に作成できるようになること. 予習は基本的に不要. 小テストは参考書から出題する. 授業内容の復習は, 毎回行うこと. 2
成績評価の方法 レポート ( 冬休み ):20 点満点 期末試験 (2 月 ):80 点満点 自筆ノート 1 冊参照可, 教科書 配付資料は参照不可. 毎回授業中に実施する小テスト ( アンケートのことも ) は, 成績に加味しない. しかし, 内容を着実に理解するには毎回出席するのが一番! 3
教科書 参考書について 教科書 林晴比古 C 言語クイック入門 & リファレンス, ソフトバンククリエイティブ,ISBN9784797359992 文法解説主体のリファレンス ipad 用電子書籍もある 授業で読み上げ解説するので, 購入し, 毎回持参すること 参考書 村山公保 C プログラミング入門以前, 毎日コミュニケーションズ,ISBN4839920648 プログラミング基礎 Ⅰ の教科書 基礎と考え方を重視 この授業では持参しなくてもよいが, 小テストはここから出す 4
電子機器の授業中の使用について この授業では ( 今年度の実験的試みとして ), 電子機器の使用を認める. ノート PC,iPad, タブレット端末, スマートフォンなど 授業 Web ページや他の Web コンテンツを参照してよい. 自分で例題プログラムを動かしてみてもよい. 音声通話は不可 使用した学生は, 小テスト解答用紙の 日 の右に印をつけること. その使用が, 授業の内容理解の役に立ったなら, 役に立たなかったら, 塗りつぶす 塗りつぶさない 5
セメスター 1 科目 情報処理 Ⅰ プログラミング基礎 Ⅰ 他の科目との関連 内容 リテラシープログラミングの入門 目標 計算機に慣れる 2 情報処理 Ⅱ プログラミング基礎 Ⅱ プログラミングと C の基礎 ( 講義 ) プログラミングと C の基礎 ( 演習 ) プログラミングを学ぶ 3 アルゴリズム演習 Ⅰ プログラミングとCの基礎 ( 演習 ) Cプログラミング基礎演習プログラミングとCの基礎 ( 復習 ) 情報処理 Ⅲ Java,OOP 他のプログラミングパラダイム C で自在にプログラミング 4 5 オブジェクト指向 情報ネットワーク演習 ビジュアル情報演習 C++,OOP 通信 2D & 3D 画像処理 専門科目の内容をプログラミングで確認 6 7 ~ 情報通信システム演習卒業研究 研究室配属. 研究テーマに応じたプログラム作成 6
プログラミングにまつわる用語 プログラミング (programming) プログラムを作ること プログラム (program) プログラミングの結果, 作られたファイル 実行可能なファイルを作って計算機に渡すことで, プログラムの指示通りに動作する. Cのファイルは実行可能ではなく ( ソースファイルと呼ばれる ), コンパイラを用いて, 実行ファイルに変換する. プログラムの指示 プログラマ (programmer) の意図 コマンド (command) 計算機に何をしてもらうか指示すること 7
プログラミングの順序 目的 アイデア プログラミング ( テキストエディタ ) (C などで書いた ) ソースファイル エラー コンパイル ( コンパイラ ) 実行 失敗 実行ファイル バイナリ とも呼ばれる 実行可能なファイル 成功! 8
なぜプログラミングをするのか? 高速 高精度が要求される処理が可能 ロボット, 車などの 制御 データの 整理整頓, 整形出力など 他の計算機 プロセス デバイスとの 通信 問題解決に要する時間を短縮 それは, 自分がすべき仕事か? それは, 計算機に向いた仕事か? デザインツール 計算機にさせたいことを, 主体的に決めて指示する. 人の 作ったもの を見て, 価値を評価できる. これから作るもの のコスト( 時間, 金銭, 人的 ) を見積もる. 9
なぜ C?(1) 有名なプログラミング言語 C,C++ Java 情報処理 Ⅲ で 非手続き型言語 : Lisp,Prolog,SQL Lightweight Language: Perl,PHP,Python,Ruby 数値処理 統計処理 : MATLAB,S (S PLUS, R) Pascal,Fortran,COBOL,BASIC,PL/Ⅰ,ALGOL JavaScript (JScript, ECMAScript) シェルスクリプト, バッチファイルアセンブリ言語 注 : は学科授業で使用しているプログラミング言語 10
なぜ C?(2) 普及しているプログラミング言語 適度に高級, 適度に低級 高級 ( 高水準 ): 人間が読み書きしやすい. 低級 ( 低水準 ): 計算機向けの記述がしやすい. プログラミング言語や使用者の優劣ではない. 他のプログラミング言語の習得に役立つ 実用的な多くのプログラミング言語が,C の影響を受けて設計された. C は, プログラミング言語の世界の 英語 のようなもの! 11
行列の積 (1) 2 行 2 列の行列の積 C=AB A = a 11 a 12 B = b 11 b 12 a 21 a 22, b 21 b 22 C = c 11 c 12 a 11 a 12 b 11 b 12 = = c 21 c 22 a 21 a 22 b 21 b 22 a 11 b 11 +a 12 b 21 a 11 b 12 +a 12 b 22 a 21 b 11 +a 22 b 21 a 21 b 12 +a 22 b 22 A,Bの成分を自由に変更して, 積を求める処理を定型化できないか 行列の積を求めるプログラムを作る! 1 2 0-1 3-1 1 2 =, -2-4 1 2 2 = 12
行列の積 (2) プログラムの作り方 動かし方 テキストエディタ (Emacs) でソースファイルを作り, 保存する ( ここでは matrix22.c というファイル名にする ). ターミナル (GNOME 端末など ) で cc matrix22.c を実行する. コンパイルが成功すれば,a.out という実行ファイルができる. 続いてターミナルで./a.out を実行する. Web で参照可能. 復習に役立ててください. 20111003/matrix22.c 13
プログラムの定型 Cプログラムの定型 #include <stdio.h> int main(void) { 3ブロック開始... 4 処理 return 0; 読み方 1 インクルード文 2 メイン関数の宣言 5メイン関数の終了 } 6ブロック終了 stdio.h スタンダード アイ オー ドット ヘッダ int イント 14
printf printf("%d n", x); その時点のxの値を十進数で出力する. x=3のとき, 3 を出力する( 画面に 3 が表示される). x=5のとき, 5 を出力する. printf("%d / 2 => %d n", x, x / 2); x=10のとき, 10 / 2 => 5 を出力する. x=16のとき, 16 / 2 => 8 を出力する. printf("ok n"); 変数の値に関係なく, OK を出力する. n は改行文字. 15
括弧類 ( ) 式や構文の一部 a = (b + c) / 2; if (a == 1) { } ブロック [ ] 配列の参照 < > ヘッダファイルの指定 #include <stdio.h> ( ) の中に ( ) がある状態を, カッコの入れ子 という いずれも他の括弧記号に置き換えることはできない ( ),{ },[ ] はネスト ( 入れ子 ) にできる printf("%d n", n * (n 1) / 2); 16
授業の進め方 プリプロセッサ指令 構造体 ファイル入出力 その他の型 記憶域管理関数 2 年以降でさらに学習 習熟 配列 文字列 ポインタ 識別子 算術型 関数 変数の有効範囲 制御文 演算子 再帰呼び出し ライブラリ関数 式評価 プログラムの作成 コンパイル 実行 17
配布資料について サンプルプログラムの配布資料は, 紙上でプログラムを 読む のを支援するためのもの. 見本 であって 理想 ではない. 書き込み推奨. 試験でも役に立つ. 資料をもらって安心しない. 重要なことはノートに書き, 復習しながら理解を深めること. 18
識別子 型 行列の積を求めるプログラムで, 変数を一つ使用するため と書いたが, これ以外にどんな書き方があるのか? a11は 識別子 intは 型 int a11 = 1; 19
変数名の慣習 変数名は,1 文字 ~ 数文字. もしくは, その用途がわかるものにする. a, b, c, filename, msg よく使う変数名 ループカウンタ : i, j, k 座標 : x, y 大文字は使わない 定数は大文字のみで書くのが慣例 (NULL,EOF など ) 20
型 (type) 変数や値がどのような種類の情報を持っているか C, C++, Java などのプログラミング言語では, 変数宣言時に型を指示しなければならない 型の違いの例 int i = 1; ( 整数の 1 ) double d = 1.0; ( 実数の 1 ) char c = '1'; ( 文字の 1 ) char *p = "1"; ( 文字列の 1 ) 21
整数型の範囲 整数型 (char,int,long など ) のとり得る値は その型を何バイト ( 何ビット ) で表現するか符号の有無 で決まる. nビットなら,2 進数を用いて2 n 種類の数値を表現できる. どの整数型も,0を表現できる. この授業では, 整数の表現として 2 の補数 を前提とする. 22
signed と unsigned signed ( 符号あり ) 負の数をとり得る整数 最小は, 2 n 1 最大は,2 n 1 1 unsigned ( 符号なし ) 負の数をとらない整数 最小は,0 最大は,2 n 1 signed も unsigned も書かなかったら 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 int, short, longでは 符号あり と決まっている charでは処理系に依存 n=8 のビットパターン 23
浮動小数点とは? 科学技術計算では,602000000000000000000000 を 6.02 10 23 と書く. 計算例 :(6.02 10 23 ) 10 = 6.02 10 24 ( 符号 ) 仮数 底指数による表現を, 浮動小数点形式という. ただし 1 仮数 < 底, 指数は整数 (0 や負でもよい ) 底 は 基数 とも言う. 計算例 :(6 10 2 ) (6 10 2 ) = (6 6) 10 2+2 = 36 10 4 = 3.6 10 5 2 を底とする浮動小数点形式で表されることが多い. 例 : 0.625 (=1/2+1/8) は, 1.01 (2) * 2 1 24
実数型の範囲 仮数と指数をそれぞれ何ビットで表現するかによって, 取り得る値が決まる. 単精度の例 : 符号 1 ビット + 仮数部 23 ビット + 指数部 8 ビット =32 ビット (4 バイト ) 倍精度の例 : 符号 1 ビット + 仮数部 52 ビット + 指数部 11 ビット =64 ビット (8 バイト ) ビット数の制約があるため, あらゆる実数を表すことはできない. 表現できない数の例 :10 1000, 2,π 25
代入で変数の値を交換 コード抜粋 int x = 2; int y = 3; x = x + y; y = x y; x = x y; それぞれの代入で,x と y の値は何になるか? x と y の初期値をいろいろ変えて実行させても, 必ず値を交換するのか? xyyx.c 26
変数の値を交換する他の方法 交換用の変数を介する int x = 2; int y = 3; int tmp; tmp = x; x = y; y = tmp; 値を交換 と言えば普通はこれ 変数を多用 int x = 2, y = 3, v1, v2, v3; v1 = x + y; v2 = v1 y; v3 = v1 x; y = v2; x = v3; tmp x x: y: y 授業では資料配付していませんが,Web で参照可能です. v1: v2: v3: xyyx2.c 27
ダイクストラの構造化プログラミング プログラムは, 順接, 反復, 分岐 の組み合わせで表現できる. 順接反復分岐 処理 1 条件 条件 処理 2 処理 条件を満たすときの処理 条件を満たさないときの処理 28
for 文 構文 for ( 初期化 ; 条件 ; 増分 ) { 処理 } 最初に 条件 を満たしていなければ,1 回も 処理 をしない. 初期化 条件 処理 増分 29
0, 0.1,..., 1.0 を出力するには ループ用の変数 i は整数型にする. for 文を用いて,i の値を 0, 1,..., 10 と変えるようにする. i * 0.1 は,0, 0.1,..., 1.0 となる. for (i = 0; i <= 10; i++) { i の初期値は 0 i は 10 まで (for i less than or equal to 10) i の値を 1 増やす i = i + 1 と等価 from0to1.c 30
while 文 構文 while ( 条件 ) { 処理 } 最初に 条件 を満たしていなければ,1 回も 処理 をしない. 条件 処理 31
} do 文 (do~while) 構文 do { 処理 while ( 条件 ); 少なくとも 1 回は 処理 をする. セミコロンを忘れずに 処理 条件 32
多重ループの準備 大小のサイコロ 1 個ずつを振ったときの出目は何種類? ( 大, 小 )=(1,1),(1,2), (6,6) の36 種類. しかし全てを数え上げるのは手間がかかるし, 間違いも起こりやすい. 大の出目は1~6のいずれか. そのそれぞれに対して, 小の出目は1~6のいずれか. したがって6 6=36 種類. 33
九九プログラム 方針 1 i 9, 1 j 9 の各 (i,j) について,i * j を計算する. 1 j 9 のそれぞれの j の値に対して, 1 i 9 のそれぞれの i の値との積を計算し, 出力する kuku.c for (j = 1; j <= 9; j++) { for (i = 1; i <= 9; i++) { printf("%2d ", i * j); } printf(" n"); } for 文の入れ子 ( ネスト ) を使用 i=3, j=9 34 : 改行
ループの用語 ループ (loop): 反復のこと for ループ, while ループ などという. ループカウンタ : 反復処理を制御する変数のこと.for 文の中で使われる. 2 重ループ : ループの中にループを書くこと 多重ループ :2 重ループ,3 重ループ,4 重ループ の総称 35
} if 文 構文 if ( 条件 ) { 処理 条件 } 処理 if ( 条件 ) { 条件を満たすときの処理 } else { 条件を満たさないときの処理 条件 条件を満たすときの処理 条件を満たさないときの処理 36
case case 値 値 switch 文 (switch~case) 多分岐を実現するもう一つの方法 構文 switch ( 整数値 ) { 値 1: 1の処理 break; コロン 整数値 値 2: 2 の処理 break; 値 1 の処理 break 値 2 の処理 break それ以外の処理 default: それ以外の処理 } 整数値 は通常, 単一の変数または変数を含んだ式 値 1 値 2 は, コンパイル時に値の決まる定数式 37
case case 値 値 switch 文の中に break がなかったら 構文 switch ( 整数値 ) { } 値 1: 1 の処理 値 2: 2の処理 default: それ以外の処理 整数値 それ以外の処理 値 1 の処理 値 2 の処理 38
序数プログラム 方針 1 i 1000の各整数に対して (for 文を用いて ), その序数となる英単語を出力する 出力方法 printf("%dst", 1); 1st printf("%dnd", 2); 2nd printf("%drd", 3); 3rd printf("%dth", 4); 4th ordinal.c 39
序数プログラム 方針 ( つづき ) 接尾辞のつけかた 下 2 桁が 11, 12 もしくは 13 のとき,"th" 下 1 桁が 1 のとき,"st" 下 1 桁が 2 のとき,"nd" 下 1 桁が 3 のとき,"rd" それ以外は,"th" 下? 桁 整数 iの下 1 桁 iを10で割った余り i % 10 整数 iの下 2 桁 iを100で割った余り i % 100 40
処理 { と } が省略可能なとき 処理 が一つの文のときは,{ と } を省略できる. if ( 条件 ) ; ただし, 条件を満たすときにする処理, 満たさないときにする処理が紛らわしくなるので, 常に { と } をつけるようにしておくとよい if ( 条件 ) 処理 1; 処理 2; if ( 条件 ) { 処理 1; 処理 2; } if ( 条件 1) if ( 条件 2) 処理 1; else 処理 2; if ( 条件 1) { if ( 条件 2) 処理 1; } else 処理 2; 違う! 条件の真偽にかかわらず処理 2 を実行する. 違う! 条件 1 が真, 条件 2 が偽のときに限り, 処理 2 を実行する. 41
さまざまな分岐 if 文の入れ子 else if 文 AND 条件,OR 条件 42
} if } 条件 条件 条件 多分岐 (1) 構文 if ( 条件 1) { } } ( 条件 2) { 1~2をともに満たすときの処理 else { else { 1 を満たすが, 条件 2 を満たさないときの処理 1 を満たさないときの処理 if 文の中に if 文 if 文の 入れ子 43
} } } 条件 条件 条件 条件 多分岐 (2) 構文 (else if 文 ) if ( 条件 1) { } 1 を満たすときの処理 else if ( 条件 2) { 1 は満たさず, 条件 2 を満たすときの処理 else if ( 条件 3) { 1~2 は満たさず, 条件を 3 を満たすときの処理 else { 1~3 のいずれも満たさないときの処理 44
} } 条件 条件 条件 条件 AND 条件と OR 条件 AND 条件 if ( 条件 1 && 条件 2) { } OR 条件 1~2 をともに満たすときの処理 else { 1~2 の少なくとも一方を満たさないときの処理 if ( 条件 1 条件 2) { } 1~2 の少なくとも一方を満たすときの処理 else { パイプ記号 (Shift を押しながら ) を 2 個 1~2 をともに満たさないときの処理 45
演算子 式評価に関する用語 演算対象をオペランド (operand) という. y = x + 1; のとき, x と 1 は, 演算子 + のオペランド y と x + 1 は, 演算子 = のオペランド 代入できるオブジェクトを左辺値 (lvalue) という. 例 : p = (++q) + 1; としたときの p と q 演算子を適用して値を得ることを評価という. left value の略 例 : if (x = 3) {...} のとき, x = 3 により,x に 3 が代入されるとともに, この式を評価した値は 3 となる. x が 3 と等しいか を判定したければ x == 3 と書く 46
論理演算の真理値表 x y x&&y x y x!x 真 真 1 1 真 0 偽 真 0 1 偽 1 真 偽 0 1 偽 偽 0 0 偽 : 整数型なら 0, 浮動小数点型なら 0.0, ポインタ型なら NULL と等しくなる値. 真 : 偽でないスカラ型 ( 整数型, 浮動小数点型もしくはポインタ型 ) の値. 47
ビット演算の真理値表 x y x & y x y x ^ y x ~x 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 ビット単位の演算結果であることに注意. 0 ^ 1 = 1 ^ 0 = 1 ( 相補律 ) 1 ^ 1 = 0 ( ビットの反転 ), x ^ x = 0 ( ビットのクリア ) が成り立つ. 48
ビットパターン出力プログラム : 準備 対象 ( 入力 ) は,unsigned char 型の値 ビット長が分かれば, 他の整数型にも適用可能 x=40 0 0 1 0 1 0 0 0 charall.c 49
ビットパターン出力プログラム : 考え方 x: 0 0 1 0 1 0 0 0 b の初期値は,1 << 7 b の 増分 は,b >>= 1 x の値は変化しない b: x & b は 0 0 を出力 1 0 0 0 0 0 0 0 b: x & b は 0 0 を出力 0 1 0 0 0 0 0 0 b: x & b は 32 1 を出力 0 0 1 0 0 0 0 0 b: x & b は 0 0 を出力 0 0 0 0 0 0 0 1 50
演算子と, 演算子でないもの 関数呼び出し : ( ) 配列の添字 : [ ] コンマ演算子 :, for (i=0, max= 1; scanf("%d", &d[i]) == 1; i++) これらは構文の一部であり, 演算子ではない. 51
1 にならない? for 文を用いて,0, 0.1, 0.2,..., 1.0 を取り出す, 間違った方法 double i; for (i = 0; i!= 1.0; i += 0.1) 0.1 という値を, 計算機内で誤差なく表現できない. 計算誤差 により,0.1 10 が 1 でないという事態が起こる. プログラミングの心がけ ( 最善 ) ループカウンタは実数型にしない. ( 次善 )!= ではなく,> や < を用いて判定をする. from0to1bad.c 52
異なる型の値同士の計算 1/3 と 1.0/3 と 1/3.0 と 1.0/3.0 は同じ値? 算術演算において, 大きい範囲の型に揃えられる. int > short, int > char ( 汎整数拡張 ) long double > double > float > long long > long > int ( 暗黙の型変換 ) unsigned > signed プログラミングの心がけ 整数割る整数は, 整数. unsigned と signed の整数値を混在させて演算しない. 53
C らしい式の例 x の値を 1 だけ増やす x++; x = x + 1; ++x; x の値を倍にする 実数なら,x *= 2; x = x * 2; x += x; 正の整数なら,x <<= 1; x が偶数か奇数か判定する if (x & 1) if (x % 2) x が 0 か否か判定する if (x == 0) if (!x) 54
代入の順序 オペランドの評価順序は, 特に明記したものを除いて, 不定 ( 処理系依存 ) である. 式の中で同一の変数などに 2 つ以上の代入をしないよう心がける. x=2; printf("%d %d", ++x, ++x); の出力は 3 4 かもしれないし, 4 3 かもしれない. x % 2? (x = x * 3 + 1) : (x /= 2); は意図通りに動作する ( が,if 文で書くほうが自然 ). 55