Cプログラミング入門 - Nakamura Laboratory

第1回
三輪忍

ソフトウェア設計技術の基礎の習得

ソフトウェア設計の目的:
◦ 人間が意図した作業を代わりにコンピュータに行わせること

なぜ?
◦ 人間は面倒なことはやりたくない
◦ コンピュータは疲れない

そのための方法論を学ぶ
◦ C 言語を題材に

目的:ソフトウェア設計スキルの習得

普通は,
◦ 講義でプログラミング理論を教える
◦ 演習で実装して理解を深める

それぞれ半期ぐらい

『情報科学』(準必修,1年後期)
◦ Ruby を用いたプログラミングの講義と演習

空白の1年

この授業
◦ C を用いた3回の演習だけ...
◦ スタート時点での理解度がばらばら

基本は演習
◦ これから課題を提示
◦ 出席とレポートで評価

課題の提示後に簡単な講義(1回だけ)
◦ プログラミングをまったく理解していない人向け
 『情報』『情報科学』を履修していない人
 ほとんど忘れてしまった人
◦ 進められる人は講義中に課題をやってもよい

第1回(4/9)
◦ 演習 or 講義(『コンピュータ概論と C 文法の基礎』)

第2回(4/16)
◦ 演習

第3回(4/23)
◦ 演習

レポート提出(5/1正午まで)

内容
◦ 実装したプログラムをレポート形式で報告
◦ 実装が十分理解できればソース・コードを提出する必要はない

提出方法:E-Mail
◦ 宛先:[email protected]
◦ Subject: 【プログラミング入門レポート】 学籍番号:氏名
◦ PDF で

巡回セールスマン問題の近似解を求めるプログラムを作
成せよ.作成したプログラムを用いて、下記の都市データ
の最短経路を求めよ.
100
75
100
125
125
75
125
50
50
100

都市データのファイル

http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/ja.txt
都市1

データ・ファイルの見方
149
◦ 1行が1都市に相当
◦ 各行の3つの数字の意味(例:”1 288 149”)
288
 都市の番号(”1”)
 (都市の位置を 2 次元平面上にプロットした場合の) x 座標(”288”)
 y 座標(“149”)

レポートに書くべきこと
◦ 実装したアルゴリズムの説明
◦ 求めた解(ルート,総移動距離)

解の精度とアルゴリズムの面白さで評価

まだ訪問していない都市の中で最も近いものを選択
スタート
100
75
100
125
125
75
125
50
100
50

生活を豊かにする便利なもの
◦
◦
◦
◦
◦

インターネット端末
ワード・プロセッサ
電子書籍リーダ
携帯電話
etc
どんなシステム???

融通のきかない人
◦ あらかじめ決められた手続きしかできない
◦ 決まった言葉(言語・文法)しか理解できない

プログラム
◦ コンピュータに行わせる一連の手続き
◦ 命令の集合として記述
Ex.) C = A + B

Memory
◦ 命令やデータを格納する領域

CPU(Central Processing Unit)
◦ メモリから命令やデータを取得
◦ 演算を行う装置
詳しくは『計算システム論第2』で
CPU
C
C=A+B A B
Memory

プログラム
◦ コンピュータに行わせる手続き
 命令の集合
◦ 最終的には機械語(アセンブリ)
 「01001110 …」

人間が直接書くのはほぼ不可能
◦ 昔は書いてた
 『マイコンプログラミング演習』でもやる
◦ ちょっと複雑になると無理

高級言語
Ex.) Fortran, C, Java, Ruby, …
◦ これなら何とかなる(for 人間)
◦ 理解不能(for コンピュータ)

コンパイラ
◦ 翻訳を行うプログラム
◦ 高級言語で記述されたものを機械語へと変換
機械語
高級言語
コンパイル

web を参照
◦ http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/exp-C.html



プログラムの基本構造
データと演算
制御の流れ

問題:
◦ 進振り対象の学生の成績データ(平均点のデータ.3,000人分)が
手元にある.中央値を求めなさい.
Ex.) 75点,95点,63点,70点,82点,・・・

どうやって?
◦ 人間が集計
数日仕事
 データを昇順に並び替え(ソート)
1,500人目
 1,500人目を探す
Ex.) 60点,60点,62点,63点,65点,・・・,77点,・・・
◦ コンピュータに集計させる
数分仕事

バブル・ソート
◦ 左端から右端に向かって以下の操作を行う
 隣り合うデータの大小を比較
 昇順になっていなかったら入れ替え
