Cプログラミング入門 第１回 三輪忍

この授業のねらい ソフトウェア設計技術の基礎の習得 ソフトウェア設計の目的： なぜ？ そのための方法論を学ぶ 人間が意図した作業を代わりにコンピュータに行わせること なぜ？ 人間は面倒なことはやりたくない コンピュータは疲れない そのための方法論を学ぶ C 言語を題材に

授業の進め方（普通の情報科の場合） 目的：ソフトウェア設計スキルの習得 普通は， それぞれ半期ぐらい 講義でプログラミング理論を教える 演習で実装して理解を深める それぞれ半期ぐらい

授業の進め方（うちの場合） 『情報科学』（準必修，１年後期） 空白の１年 この授業 Ruby を用いたプログラミングの講義と演習 C を用いた３回の演習だけ．．． スタート時点での理解度がばらばら

この演習の進め方 基本は演習 課題の提示後に簡単な講義（１回だけ） これから課題を提示 出席とレポートで評価 プログラミングをまったく理解していない人向け 『情報』『情報科学』を履修していない人 ほとんど忘れてしまった人 進められる人は講義中に課題をやってもよい

スケジュール 第１回（４/７） 第２回（４/１４） 第３回（４/２１） レポート提出（４/２８正午まで） 演習 or 講義（『コンピュータ概論と C 文法の基礎』） 第２回（４/１４） 演習 第３回（４/２１） レポート提出（４/２８正午まで）

レポートに関して 内容 提出方法：E-Mail 実装したプログラムをレポート形式で報告 実装が十分理解できればソース・コードを提出する必要はない 提出方法：E-Mail 宛先：miwa@hal.ipc.i.u-tokyo-ac.jp Subject： 【プログラミング入門レポート】 学籍番号：氏名 PDF で

レポート課題 巡回セールスマン問題の近似解を求めるプログラムを作 成せよ．作成したプログラムを用いて、下記の都市データ の最短経路を求めよ． 都市データのファイル http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/ja.txt 100 75 125 125 100 75 50 125 50 100

注意事項 データ・ファイルの見方 レポートに書くべきこと 解の精度とアルゴリズムの面白さで評価 1行が1都市に相当 都市1 149 データ・ファイルの見方 1行が1都市に相当 各行の3つの数字の意味（例：”1 288 149”） 都市の番号（”1”） （都市の位置を 2 次元平面上にプロットした場合の） x 座標（”288”） y 座標（“149”） レポートに書くべきこと 実装したアルゴリズムの説明 求めた解（ルート，総移動距離） 解の精度とアルゴリズムの面白さで評価 288

最近近傍法 まだ訪問していない都市の中で最も近いものを選択 スタート 100 75 125 125 100 75 50 125 50 100

コンピュータ概論

コンピュータに対する理解 生活を豊かにする便利なもの どんなシステム？？？ インターネット端末 ワード・プロセッサ 電子書籍リーダ 携帯電話 etc どんなシステム？？？

システムとしてのコンピュータ 融通のきかない人 プログラム あらかじめ決められた手続きしかできない 決まった言葉（言語・文法）しか理解できない プログラム コンピュータに行わせる一連の手続き 命令の集合として記述 Ex.) C = A + B

コンピュータの構成 CPU C C C = A + B C = A + B Memory A A B B Memory 命令やデータを格納する領域 CPU（Central Processing Unit） メモリから命令やデータを取得 演算を行う装置 詳しくは『計算システム論第２』で CPU C C C = A + B C = A + B Memory A A B B

プログラミング プログラム 人間が直接書くのはほぼ不可能 コンピュータに行わせる手続き 最終的には機械語（アセンブリ） 昔は書いてた 命令の集合 最終的には機械語（アセンブリ） 「01001110 …」 人間が直接書くのはほぼ不可能 昔は書いてた 『マイコンプログラミング演習』でもやる ちょっと複雑になると無理

高級言語とコンパイラ 高級言語 コンパイラ 高級言語 機械語 コンパイル Ex.) Fortran, C, Java, Ruby, … 翻訳を行うプログラム 高級言語で記述されたものを機械語へと変換 高級言語 機械語 コンパイル

コンパイルの手順 web を参照 http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/exp-C.html

C言語の文法の基礎

内容 プログラムの基本構造 データと演算 制御の流れ

