Download presentation
Presentation is loading. Please wait.
1
第１回 三輪忍
2
ソフトウェア設計技術の基礎の習得 ソフトウェア設計の目的： ◦ 人間が意図した作業を代わりにコンピュータに行わせること なぜ？ ◦ 人間は面倒なことはやりたくない ◦ コンピュータは疲れない そのための方法論を学ぶ ◦ C 言語を題材に
3
目的：ソフトウェア設計スキルの習得 普通は， ◦ 講義でプログラミング理論を教える ◦ 演習で実装して理解を深める それぞれ半期ぐらい
4
『情報科学』（準必修，１年後期） ◦ Ruby を用いたプログラミングの講義と演習 空白の１年 この授業 ◦ C を用いた３回の演習だけ．．． ◦ スタート時点での理解度がばらばら
5
基本は演習 ◦ これから課題を提示 ◦ 出席とレポートで評価 課題の提示後に簡単な講義（１回だけ） ◦ プログラミングをまったく理解していない人向け 『情報』『情報科学』を履修していない人 ほとんど忘れてしまった人 ◦ 進められる人は講義中に課題をやってもよい
6
第１回（４ / ８） ◦ 演習 or 講義（『コンピュータ概論と C 文法の基礎』） 第２回（４ / １５） ◦ 演習 第３回（４ / ２２） ◦ 演習 レポート提出（５ / ７正午まで）
7
内容 ◦ 実装したプログラムをレポート形式で報告 ◦ 実装が十分理解できればソース・コードを提出する必要はな い 提出方法： E-Mail ◦ 宛先： miwa@hal.ipc.i.u-tokyo-ac.jp miwa@hal.ipc.i.u-tokyo-ac.jp ◦ Subject ： 【プログラミング入門レポート】 学籍番号：氏名 ◦ PDF で
8
巡回セールスマン問題の近似解を求めるプログラムを 作成せよ．作成したプログラムを用いて、下記の都市 データの最短経路を求めよ． 都市データのファイル http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/ja.txt http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/ja.txt 100 125 50 75
9
データ・ファイルの見方 ◦ 1 行が 1 都市に相当 ◦ 各行の 3 つの数字の意味（例： ”1 288 149” ） 都市の番号（ ”1” ） （都市の位置を 2 次元平面上にプロットした場合の） x 座標 （ ”288” ） y 座標（ “149” ） レポートに書くべきこと ◦ 実装したアルゴリズムの説明 ◦ 求めた解（ルート，総移動距離） 解の精度とアルゴリズムの面白さで評価 288 149 都市 1
10
まだ訪問していない都市の中で最も近いものを選択 100 125 50 75 スタート
12
生活を豊かにする便利なもの ◦ インターネット端末 ◦ ワード・プロセッサ ◦ 電子書籍リーダ ◦ 携帯電話 ◦ etc どんなシステム？？？
13
融通のきかない人 ◦ あらかじめ決められた手続きしかできない ◦ 決まった言葉（言語・文法）しか理解できない プログラム ◦ コンピュータに行わせる一連の手続き ◦ 命令の集合として記述 Ex.) C = A + B
14
Memory ◦ 命令データ ◦ 命令やデータを格納する領域 CPU CPU （ Central Processing Unit ） ◦ メモリから命令やデータを取得 ◦ 演算を行う装置 詳しくは『計算システム論第２』 で CPU Memory C = A + B AB AB CC
15
プログラム ◦ コンピュータに行わせる手続き 命令の集合 ◦ 最終的には機械語（アセンブリ） 「 01001110 … 」 人間が直接書くのはほぼ不可能 ◦ 昔は書いてた 『マイコンプログラミング演習』でもやる ◦ ちょっと複雑になると無理
16
高級言語 Ex.) Fortran, C, Java, Ruby, … ◦ これなら何とかなる（ for 人間） ◦ 理解不能（ for コンピュータ） コンパイラ ◦ 翻訳を行うプログラム ◦ 高級言語で記述されたものを機械語へと変換 機械語 高級言語 コンパイル
17
web を参照 ◦ http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/exp-C.html
19
プログラムの基本構造 データと演算 制御の流れ
20
問題： ◦ 進振り対象の学生の成績データ（平均点のデータ． 3,000 人 分）が手元にある．中央値を求めなさい． Ex.) 75 点， 95 点， 63 点， 70 点， 82 点，・・・ どうやって？ ◦ 人間が集計 データを昇順に並び替え（ソート） 1,500 人目を探す Ex.) 60 点， 60 点， 62 点， 63 点， 65 点，・・・， 77 点，・・・ ◦ コンピュータに集計させる 数日仕事 数分仕事 1,500 人目
21
バブル・ソート ◦ 左端から右端に向かって以下の操作を行う 隣り合うデータの大小を比較 昇順になっていなかったら入れ替え ◦ 右端に到達したら左端に戻ってやり直し ◦ 計算量：最悪 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
22
#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] ); } 関数 文 ヘッダ ファイル median.c の内容](http://images.slidesplayer.net/40/11103604/slides/slide_22.jpg "#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 の内容")
23
処理のまとまり ◦ 複数の文からなる サブルーチンを実現（後述） 普通は繰り返し行われる処理を関数化 ◦ 同じことを何度も書くのは面倒 ◦ バグのもと
24
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] ); }
![ 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] ); }](http://images.slidesplayer.net/40/11103604/slides/slide_24.jpg " 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] ); }")
25
処理の最小単位 ◦ 「 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] ); }
![ 処理の最小単位 ◦ 「 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] ); }](http://images.slidesplayer.net/40/11103604/slides/slide_25.jpg " 処理の最小単位 ◦ 「 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] ); }")
26
ヘッダ・ファイルの展開（ 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 ） ヘッダ・ファイル ◦ 複数のファイルで使用される関数などを宣言 ◦ あらかじめ用意されていることもある #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] ); }](http://images.slidesplayer.net/40/11103604/slides/slide_26.jpg " ヘッダ・ファイルの展開（ 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] ); }")
27
#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 プログラムの開始地 点 処理の方向 プログラムの終 了 バブル・ソー ト 中央値を出力
![#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 プログラムの開始地 点 処理の方向 プログラムの終 了 バブル・ソー ト 中央値を出力](http://images.slidesplayer.net/40/11103604/slides/slide_27.jpg "#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 プログラムの開始地 点 処理の方向 プログラムの終 了 バブル・ソー ト 中央値を出力")
28
プログラムの大部分はデータに対する演算 ◦ 「隣り合う２つの点数を比較する」 ◦ 「２つの点数を交換する」 など データ 演算
29
データ ◦ 定数 ◦ 定数：変更不可 （ e.g. “1500”, “3000” ） ◦ 変数 ◦ 変数：値の入れ物．中身を変更可能 （ e.g. “i”, “j”, “tmp” ） データ型 ◦ データを扱う形式 ◦ コンパイラが機械語を生成する際のヒント “A + B” 整数の加算 or 浮動小数点の加算？ tmp 63 75 95
30
基本型 ◦ char ： 1B の数値．文字の型としても使用 ◦ int ：整数（通常 4B ） ◦ float ：単精度浮動小数点（通常 4B ） ◦ double ：倍精度浮動小数点（通常 8B ） 修飾子 ◦ 長さ（ short, long ） ◦ 符号（ singed, unsigned ）
31
使い方（変数に限らない） 宣言 ◦ 最初に型を宣言 定義 ◦ どこかで定義（宣言を兼ねることも） ◦ 後は普通に使用 宣言 / 定義の位置 ◦ グローバル 関数の外で宣言 / 定義 そのファイル中のどこでも参照可能 ◦ ローカル 関数の冒頭で宣言 / 定義 その関数内でのみ参照可能 #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] ); } 関数の冒頭で 宣言 / 定義 宣言（定義は 別のファイ ル） 使用
![ 使い方（変数に限らない） 宣言 ◦ 最初に型を宣言 定義 ◦ どこかで定義（宣言を兼ねることも） ◦ 後は普通に使用 宣言 / 定義の位置 ◦ グローバル 関数の外で宣言 / 定義 そのファイル中のどこでも参照可能 ◦ ローカル 関数の冒頭で宣言 / 定義 その関数内でのみ参照可能 #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] ); } 関数の冒頭で 宣言 / 定義 宣言（定義は 別のファイ ル） 使用](http://images.slidesplayer.net/40/11103604/slides/slide_31.jpg " 使い方（変数に限らない） 宣言 ◦ 最初に型を宣言 定義 ◦ どこかで定義（宣言を兼ねることも） ◦ 後は普通に使用 宣言 / 定義の位置 ◦ グローバル 関数の外で宣言 / 定義 そのファイル中のどこでも参照可能 ◦ ローカル 関数の冒頭で宣言 / 定義 その関数内でのみ参照可能 #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] ); } 関数の冒頭で 宣言 / 定義 宣言（定義は 別のファイ ル） 使用")
32
配列 ◦ ベクタ，行列 ◦ インデクス付けされたデータの集合 Ex.) 3,000 人分の平均点データ int data0, data1, …, data2999; int data [3000]; “data [ i ]” で i 番目の要素にアクセス ポインタ ◦ データのアドレスを格納する変数
![ 配列 ◦ ベクタ，行列 ◦ インデクス付けされたデータの集合 Ex.) 3,000 人分の平均点データ int data0, data1, …, data2999; int data [3000]; data [ i ] で i 番目の要素にアクセス ポインタ ◦ データのアドレスを格納する変数](http://images.slidesplayer.net/40/11103604/slides/slide_32.jpg " 配列 ◦ ベクタ，行列 ◦ インデクス付けされたデータの集合 Ex.) 3,000 人分の平均点データ int data0, data1, …, data2999; int data [3000]; data [ i ] で i 番目の要素にアクセス ポインタ ◦ データのアドレスを格納する変数")
33
基本的には同じ型のデータ同士 種類 ◦ 算術演算（ +, -, ＊, /, % ） ◦ 論理演算（ &, |, ^, >, ~ ） ◦ 関係演算（, >=, <=, == ） 結果は真（１） or 偽（０） ◦ 代入演算（ = ） “A = B” は「 A に B を代入する」
34
#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 番目の位置に代 入 データ交換
![#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 番目の位置に代 入 データ交換](http://images.slidesplayer.net/40/11103604/slides/slide_34.jpg "#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 番目の位置に代 入 データ交換")
35
基本 ◦ 左から右へ ◦ 上から下へ 流れを変えたいこともある ◦ 条件付き実行 「左のデータの値が右のデータの値よりも大きい場合は交換す る」 「 3000 回繰り返す（カウンタが 3000 を超えたら繰り返すのをや める）」 ◦ 関数呼び出し “ printf () ” ソース・コード
36
分岐 ◦ if 文 ◦ switch 文 ループ ◦ for 文 ◦ while 文 サブルーチン
37
条件によって実行する部分を変更 ◦ if 文： 条件の真偽により変更 ◦ switch 文： 条件の値により変更 if ( A ) { B ; } else { C ; } switch ( x ) { case 0: A ; break; case 1: B ; break; } x が 0 の場合 x が 1 の場合 A が真の場合 A が偽の場合
38
#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 番目のデータ よりも大きいか比 較 結果が真の場合 のみ交換を行う
![#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 番目のデータ よりも大きいか比 較 結果が真の場合 のみ交換を行う](http://images.slidesplayer.net/40/11103604/slides/slide_38.jpg "#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 番目のデータ よりも大きいか比 較 結果が真の場合 のみ交換を行う")
39
条件が成立している限り繰り返 す 書き方は２通り ◦ for 文 / while 文 ◦ どちらでも同じことが実現可能 ◦ 慣例として， for 文：制御変数が単調に変化する 時 （配列アクセスなど） while 文：それ以外 for ( A ; B ; C ) { D ; } while ( B ) { D ; } 制御変数 の初期化 条件式 制御変数 の更新 条件式 B D B D A B D C B D C
40
#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 をインクリメ ント
![#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 をインクリメ ント](http://images.slidesplayer.net/40/11103604/slides/slide_40.jpg "#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 をインクリメ ント")
41
サブルーチン ◦ 別の処理を呼び出す ◦ 終わったら元の位置に戻る ◦ 関数呼び出し / 復帰によって実現 関数 ◦ 引数 ◦ 引数：呼び出し時に関数に渡す データ ◦ 返り値 ◦ 返り値：復帰時に元のルーチン に返すデータ printf ( “median = %d\n”, data [1500] ); void printf ( char* s, … ) { } 第１引数 返り値の型
![ サブルーチン ◦ 別の処理を呼び出す ◦ 終わったら元の位置に戻る ◦ 関数呼び出し / 復帰によって実現 関数 ◦ 引数 ◦ 引数：呼び出し時に関数に渡す データ ◦ 返り値 ◦ 返り値：復帰時に元のルーチン に返すデータ printf ( median = %d\n , data [1500] ); void printf ( char* s, … ) { } 第１引数 返り値の型](http://images.slidesplayer.net/40/11103604/slides/slide_41.jpg " サブルーチン ◦ 別の処理を呼び出す ◦ 終わったら元の位置に戻る ◦ 関数呼び出し / 復帰によって実現 関数 ◦ 引数 ◦ 引数：呼び出し時に関数に渡す データ ◦ 返り値 ◦ 返り値：復帰時に元のルーチン に返すデータ printf ( median = %d\n , data [1500] ); void printf ( char* s, … ) { } 第１引数 返り値の型")
42
プログラムの基本構造 データと演算 ◦ データには型が存在 制御の流れ ◦ 基本は左から右へ．上から下へ ◦ 流れを変えるもの 分岐，ループ，関数呼び出し
43
カーニハン＆リッチー： 「プログラミング言語 C 第２版」，共立出版 講義スライド ◦ http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/C1_2013.pptx
45
正直に言って，あまりよくない ◦ 「どうしたらいいかわからない」 ◦ 「教え方が不親切．できる人にはこれでいいんだろうけ ど．．．」 でも，こちらの立場としては， ◦ 理解度のばらつきが大きすぎて，演習や講義の最低ラインを 決めるのが非常に難しい（あまりに易しくしすぎると，でき る人には物足りない演習になる） ◦ 誰が何をわかってないのかこちらはわからないので，わから ないことがあるなら質問してほしい（演習の間は講義室にい るのだから） できない人をサポートしつつ， できる人も楽しめる演習にする にはどうすればよいか？
46
サンプル・プログラムを配ります ◦ データ・ファイルの読み込み，結果の出力部分など，アルゴ リズムとは直接関係ない部分を実装する手間を削減 ◦ アルゴリズムの考案・実装に注力できるようになる サンプル・プログラムの URL ◦ http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/tsp.c http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/tsp.c ※ あくまでサンプルなので，ゼロから自分で書きたい人は自由 に書いてください
47
１行が都市間の 移動１回を表す 直前にいた都市 の座標（ X, Y ） 訪問中の都市 の座標（ X, Y ） この都市に訪問するまで のトータルの移動距離
Similar presentations
