Cプログラミング入門

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

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

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

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

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

コンパイルの手順 Visual C++ の場合 Windows を起動 ログインして Visual Studio を起動 メニューから「ファイル」→「新規作成」→「プロジェクト」を選択 「Win32」→「Win32コンソールアプリケーション」を選択し，「プロジェクト名」と 「場所」を入力．「ソリューションのディレクトリを作成」のチェックはOFFにして 「OK」をクリック Win32アプリケーションウィザードにて「次へ」をクリック．「コンソールアプリ ケーション」を選択．「空のプロジェクト」にチェックを入れ，「完了」をクリック メニューから「プロジェクト」→「新しい項目の追加」を選択 「C++ファイル(.cpp)」を選択し，「ファイル名」と「場所」を入力して「追加」をク リック プログラムを記述 メニューから「ビルド」→「ソリューションのビルド」（コンパイル） メニューから「デバッグ」→「デバッグなしで開始」

コンパイルの手順 gcc の場合 Ubuntu を起動 （emacsなどの）テキストエディタを起動し，プログラムを記述 コマンドライン端末を起動し，コマンド「gcc filename」 （filename はプログラムのファイル名）を実行．（正しくコンパイル ができていれば）「a.out」という名前の実行ファイルができる 上記のファイルを実行（コマンド「./a.out」を実行）

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点 63点 75点 63点 95点 95点 70点 75点 左端から右端に向かって以下の操作を行う 隣り合うデータの大小を比較 昇順になっていなかったら入れ替え 右端に到達したら左端に戻ってやり直し 計算量：最悪 O (n^2) ２回目 １回目 63点 75点 75点 63点 75点 63点 95点 95点 70点 75点 63点 63点 70点 63点 75点 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 第２版」，共立出版

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

対応策 サンプル・プログラムを配ります サンプル・プログラム データ・ファイルの読み込み，結果の出力部分など，アルゴリズム とは直接関係ない部分を実装する手間を削減 アルゴリズムの考案・実装に注力できるようになる サンプル・プログラム tsp.c　（資料４） ※ あくまでサンプルなので，ゼロから自分で書きたい人は自由に書 いてください

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