仕事の例 問題： どうやって？ 数日仕事 1,500人目 数分仕事 進振り対象の学生の成績データ（平均点のデータ．3,000人分）が 手元にある．中央値を求めなさい． 　　　Ex.) 75点，95点，63点，70点，82点，・・・ どうやって？ 人間が集計 データを昇順に並び替え（ソート） 1,500人目を探す 　　　Ex.) 60点，60点，62点，63点，65点，・・・，77点，・・・ コンピュータに集計させる 数日仕事 1,500人目 数分仕事

ソーティング・アルゴリズム バブル・ソート １回目 ２回目 63点 75点 75点 75点 63点 63点 95点 95点 63点 63点 左端から右端に向かって以下の操作を行う 隣り合うデータの大小を比較 昇順になっていなかったら入れ替え 右端に到達したら左端に戻ってやり直し 計算量：最悪 O (n^2) １回目 ２回目 63点 75点 75点 75点 63点 63点 95点 95点 63点 63点 75点 70点 70点 75点 63点 70点 95点 63点 82点 70点 95点 70点 82点 95点 swap swap swap

C プログラムの構造 ヘッダ 文 関数 ファイル median.c の内容 #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] ); 関数 文 ファイル median.c の内容

関数 処理のまとまり サブルーチンを実現（後述） 普通は繰り返し行われる処理を関数化 複数の文からなる 同じことを何度も書くのは面倒 バグのもと

特殊な関数 main 関数 プログラムの実行開始地点を表す 普通は最初に1回呼ばれるだけ #include <stdio.h> int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] );

文 処理の最小単位 「 ; 」 の次の文字から 「 ; 」 まで １文/行がマナー（例外アリ） 「A を B に代入する」 「文字を出力する」 「 ; 」 の次の文字から 「 ; 」 まで １文/行がマナー（例外アリ） #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] );

ヘッダ ヘッダ・ファイルの展開（include） ヘッダ・ファイル 複数のファイルで使用される関数などを宣言 あらかじめ用意されていることもある #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] );

C プログラムの構造 ヘッダ 文 関数 文字列を出力する関数（printf）の宣言があるヘッダ・ファイル（stdio.h）を include プログラムの開始地点 ヘッダ #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] ); 関数 処理の方向 バブル・ソート 文 中央値を出力 プログラムの終了 ファイル median.c の内容

データと演算 プログラムの大部分はデータに対する演算 「隣り合う２つの点数を比較する」 「２つの点数を交換する」 など データ 演算

データの種類とデータ型 データ データ型 75 63 95 定数：変更不可 （e.g. “1500”, “3000”） 変数：値の入れ物．中身を変更可能 　　　　（e.g. “i”, “j”, “tmp”） データ型 データを扱う形式 コンパイラが機械語を生成する際のヒント “A + B”　　　　整数の加算 or 浮動小数点の加算？ 63 95 tmp

データ型の種類 基本型 修飾子 char：1B の数値．文字の型としても使用 int：整数（通常 4B） float：単精度浮動小数点（通常 4B） double：倍精度浮動小数点（通常 8B） 修飾子 長さ（short, long） 符号（singed, unsigned）

宣言/定義と使用 使い方（変数に限らない） 宣言/定義の位置 宣言（定義は別のファイル） 関数の冒頭で宣言/定義 使用 最初に型を宣言 どこかで定義（宣言を兼ねることも） 後は普通に使用 宣言/定義の位置 グローバル 関数の外で宣言/定義 そのファイル中のどこでも参照可能 ローカル 関数の冒頭で宣言/定義 その関数内でのみ参照可能 宣言（定義は別のファイル） 関数の冒頭で宣言/定義 #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] ); #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] ); 使用

派生型 配列 ポインタ ベクタ，行列 インデクス付けされたデータの集合 Ex.) 3,000人分の平均点データ int data0, data1, …, data2999;　　　　　　int data [3000]; “data [ i ]” で i 番目の要素にアクセス ポインタ データのアドレスを格納する変数

演算 基本的には同じ型のデータ同士 種類 算術演算（+, -, ＊, /, %） 論理演算（&, |, ^, <<, >>, ~） 関係演算（<, >, >=, <=, ==） 結果は真（１） or 偽（０） 代入演算（=） “A = B” は「A に B を代入する」

C プログラムの構造 j 番目のデータが j+1 番目のデータよりも大きいか比較 j 番目のデータを tmp に退避 データ交換 #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] ); #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] ); j 番目のデータが j+1 番目のデータよりも大きいか比較 j 番目のデータを tmp に退避 データ交換 j+1 番目のデータを j 番目の位置に代入 tmp のデータを j+1 番目の位置に代入 ファイル median.c の内容

