第１回 三輪忍

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

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

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

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

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

 内容 ◦ 実装したプログラムをレポート形式で報告 ◦ 実装が十分理解できればソース・コードを提出する必要はな い  提出方法： ◦ 宛先： ◦ Subject ： 【プログラミング入門レポート】 学籍番号：氏名 ◦ PDF で

 巡回セールスマン問題の近似解を求めるプログラムを 作成せよ．作成したプログラムを用いて、下記の都市 データの最短経路を求めよ．  都市データのファイル 

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

 まだ訪問していない都市の中で最も近いものを選択 スタート

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

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

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

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

 高級言語 Ex.) Fortran, C, Java, Ruby, … ◦ これなら何とかなる（ for 人間） ◦ 理解不能（ for コンピュータ）  コンパイラ ◦ 翻訳を行うプログラム ◦ 高級言語で記述されたものを機械語へと変換 機械語 高級言語 コンパイル

 web を参照 ◦

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

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

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

#include 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 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] ); }

 処理の最小単位 ◦ 「 A を B に代入する」 ◦ 「文字を出力する」  「 ; 」 の次の文字から 「 ; 」 まで  １文 / 行がマナー（例外アリ） #include 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 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 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 の内容 文字列を出力する関数 （ printf ）の宣言があるヘッ ダ・ファイル（ stdio.h ）を include プログラムの開始地 点 処理の方向 プログラムの終 了 バブル・ソー ト 中央値を出力

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

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

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

 使い方（変数に限らない） 宣言 ◦ 最初に型を宣言 定義 ◦ どこかで定義（宣言を兼ねることも） ◦ 後は普通に使用  宣言 / 定義の位置 ◦ グローバル  関数の外で宣言 / 定義  そのファイル中のどこでも参照可能 ◦ ローカル  関数の冒頭で宣言 / 定義  その関数内でのみ参照可能 #include 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 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 を代入する」

#include 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 の内容 #include 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 番目の位置に代 入 データ交換

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

 分岐 ◦ if 文 ◦ switch 文  ループ ◦ for 文 ◦ while 文  サブルーチン

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

#include 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 の内容 j 番目のデータが j+1 番目のデータ よりも大きいか比 較 結果が真の場合 のみ交換を行う

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

#include 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 の内容 i を初期化 i が 2999 に達 するまで繰り返 す i をインクリメ ント

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

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

 カーニハン＆リッチー： 「プログラミング言語 C 第２版」，共立出版  講義スライド ◦

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

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

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