Week 2 配列
ようこそ！
前回のセッションでは、テキストベースのプログラミング言語であるC言語について学びました。
今週は、ボトムアップでプログラミングをより深く学ぶという目標を支える、さらなる構成要素を詳しく見ていきます。
根本的に、このコースはプログラミングの要点だけでなく、問題解決についても扱います。そのため、コンピュータサイエンスの問題へのアプローチ方法にもさらに焦点を当てていきます。
コースの終わりまでに、前述の構成要素を使用して、コンピュータサイエンスの多種多様な問題を解決する方法を学びます。
読解レベル
このコースで解決する現実世界の問題の1つは、読解レベルを理解することです。
皆さんの仲間の助けを借りて、さまざまな読解レベルの文章を提示しました。
今週は、多くのプログラミング課題の1つとして、読解レベルを定量化します。
コンパイル
暗号化 (Encryption) とは、平文 (plain text) を覗き見から隠す行為です。復号 (Decrypting) とは、暗号化されたテキストを取り出し、人間が読める形式に戻す行為です。
暗号化されたテキストは、例えば以下のようになります。
U I J T J T D T 5 0
- 先週、コンパイラ、つまりソースコードをコンピュータが理解できる*マシン語 (機械語)*に変換する特別なコンピュータプログラムについて学んだことを思い出してください。
例えば、以下のようなコンピュータプログラムがあるとします。
#include
int main(void)
{
printf("hello, world\n");
}
コンパイラは上記のコードを取り込み、以下のようなマシン語に変換します。
VS Code（CS50の学生に提供されているプログラミング環境）は、clang（c language）と呼ばれるコンパイラを使用しています。
- ターミナルウィンドウに次のように入力して、コードをコンパイルできます：
clang -o hello hello.c。
コマンドライン引数は、clang -o hello hello.cのようにコマンドラインでclangに提供されます。
- ターミナルウィンドウで
./helloを実行すると、プログラムが意図通りに実行されます。
先週の以下のコードを考えてみましょう。
#include
#include
int main(void)
{
string name = get_string("What's your name? ");
printf("hello, %s\n", name);
}
このコードをコンパイルするには、
clang -o hello hello.c -lcs50と入力します。もし
make helloと入力すれば、clangを実行して、ユーザーとして実行可能な出力ファイルを作成するコマンドが実行されます。VS Codeは、ユーザーとしての利便性のために、
makeがclangとともに多数のコマンドライン引数を実行するようにあらかじめプログラムされています。上記は説明として提供されていますが、コードをコンパイルするプロセスと概念をより深く理解するためであれば、CS50で
makeを使用することは全く問題ありませんし、むしろ推奨されています！コンパイルには、以下の4つの主要なステップが含まれます。
第一に、プリプロセッシング (前処理) は、コード内の#で指定されたヘッダーファイル（#include <cs50.h>など）が、実質的にファイルにコピー・アンド・ペーストされる工程です。このステップでは、cs50.hのコードがプログラムにコピーされます。同様に、コードに#include <stdio.h>が含まれているのと同様に、コンピュータのどこかにあるstdio.hに含まれるコードがプログラムにコピーされます。このステップは以下のように視覚化できます。
string get_string(string prompt);
int printf(string format, ...);
int main(void)
{
string name = get_string("What's your name? ");
printf("hello, %s\n", name);
}
第二に、コンパイル は、プログラムがアセンブリコードに変換される工程です。このステップは以下のように視覚化できます。
...
main:
.cfi_startproc
# BB#0:
pushq %rbp
.Ltmp0:
.cfi_def_cfa_offset 16
.Ltmp1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
.Ltmp2:
.cfi_def_cfa_register %rbp
subq $16, %rsp
xorl %eax, %eax
movl %eax, %edi
movabsq $.L.str, %rsi
movb $0, %al
callq get_string
movabsq $.L.str.1, %rdi
movq %rax, -8(%rbp)
movq -8(%rbp), %rsi
movb $0, %al
callq printf
...
第三に、アセンブル では、コンパイラがアセンブリコードをマシン語に変換します。このステップは以下のように視覚化できます。
01111111010001010100110001000110
00000010000000010000000100000000
00000000000000000000000000000000
00000000000000000000000000000000
00000001000000000011111000000000
00000001000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
10100000000000100000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
01000000000000000000000000000000
00000000000000000100000000000000
00001010000000000000000100000000
01010101010010001000100111100101
01001000100000111110110000010000
00110001110000001000100111000111
01001000101111100000000000000000
00000000000000000000000000000000
00000000000000001011000000000000
11101000000000000000000000000000
00000000010010001011111100000000
00000000000000000000000000000000
00000000000000000000000001001000
...
最後に、リンク のステップでは、インクルードされたライブラリのコードもマシン語に変換され、自分のコードと結合されます。その後、最終的な実行ファイルが出力されます。
デバッグ
- 誰でもコーディング中に間違いを犯します。
デバッグ (Debugging) とは、コードからバグを見つけて取り除くプロセスです。
このコースでコードをデバッグするために使用するテクニックの1つに、ラバーダック・デバッグがあります。これは、無生物（あるいは自分自身）に向かって話し、コードがなぜ意図通りに動かないのかを考えるのに役立てる手法です。コードで行き詰まったときは、文字通りラバーダック（アヒルちゃん）にコードの問題について声に出して話しかけてみることを検討してください。小さなプラスチックのアヒルと話したくない場合は、近くにいる人間に話しかけても構いません！
私たちは、コードのデバッグを支援するツールとして CS50 Duck と CS50.ai を作成しました。
先週の以下の画像を考えてみましょう。
バグを意図的に挿入した以下のコードを考えてみましょう。
// Buggy example for printf
#include
int main(void)
{
for (int i = 0; i 3; i++)
{
printf("#\n");
}
}
このコードが3つではなく4つのブロックを出力することに注目してください。
ターミナルウィンドウに
code buggy0.cと入力し、上記のコードを書き込みます。このコードを実行すると、意図した3つではなく4つのレンガが表示されます。
printf はコードをデバッグするのに非常に便利な方法です。以下のようにコードを修正できます。
// Buggy example for printf
#include
int main(void)
{
for (int i = 0; i 3; i++)
{
printf("i is %i\n", i);
printf("#\n");
}
}
このコードがループの各反復中に i の値を出力し、デバッグに役立つことに注目してください。
このコードを実行すると、i is 0、i is 1、i is 2、i is 3 を含む多数のステートメントが表示されます。これを見て、コードをさらに以下のように修正する必要があることに気づくでしょう。
#include
int main(void)
{
for (int i = 0; i 3; i++)
{
printf("#\n");
}
}
<= が < に置き換えられたことに注目してください。
このコードは、さらに以下のように改善できます。
// Buggy example for debug50
#include
#include
void print_column(int height);
int main(void)
{
int h = get_int("Height: ");
print_column(h);
}
void print_column(int height)
{
for (int i = 0; i height; i++)
{
printf("#\n");
}
}
このコードをコンパイルして実行しても、まだバグがあることに注目してください。
このバグに対処するために、新しいツールを使用します。
デバッグの2つ目のツールは、デバッガと呼ばれるものです。これは、コード内のバグを追跡するためにプログラマによって作成されたソフトウェアツールです。
VS Code では、あらかじめ設定されたデバッガが提供されています。
このデバッガを利用するには、まずコードの行番号のすぐ左側をクリックしてブレークポイントを設定します。そこをクリックすると、赤い点が表示されます。これを一時停止の標識と考え、コンパイラに停止を求めて、コードのこの部分で何が起こっているかを検討できるようにします。
次に、
debug50 ./buggy0を実行します。デバッガが起動し、コードの一行が金色のような色で光るのがわかります。文字通り、コードはその行で一時停止しています。ウィンドウの左上で、まだ値を持っていないhを含むすべてのローカル変数がどのように表示されているかに注目してください。ウィンドウの上部でステップオーバー (step over)ボタンをクリックすると、コードを一行ずつ進めることができます。hの値がどのように増えるかに注目してください。このツールはバグがどこにあるかを教えてくれるわけではありませんが、速度を落として、コードがステップごとにどのように実行されているかを確認するのに役立ちます。バグのあるコードの詳細をさらに調べる方法として、
ステップイン (step into)を使用することもできます。
配列
第0週では、
bool,int,char,stringなどのデータ型について話しました。各データ型は一定量のシステムリソースを必要とします。
bool 1 バイト
int 4 バイト
long 8 バイト
float 4 バイト
double 8 バイト
char 1 バイト
string ? バイト
コンピュータの内部には、利用可能なメモリの量が限られています。
物理的には、コンピュータのメモリ上で、特定の種類のデータがどのように格納されるかを想像することができます。1バイトのメモリしか必要としない char は、以下のようになっていると想像できるでしょう。
同様に、4バイトを必要とする int は、以下のようになっているかもしれません。
これらの概念を探求するプログラムを作成できます。ターミナルで code scores.c と入力し、次のようにコードを記述します。
// Averages three (hardcoded) numbers
#include
int main(void)
{
// Scores
int score1 = 72;
int score2 = 73;
int score3 = 33;
// Print average
printf("Average: %f\n", (score1 + score2 + score3) / 3.0);
}
最終的な計算結果が浮動小数点値としてレンダリングされるように、右側の数値が 3.0 という浮動小数点値であることに注目してください。
make scoresを実行すると、プログラムが動作します。
これらの変数がメモリにどのように格納されているか想像してみてください。
配列 (Arrays) とは、メモリ内に連続して格納される値のシーケンスです。
int scores[3] は、3つの scores を格納するために、 int サイズのメモリ領域を3つ連続して提供するようコンパイラに指示する方法です。プログラムを考慮して、コードを次のように修正できます。
// Averages three (hardcoded) numbers using an array
#include
#include
int main(void)
{
// Scores
int scores[3];
scores[0] = 72;
scores[1] = 73;
scores[2] = 33;
// Print average
printf("Average: %f\n", (scores[0] + scores[1] + scores[2]) / 3.0);
}
score[0] が、 scores という配列の 0 番目の位置にインデックスを指定してアクセスし、そこにどのような値が格納されているかを確認していることに注目してください。
上記のコードは動作しますが、まだ改善の余地があることがわかります。コードを次のように修正してください。
// Averages three numbers using an array and a loop
#include
#include
int main(void)
{
// Get scores
int scores[3];
for (int i = 0; i 3; i++)
{
scores[i] = get_int("Score: ");
}
// Print average
printf("Average: %f\n", (scores[0] + scores[1] + scores[2]) / 3.0);
}
for ループによって提供される i を使用して、 scores[i] と記述することで、 scores にインデックスを指定してアクセスしていることに注目してください。
平均値の計算を簡素化、つまり抽象化することができます。コードを次のように変更します。
// Averages three numbers using an array, a constant, and a helper function
#include
#include
// Constant
const int N = 3;
// Prototype
float average(int length, int array[]);
int main(void)
{
// Get scores
int scores[N];
for (int i = 0; i N; i++)
{
scores[i] = get_int("Score: ");
}
// Print average
printf("Average: %f\n", average(N, scores));
}
float average(int length, int array[])
{
// Calculate average
int sum = 0;
for (int i = 0; i length; i++)
{
sum += array[i];
}
return sum / (float) length;
}
average という新しい関数が宣言されていることに注目してください。さらに、 N という定数値 (const) が宣言されていることに注目してください。最も重要なのは、 average 関数が int array[] を引数に取っていることです。これは、コンパイラがこの関数に配列を渡すことを意味します。
- 配列はコンテナになれるだけでなく、関数間で受け渡すこともできます。
文字列
stringは単にchar型の変数の配列、つまり文字の配列です。
char と string を調べるために、ターミナルウィンドウで code hi.c と入力し、次のようにコードを記述します。
// Prints chars
#include
int main(void)
{
char c1 = 'H';
char c2 = 'I';
char c3 = '!';
printf("%c%c%c\n", c1, c2, c3);
}
これが文字の文字列を出力することに注目してください。
同様に、コードを次のように変更してみましょう。
#include
int main(void)
{
char c1 = 'H';
char c2 = 'I';
char c3 = '!';
printf("%i %i %i\n", c1, c2, c3);
}
%c を %i に置き換えることで、ASCIIコードが印刷されることに注目してください。
以下の画像を考えると、文字列は最初の文字で始まり、 NUL文字 と呼ばれる特別な文字で終わる文字の配列であることがわかります。
これを10進数で想像すると、配列は以下のようになります。
string がどのように機能するかをさらに理解するために、コードを次のように修正します。
// Treats string as array
#include
#include
int main(void)
{
string s = "HI!";
printf("%c%c%c\n", s[0], s[1], s[2]);
}
printf ステートメントが、 s という配列から3つの値を提示していることに注目してください。
以前と同様に、 %c を次のように %i に置き換えることができます。
// Prints string's ASCII codes, including NUL
#include
#include
int main(void)
{
string s = "HI!";
printf("%i %i %i %i\n", s[0], s[1], s[2], s[3]);
}
これが、NULを含む文字列のASCIIコードを印刷することに注目してください。
HI! と BYE! の両方を表示したいとしましょう。コードを次のように変更します。
// Multiple strings
#include
#include
int main(void)
{
string s = "HI!";
string t = "BYE!";
printf("%s\n", s);
printf("%s\n", t);
}
この例では、2つの文字列が宣言され、使用されていることに注目してください。
これは次のように視覚化できます。
このコードはさらに改善できます。コードを次のように変更します。
// Array of strings
#include
#include
int main(void)
{
string words[2];
words[0] = "HI!";
words[1] = "BYE!";
printf("%s\n", words[0]);
printf("%s\n", words[1]);
}
両方の文字列が string 型の単一の配列内に格納されていることに注目してください。
2つの文字列を文字列の配列にまとめることができます。
#include
#include
int main(void)
{
string words[2];
words[0] = "HI!";
words[1] = "BYE!";
printf("%c%c%c\n", words[0][0], words[0][1], words[0][2]);
printf("%c%c%c%c\n", words[1][0], words[1][1], words[1][2], words[1][3]);
}
words の配列が作成されていることに注目してください。これは文字列の配列です。各単語は words に格納されます。
文字列の長さ
プログラミング、特にC言語における一般的な問題は、配列の長さを発見することです。これをコードでどのように実装できるでしょうか？ターミナルウィンドウに code length.c と入力し、次のようにコーディングします。
// Determines the length of a string
#include
#include
int main(void)
{
// Prompt for user's name
string name = get_string("Name: ");
// Count number of characters up until '\0' (aka NUL)
int n = 0;
while (name[n] != '\0')
{
n++;
}
printf("%i\n", n);
}
このコードが NUL 文字が見つかるまでループすることに注目してください。
このコードは、カウントを関数に抽象化することで、次のように改善できます。
// Determines the length of a string using a function
#include
#include
int string_length(string s);
int main(void)
{
// Prompt for user's name
string name = get_string("Name: ");
int length = string_length(name);
printf("%i\n", length);
}
int string_length(string s)
{
// Count number of characters up until '\0' (aka NUL)
int n = 0;
while (s[n] != '\0')
{
n++;
}
return n;
}
string_length という新しい関数が、NULが配置されるまで文字をカウントすることに注目してください。
これはプログラミングにおいて非常によくある問題であるため、他のプログラマが string.h ライブラリに文字列の長さを取得するコードを作成しています。コードを次のように変更することで、文字列の長さを取得できます。
// Determines the length of a string using a function
#include
#include
#include
int main(void)
{
// Prompt for user's name
string name = get_string("Name: ");
int length = strlen(name);
printf("%i\n", length);
}
このコードが、ファイルの先頭で宣言された string.h ライブラリを使用していることに注目してください。さらに、そのライブラリの strlen という関数を使用して、渡された文字列の長さを計算しています。
- 私たちのコードは、先人のプログラマの肩の上に立ち、彼らが作成したライブラリを利用することができます。
ctype.h も非常に便利なライブラリです。すべての小文字を大文字に変換するプログラムを作成したいとしましょう。ターミナルウィンドウで code uppercase.c と入力し、次のようにコードを記述します。
// Uppercases a string
#include
#include
#include
int main(void)
{
string s = get_string("Before: ");
printf("After: ");
for (int i = 0, n = strlen(s); i n; i++)
{
if (s[i] >= 'a' && s[i] 'z')
{
printf("%c", s[i] - 32);
}
else
{
printf("%c", s[i]);
}
}
printf("\n");
}
このコードが文字列内の各値を反復していることに注目してください。プログラムは各文字を調べます。文字が小文字の場合、その値から32を引いて大文字に変換します。
先週の以前の作業を思い出すと、このASCII値チャートを覚えているかもしれません。
0
NUL
16
DLE
32
SP
48
0
64
@
80
P
96
`
112
p
1
SOH
17
DC1
33
!
49
1
65
A
81
Q
97
a
113
q
2
STX
18
DC2
34
”
50
2
66
B
82
R
98
b
114
r
3
ETX
19
DC3
35
#
51
3
67
C
83
S
99
c
115
s
4
EOT
20
DC4
36
$
52
4
68
D
84
T
100
d
116
t
5
ENQ
21
NAK
37
%
53
5
69
E
85
U
101
e
117
u
6
ACK
22
SYN
38
&
54
6
70
F
86
V
102
f
118
v
7
BEL
23
ETB
39
’
55
7
71
G
87
W
103
g
119
w
8
BS
24
CAN
40
(
56
8
72
H
88
X
104
h
120
x
9
HT
25
EM
41
)
57
9
73
I
89
Y
105
i
121
y
10
LF
26
SUB
42
*
58
:
74
J
90
Z
106
j
122
z
11
VT
27
ESC
43
+
59
;
75
K
91
[
107
k
123
{
12
FF
28
FS
44
,
60
<
76
L
92
\
108
l
124
13
CR
29
GS
45
-
61
=
77
M
93
]
109
m
125
}
14
SO
30
RS
46
.
62
>
78
N
94
^
110
n
126
~
15
SI
31
US
47
/
63
?
79
O
95
_
111
o
127
DEL
- 小文字から
32を引くと、同じ文字の大文字になります。
プログラムはやりたいことを実現していますが、 ctype.h ライブラリを使用するより簡単な方法があります。プログラムを次のように変更します。
// Uppercases string using ctype library (and an unnecessary condition)
#include
#include
#include
#include
int main(void)
{
string s = get_string("Before: ");
printf("After: ");
for (int i = 0, n = strlen(s); i n; i++)
{
if (islower(s[i]))
{
printf("%c", toupper(s[i]));
}
else
{
printf("%c", s[i]);
}
}
printf("\n");
}
プログラムが文字列の各文字を反復処理していることに注目してください。 toupper 関数に s[i] が渡されます。各文字（小文字の場合）は大文字に変換されます。
toupper は小文字だけを大文字に変換することを自動的に認識していることは特筆に値します。したがって、コードは次のように簡略化できます。
// Uppercases string using ctype library
#include
#include
#include
#include
int main(void)
{
string s = get_string("Before: ");
printf("After: ");
for (int i = 0, n = strlen(s); i n; i++)
{
printf("%c", toupper(s[i]));
}
printf("\n");
}
このコードが ctype ライブラリを使用して文字列を大文字にすることに注目してください。
ctypeライブラリのすべての機能については、 Manual Pages で読むことができます。
コマンドライン引数
コマンドライン引数 (Command-line arguments) とは、コマンドラインでプログラムに渡される引数のことです。例えば、 clang の後に入力したすべてのステートメントはコマンドライン引数と見なされます。これらの引数は自分のプログラムで使用できます！
ターミナルウィンドウで code greet.c と入力し、次のようにコードを記述します。
// Uses get_string
#include
#include
int main(void)
{
string answer = get_string("What's your name? ");
printf("hello, %s\n", answer);
}
これがユーザーに hello と言うことに注目してください。
それでも、プログラムが実行される前に引数を受け取ることができれば便利だと思いませんか？コードを次のように変更します。
// Prints a command-line argument
#include
#include
int main(int argc, string argv[])
{
if (argc == 2)
{
printf("hello, %s\n", argv[1]);
}
else
{
printf("hello, world\n");
}
}
このプログラムが、コマンドライン引数の数である argc と、コマンドラインで引数として渡された文字の配列である argv の両方を知っていることに注目してください。
- したがって、このプログラムの構文を使用すると、
./greet Davidを実行するとプログラムがhello, Davidと言う結果になります。
次のコードで、各コマンドライン引数を印刷できます。
// Prints command-line arguments
#include
#include
int main(int argc, string argv[])
{
for (int i = 0; i argc; i++)
{
printf("%s\n", argv[i]);
}
}
終了ステータス
プログラムが終了すると、特別な終了コードがコンピュータに提供されます。
プログラムがエラーなしで終了すると、ステータスコード
0がコンピュータに提供されます。多くの場合、プログラムの終了につながるエラーが発生すると、ステータス1がコンピュータによって提供されます。
code status.c と入力し、次のようにコードを記述することで、これを説明するプログラムを作成できます。
// Returns explicit value from main
#include
#include
int main(int argc, string argv[])
{
if (argc != 2)
{
printf("Missing command-line argument\n");
return 1;
}
printf("hello, %s\n", argv[1]);
return 0;
}
./status David を提供しなかった場合、終了ステータス 1 が返されることに注目してください。しかし、 ./status David を提供した場合は、終了ステータス 0 が返されます。
ターミナルで
echo $?と入力すると、最後に実行されたコマンドの終了ステータスを確認できます。ユーザーが正しい数のコマンドライン引数を提供したかどうかを確認するために、上記のプログラムの一部をどのように使用できるか想像できるでしょう。
暗号
暗号学 (Cryptography) とは、メッセージを暗号化したり復号したりする技術です。
これで、配列、文字 (char)、および文字列という構成要素を使用して、メッセージを暗号化および復号できるようになりました。
平文 (plaintext) と 鍵 (key) が 暗号 (cipher) に提供され、結果として暗号化されたテキストが得られます。
鍵は、平文とともに暗号に渡される特別な引数です。暗号は鍵を使用して、暗号アルゴリズムをどのように実装するかを決定します。
今週は、上記のようなプログラミングの課題に取り組みます。
まとめ
このレッスンでは、コンパイルの詳細と、コンピュータ内にデータがどのように格納されるかについて詳しく学びました。具体的には、以下のことを学びました。
一般的なコンパイラの仕組み。
4つのメソッドを使用してコードをデバッグする方法。
コード内で配列を利用する方法。
配列がどのようにメモリの連続した部分にデータを格納するか。
文字列が単なる文字の配列であること。
コード内で配列を操作する方法。
コマンドライン引数をプログラムに渡す方法。
暗号学の基本的な構成要素。
また次回お会いしましょう！