◦ 右端に到達したら左端に戻ってやり直し
◦ 計算量:最悪 O (n^2)
1回目
2回目
63点
75点
75点
70点
63点
95点
swap
70点
75点
63点
95点
swap
70点
95点
82点
swap
82点
95点
ヘッダ
#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>
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 に代入する」
◦ 「文字を出力する」


「 ; 」 の次の文字から 「 ; 」 まで
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] );

ヘッダ・ファイルの展開(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] );
文字列を出力する関数
(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 の内容

プログラムの大部分はデータに対する演算
◦ 「隣り合う2つの点数を比較する」
◦ 「2つの点数を交換する」 など
データ 演算

75
データ
◦ 定数:変更不可
(e.g. “1500”, “3000”)
◦ 変数:値の入れ物.中身を変更可能
(e.g. “i”, “j”, “tmp”)

63
tmp
データ型
◦ データを扱う形式
◦ コンパイラが機械語を生成する際のヒント
 “A + B”
95
整数の加算 or 浮動小数点の加算?

基本型
◦
◦
◦
◦

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] );

配列
◦ ベクタ,行列
◦ インデクス付けされたデータの集合
Ex.) 3,000人分の平均点データ
 int data0, data1, …, data2999;
 “data [ i ]” で i 番目の要素にアクセス

ポインタ
◦ データのアドレスを格納する変数
int data [3000];

基本的には同じ型のデータ同士

種類
◦ 算術演算(+, -, *, /, %)
◦ 論理演算(&, |, ^, <<, >>, ~)
◦ 関係演算(<, >, >=, <=, ==)
 結果は真(1) or 偽(0)
◦ 代入演算(=)
 “A = B” は「A に B を代入する」
#include <stdio.h>
main ( ) {
int i, j, tmp;
int data [3000];
j 番目のデータが
j+1 番目のデータ
よりも大きいか比較
j 番目のデータ
for ( i = 0 ; i < 3000 – 1 ; i = i + 1) {
を tmp に退避
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;
}
tmp のデータを
j+1
}
番目の位置に代入
}
j+1 番目のデータを
j 番目の位置に代入
printf ( “median = %d\n”, data [1500] );
ファイル median.c の内容
ソース・コード

基本
◦ 左から右へ
◦ 上から下へ

流れを変えたいこともある
◦ 条件付き実行
 「左のデータの値が右のデータの値よりも大きい場合は交換する」
 「3000回繰り返す(カウンタが3000を超えたら繰り返すのをやめる)」
◦ 関数呼び出し
 “ printf () ”

分岐
◦ if 文
◦ switch 文

ループ
◦ for 文
◦ while 文

サブルーチン

条件によって実行する部分を変更
◦ if 文:
条件の真偽により変更
if ( A ) {
A が真の場合
B;
} else {
A が偽の場合
C;
}
◦ switch 文:
条件の値により変更
switch ( x ) {
case 0:
A;
x が0の場合
break;
case 1:
x が1の場合
B;
break;
}
#include <stdio.h>
main ( ) {
int i, j, tmp;
int data [3000];
j 番目のデータが
j+1 番目のデータ
よりも大きいか比較
結果が真の場合
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 の内容

条件が成立している限り繰り返す

書き方は2通り
条件式
while ( B ) {
B B
◦ for 文 / while 文
D;
}
◦ どちらでも同じことが実現可能
D D
条件式
◦ 慣例として,
制御変数
制御変数
 for 文:制御変数が単調に変化する時
の初期化
の更新
(配列アクセスなど)
 while 文:それ以外
A
for ( A ; B ; C ) {
D;
}
B B
D D
C C
#include <stdio.h>
i
i が 2999 に達
main ( ) {
int i, j, tmp;するまで繰り返す
を初期化
int data [3000];
i をインクリメント
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 の内容

サブルーチン
◦ 別の処理を呼び出す
◦ 終わったら元の位置に戻る
◦ 関数呼び出し/復帰によって実現

関数
◦ 引数:呼び出し時に関数に渡す
データ
◦ 返り値:復帰時に元のルーチン
に返すデータ
返り値の型
第1引数
void printf ( char* s, … ) {
}
printf ( “median = %d\n”, data [1500] );

プログラムの基本構造

データと演算
◦ データには型が存在

制御の流れ
◦ 基本は左から右へ.上から下へ
◦ 流れを変えるもの
 分岐,ループ,関数呼び出し

カーニハン&リッチー:
「プログラミング言語C 第2版」,共立出版

講義スライド
◦ http://www.hal.ipc.i.u-tokyo.ac.jp/~miwa/C1_2012.pptx