制御の流れ 基本 流れを変えたいこともある 左から右へ 上から下へ 条件付き実行 関数呼び出し ソース・コード 基本 左から右へ 上から下へ 流れを変えたいこともある 条件付き実行 「左のデータの値が右のデータの値よりも大きい場合は交換する」 「3000回繰り返す（カウンタが3000を超えたら繰り返すのをやめる）」 関数呼び出し “ printf () ”

流れを変えるもの 分岐 if 文 switch 文 ループ for 文 while 文 サブルーチン

分岐 条件によって実行する部分を変更 if 文： switch 文： 条件の真偽により変更 条件の値により変更 switch ( x ) { 　条件の真偽により変更 switch 文： 　条件の値により変更 if ( A ) { B; } else { C; } switch ( x ) { case 0: A; break; case 1: B; } A が真の場合 x が0の場合 A が偽の場合 x が1の場合

C プログラムの構造 j 番目のデータが j+1 番目のデータよりも大きいか比較 結果が真の場合のみ交換を行う #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] ); j 番目のデータが j+1 番目のデータよりも大きいか比較 結果が真の場合のみ交換を行う ファイル median.c の内容

ループ 条件が成立している限り繰り返す 書き方は２通り 条件式 条件式 制御変数の初期化 制御変数の更新 for 文 / while 文 どちらでも同じことが実現可能 慣例として， for 文：制御変数が単調に変化する時 　　　　　　（配列アクセスなど） while 文：それ以外 条件式 while ( B ) { D; } B B D D 条件式 制御変数の初期化 制御変数の更新 A for ( A ; B ; C ) { 　　D; } B B D D C C

C プログラムの構造 i が 2999 に達するまで繰り返す i を初期化 i をインクリメント ファイル median.c の内容 #include <stdio.h> main ( ) { int i, j, tmp; int data [3000]; for ( i = 0 ; i < 3000 – 1 ; i = i + 1) { for ( j = 0 ; j < 3000 – i + 1 ; j = j + 1) { if ( data [ j ] > data [ j + 1 ] ) { tmp = data [ j ]; data [ j ] = data [ j + 1]; data [ j + 1 ] = tmp; } printf ( “median = %d\n”, data [1500] ); i が 2999 に達するまで繰り返す i を初期化 i をインクリメント ファイル median.c の内容

サブルーチンと関数 サブルーチン 関数 別の処理を呼び出す 終わったら元の位置に戻る 関数呼び出し/復帰によって実現 引数：呼び出し時に関数に渡す 　　　　　データ 返り値：復帰時に元のルーチン 　　　　　　に返すデータ void printf ( char* s, … ) { } 返り値の型 第１引数 printf ( “median = %d\n”, data [1500] );

C文法のまとめ プログラムの基本構造 データと演算 制御の流れ データには型が存在 基本は左から右へ．上から下へ 流れを変えるもの 分岐，ループ，関数呼び出し

参考書 カーニハン＆リッチー： 「プログラミング言語C 第２版」，共立出版 講義スライド http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/C1_2013.pptx

おまけ

できない人をサポートしつつ，できる人も楽しめる演習にするにはどうすればよいか？ この演習の例年の評判 正直に言って，あまりよくない 「どうしたらいいかわからない」 「教え方が不親切．できる人にはこれでいいんだろうけど．．．」 でも，こちらの立場としては， 理解度のばらつきが大きすぎて，演習や講義の最低ラインを決め るのが非常に難しい（あまりに易しくしすぎると，できる人には物足 りない演習になる） 誰が何をわかってないのかこちらはわからないので，わからないこ とがあるなら質問してほしい（演習の間は講義室にいるのだから） できない人をサポートしつつ，できる人も楽しめる演習にするにはどうすればよいか？

対応策 サンプル・プログラムを配ります サンプル・プログラムの URL データ・ファイルの読み込み，結果の出力部分など，アルゴリズム とは直接関係ない部分を実装する手間を削減 アルゴリズムの考案・実装に注力できるようになる サンプル・プログラムの URL http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/tsp.c ※ あくまでサンプルなので，ゼロから自分で書きたい人は自由に書 いてください

直前にいた都市 の座標（X, Y） 訪問中の都市 の座標（X, Y） この都市に訪問するまで のトータルの移動距離 １行が都市間の 移動１回を表す