C言語入門

1
C言語入門
第7週
プログラミング言語Ⅰ(実習を含む。),
計算機言語Ⅰ・計算機言語演習Ⅰ,
情報処理言語Ⅰ(実習を含む。)
2
多次元配列
3
多次元の値も扱いたい
• 例えば行列の演算(1,2次元混合)
𝑎1,1
⋮
𝑎𝑚,1
… 𝑎1,𝑛
⋱
⋮
… 𝑎𝑚,𝑛
行列は2次元
𝐴𝑥 = 𝑏
𝑥1
𝑏1
⋮ = ⋮
𝑥𝑛
𝑏𝑚
ベクトルは1次元
4
多次元の値も扱いたい
• 例えば白黒や濃淡画像(2次元)
0
32
64
128
0
32
64
128
32
64
128
192
32
64
128
192
128
128
192
255
128
128
192
255
x,y座標の各点をマス目で表し
各マス目の明るさを
256段階(8bit)の数値で表す
輝度値や明度値と言う
それぞれのマス目の数値に応じて
光らせる明るさを調整すると
絵が描ける
5
多次元の値も扱いたい
• 例えば白黒や濃淡画像(3次元)
255
0
0
255
255
0
0
255
x,y座標の各点の
光の三原色
赤緑青の明るさ(RGB値)を
数値で表す
0
画面を虫眼鏡で見ると
こんな感じに
光っているのが見える
255
0
255
0
0
255
0
255
255
6
多次元の値も扱いたい
• 例えば白黒や濃淡画像(3次元)
255
0
0
255
255
0
0
255
遠目で見た場合や
ソフトウェア上では
色が混ざって
このように見える
0
255
0
255
0
0
255
0
255
255
7
画面表示の仕組み
• 方眼紙のような構造
• 光の三原色(RGB=赤緑青)で加法混色
• 通常、各色8bit(256段階)で電圧調整して明暗表現
• 計24bit(16,777,216色)=8bit×3(256×256×256 段階)
8
混色
• 加法混色
• 減法混色
• 画面、光
• RGBカラーモデル
• Red, Green, Blue
• 印刷、絵の具
• CMYカラーモデル
• Cyan, Magenta, Yellow
R
Y
Y
M
Bk
W
G
C
M
R
G
B
B
C
9
教科書 pp.52-56.
メモリの構成
• メモリのアドレスは1次元でした
32bitのOSは32bitのアドレス空間
最大232 Bytes=4GiB
64bitのOSは64bitのアドレス空間
最大264 Bytes=16EiB
0x00000000
0x00
0x0000000000000000
0x00
0x00000001
0x00
0x0000000000000001
0x00
0x00000002
0x00
0x0000000000000002
0x00
0x00000003
0x00
0x0000000000000003
0x00
:
:
:
:
0xffffffff
0x00
アドレス
格納値
:
:
0xffffffffffffffff
アドレス
:
:
0x00
格納値
10
教科書 pp.85-108.
二次元配列変数
• 1次元のメモリを折り畳んで2次元にして使う
char a[3][4]; // 要素数3*4のchar型変数の宣言
?
?
?
?
?
?
a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1]
1行分のデータ
?
...
a[2][3]
メモリのアドレスは1次元なので
実際には2行目以降も
直線状に並んでいる
[1] pp.135-137.
11
教科書 pp.85-108.
二次元配列変数
• 要素数4の配列を3つ並べた例
char a[3][4]; // 要素数3*4のchar型変数の宣言
?
?
?
?
a[0][0] a[0][1] a[0][2] a[0][3]
?
?
?
?
a[1][0] a[1][1] a[1][2] a[1][3]
?
?
?
論理的には
2次元的に並んでいると
考えて使えば良い。
?
a[2][0] a[2][1] a[2][2] a[2][3]
[1] pp.135-137.
12
行列の行と列
• m行n列の行列
1列
1行
:
:
m行
𝑎1,1
⋮
𝑎𝑚,1
・・・
n列
… 𝑎1,𝑛
⋱
⋮
… 𝑎𝑚,𝑛
13
Row-major と Column-major
• 本来1次元のメモリをどう区切って使うか？
• 行を連続にするか？列を連続にするか？
1列
1行
:
:
m行
𝑎1,1
⋮
𝑎𝑚,1
・・・
n列
… 𝑎1,𝑛
⋱
⋮
… 𝑎𝑚,𝑛
Row-major は行方向の要素が
メモリ上で連続に並ぶ
C言語はこのタイプ
1列
𝑎1,1
⋮
𝑎𝑚,1
・・・
n列
… 𝑎1,𝑛
⋱
⋮
… 𝑎𝑚,𝑛
Column-major は列方向の要素が
メモリ上で連続に並ぶ
Fortran等はこのタイプ
14
メモリ上の配列と二次元配列(行列)
• Row-major は同じ行が繋がっている
a[0][0]
a[0][1]
a[0][0]
a[0][1]
a[0][2]
a[0][3]
a[1][0]
a[1][1]
a[1][2]
a[1][3]
a[2][0]
a[2][1]
a[2][2]
a[2][3]
a[0][2]
a[0][3]
a[1][0]
a[1][1]
a[1][2]
:
a[2][3]
二次元配列
Row-major
int a[m][n];
a[i][j];
int a[m * n];
a[n * i + j];
C言語はこのタイプ
訂正: 2015-06-20
誤: a[m * i + j] 正: a[n * i + j]
15
メモリ上の配列と二次元配列(行列)
• Column-major は同じ列が繋がっている
a[0][0]
a[0][0]
a[0][1]
a[0][2]
a[0][3]
a[1][0]
a[1][0]
a[1][1]
a[1][2]
a[1][3]
a[2][0]
a[2][0]
a[2][1]
a[2][2]
a[2][3]
a[0][1]
a[1][1]
a[2][1]
a[0][2]
:
a[2][3]
二次元配列
Column-major
int a[m][n];
a[i][j];
int a[m * n];
a[i + j * m];
Fortran等はこのタイプ
訂正: 2015-06-20
誤: a[i + j * n] 正: a[i + j * m]
16
教科書 pp.85-108.
二次元配列のメモリ上の配置
• Row-major と Column-major
?
?
?
?
?
?
a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1]
?
?
?
?
?
a[0][0] a[1][0] a[2][0] a[0][1] a[1][1] a[2][1]
1列分のデータ
...
a[2][3]
Row-major は行方向の要素が連続に並ぶ
C言語はこのタイプ
1行分のデータ
?
?
?
...
a[2][3]
Column-major は列方向の要素が連続に並ぶ
Fortran等はこのタイプ
[1] pp.135-137.
17
教科書 pp.85-108.
三次元配列変数
• 1次元のメモリを折り畳んで3次元にして使う
char a[2][3][4]; // 要素数2*3*4のchar型変数の宣言
?
?
?
?
?
?
[0][0][0] [0][0][1] [0][0][2] [0][0][3] [0][1][0] [0][1][1]
1行分のデータ
?
...
[1][2][3]
メモリのアドレスは1次元なので
実際には2行目以降も
直線状に並んでいる
[1] pp.135-137.
18
教科書 pp.85-108.
三次元配列変数
• 要素数3*4の配列を2つ並べた例
char a[2][3][4]; // 要素数2*3*4のchar型変数の宣言
?
?
?
?
[0][0][0] [0][0][1] [0][0][2] [0][0][3]
?
?
?
?
[0][1][0] [0][1][1] [0][1][2] [0][1][3]
?
?
?
?
[0][2][0] [0][2][1] [0][2][2] [0][2][3]
?
?
?
?
[1][0][0] [1][0][1] [1][0][2] [1][0][3]
?
?
?
?
[1][1][0] [1][1][1] [1][1][2] [1][1][3]
?
?
?
?
[1][2][0] [1][2][1] [1][2][2] [1][2][3]
[1] pp.135-137.
19
教科書 pp.85-108.
配列変数の使用例
• 同じ次元・要素数でもいろんな解釈で使える
char a[2][3][4];
char a[3][4];
a[ch][t];
a[t][x];
a[y][x];
a[t][y][x];
a[z][y][x];
20
二次元配列の演習
行列の演算
21
演習: 行列とベクトルの演算
• 𝐴 を3×3の行列、 𝒃, 𝒙 を3次元のベクトルとしたとき
に以下の計算を行うプログラム作ってみましょう。
• 積(matrix_vector_mul_practice_1.c)
𝑛
𝒃 = 𝐴𝒙: 𝑏𝑖 =
𝑎𝑖,𝑗 𝑥𝑗
𝑗=1
22
演習: 行列の演算
• 𝐴, 𝐵 を3×3の行列としたときに以下の計算を行うプログ
ラム作ってみましょう。
• 加算(add)、減算(sub)、要素単位の乗算(times)、
行列乗算(mtimes)、訂正: 2015-06-20
誤: 𝐶 = 𝐴 + 𝐵 正: 𝐶 = 𝐴.∗ 𝐵
転置(transpose)
•
•
•
•
•
加算:
減算:
要素単位の乗算:
行列乗算:
転置:
𝐶
𝐶
𝐶
𝐶
𝐶
= 𝐴 + 𝐵: 𝑐𝑖,𝑗 = 𝑎𝑖,𝑗 + 𝑏𝑖,𝑗
= 𝐴 − 𝐵: 𝑐𝑖,𝑗 = 𝑎𝑖,𝑗 − 𝑏𝑖,𝑗
= 𝐴.∗ 𝐵: 𝑐𝑖,𝑗 = 𝑎𝑖,𝑗 𝑏𝑖,𝑗
= 𝐴 ∗ 𝐵: 𝑐𝑖,𝑗 = 𝑚
𝑘=1 𝑎𝑖,𝑘 𝑏𝑘,𝑗
= 𝐴𝑇 : 𝑐𝑖,𝑗 = 𝑎𝑗,𝑖
訂正: 2015-06-20
誤: 𝐶 = 𝐴 + 𝐵 正: 𝐶 = 𝐴 ∗ 𝐵
23
演習: 行列の演算
• matrix_vector_xxx_practice_1.c を元にして以下のファ
イル名で作成せよ
• 加算:
matrix_vector_add_practice_1.c
• 減算:
matrix_vector_sub_practice_1.c
• 要素単位の乗算:
matrix_vector_times_practice_1.c
• 行列乗算:
matrix_vector_mtimes_practice_1.c
• 転置:
matrix_vector_transpose_practice_1.c
24
重複した処理をループにまとめる
数式をループに変換する
ループの組み立て
追加: 2015-06-20
25
ループの組み立て
重複した処理をまとめる
sum = 1 + 1 + 1 + 1 + 1;
演算を構成する項を縦に並べる
sum =
+
+
+
+
1
1
1
1
1;
各項を単文で書き直す
sum
sum
sum
sum
sum
=
+=
+=
+=
+=
1;
1;
1;
1;
1;
積算の場合
初期値を与えて
各単文を
全く同じ処理の
繰り返しにする
sum = 0; // 初期化
for (i = 0; i < 5; i++) {
sum += 1;
}
sum
sum
sum
sum
sum
sum
=
+=
+=
+=
+=
+=
0; // 初期化
1;
1;
1;
5回繰り返している
1;
1;
追加: 2015-06-20
26
ループの組み立て
重複した処理をまとめる
sum = 1 + 2 + 3 + 4 + 5;
演算を構成する項を縦に並べる
sum =
+
+
+
+
sum
sum
sum
sum
sum
1
2
3
4
5;
各項を単文で書き直す
= 1;
+= 2;
+= 3;
+= 4;
+= 5;
sum = 0; // 初期化
for (i = 1; i <= 5; i++) {
sum += i;
}
ループカウンタを活用する
積算の場合
初期値を与えて
各単文を
全く同じ処理の
繰り返しにする
sum
sum
sum
sum
sum
sum
=
+=
+=
+=
+=
+=
0; // 初期化
1;
2;
3;
1～5まで増えている
4;
5;
追加: 2015-06-20
27
ループの組み立て
重複した処理をまとめる
sum = a[0]*b[0]+a[1]*b[1]+・・・+a[N-1]*b[N-1];
演算を構成する項を縦に並べる
sum = a[0]*b[0]
+ a[1]*b[1]
⋮
⋮
+ a[N-1]*b[N-1];
ループカウンタを活用する
各項を単文で書き直す
sum = a[0]*b[0];
sum += a[1]*b[1];
⋮
⋮
sum += a[N-1]*b[N-1];
sum = 0; // 初期化
for (i = 0; i < N; i++) {
sum += a[i]*b[i];
}
積算の場合
初期値を与えて
各単文を
全く同じ処理の
繰り返しにする
sum = 0; // 初期化
sum += a[0]*b[0];
sum += a[1]*b[1];
⋮
⋮
sum += a[N-1]*b[N-1];
0～N-1
まで
増えて
いる
28
追加: 2015-06-20
加筆: 2015-06-26
ループの組み立て
数式とC言語の対応を考える
• 数式
定石の書き方から変形
𝑛
𝑛
𝑠=
𝑠=
1
𝑖=1
𝑖=1
• C言語
𝑖
積算項: 1 ↔ 𝑖
1の積算
𝑖の積算
s = 0;
for (i = 1; i <= n; i++) {
s += 1;
}
s = 0;
for (i = 1; i <= n; i++) {
s += i;
}
29
追加: 2015-06-20
加筆: 2015-06-26
ループの組み立て
数式とC言語の対応を考える
• 数式
定石の書き方から変形
𝑛
𝑛
𝑠=
𝑏𝑖 =
𝑖
𝑗=1
𝑖=1
• C言語
𝑎𝑖,𝑗 𝑥𝑗
結果:
𝑠 → 𝑏𝑖
カウンタ: 𝑖 → 𝑗
積算項: 𝑖 → 𝑎𝑖,𝑗 𝑥𝑗
𝑖の積算
𝑎𝑖,𝑗 𝑥𝑗 の積算
s = 0;
for (i = 1; i <= n; i++) {
s += i;
}
b[i] = 0;
for (j = 1; j <= n; j++) {
b[j] += a[i][j] * x[j];
}
30
追加: 2015-06-20
加筆: 2015-06-26
ループの組み立て
数式とC言語の対応を考える
要素数𝑛個の数列や配列は
数学では 𝑎1 ⋯ 𝑎𝑛 と書く場合が多いが
C言語では a[0]⋯a[n-1] になる
• 数式
𝑛
𝑏𝑖 =
𝑎𝑖,𝑗 𝑥𝑗
𝑗=1
• C言語
𝑛−1
C言語に合わせて
添え字を1つずらす
𝑏𝑖 =
𝑎𝑖,𝑗 𝑥𝑗
𝑗=0
単純に置きかえ
範囲: 1: 𝑛 → 0: 𝑛 − 1 → 0: 𝑛
𝑎𝑖,𝑗 𝑥𝑗 の積算
𝑎𝑖,𝑗 𝑥𝑗 の積算
b[i] = 0;
for (j = 1; j <= n; j++) {
b[j] += a[i][j] * x[j];
}
b[i] = 0;
for (j = 0; j < n; j++) {
b[j] += a[i][j] * x[j];
}
31
追加: 2015-06-20
加筆: 2015-06-26
ループの組み立て
数式とC言語の対応を考える
• 数式
𝑛−1
𝑏𝑖 =
𝑎𝑖,𝑗 𝑥𝑗
𝑗=0
• C言語
全ての𝑏𝑖 についてループして計算
𝑎𝑖,𝑗 𝑥𝑗 の積算
𝑎𝑖,𝑗 𝑥𝑗 の積算
for (i =
b[i] =
for (j
b[j]
}
}
b[i] = 0;
for (j = 0; j < n; j++) {
b[j] += a[i][j] * x[j];
}
0; i < m; i++) {
0;
= 0; j < n; j++) {
+= a[i][j] * x[j];
32
参考文献
• [1] B.W.カーニハン/D.M.リッチー著石田晴久
訳、プログラミング言語C 第2版 ANSI 規格準
拠、共立出版(1989)

Download Report