第2章 · 選択と反復

if、while、for

プログラムは、文を1つずつ順番に実行します。その順序を変えるものが2つあります。選択はどの文を実行するかを選び、反復は文をもう一度実行します。

図のプログラムはn = 5から始まります。nが1でない間、nが偶数なら半分にし、奇数なら3倍して1を加え、ステップを数えます。一番上のひし形はループの問いで、その下のひし形は if の問いです。赤いトークンは実行中の位置で、その横のコードは実行中の行を光らせます。

int n = 5; int steps = 0; while (n != 1) { if (n % 2 == 0) { n = n / 2; } else { n = 3 * n + 1; } steps++; } System.out.println(steps);

nは5, 16, 8, 4, 2, 1と変化します。ループの条件は6回調べられ、true が5回、最後に false が1回出て、プログラムは5を出力します。

この章は AP Computer Science A の単元2で、選択問題の得点の25〜35%を占めます。内容は、ブール式と if 文（2.1〜2.6）、while ループと for ループ（2.7〜2.8）、それらから作られる標準的なアルゴリズム（2.9〜2.10）、ループの中のループ（2.11）、文が何回実行されるかの数え方（2.12）です。

2.1 · 選択と繰り返しによるアルゴリズム

3つの構成要素

どのアルゴリズムも、順次実行（順番に並んだ手順）、選択（判断）、繰り返し（ループ）の3つから作られます。

選択は、アルゴリズムの進み方が真か偽かの判断で決まるときに起こります。繰り返しは、望む結果になるまで処理を繰り返すことです。どちらも日常の指示に現れます。「雨が降っていたら傘を持っていく」は選択、「砂糖が溶けるまでかき混ぜる」は繰り返しです。

アルゴリズムは、言葉で書くことも、フローチャートで描くこともできます。手順ごとに箱、真偽の判断ごとにひし形、繰り返しには上へ戻る矢印を使います。図は、この同じアルゴリズムを言葉で書いたものを示します。「n は偶数？」「半分にする」「ステップを数える」です。コードは、まったく同じことを Java で表します。

手順の順序によって、結果が変わります。次の2つの部分には、同じ文が入っています。

int x = 3; x = x * 2; x = x + 1;

int x = 3; x = x + 1; x = x * 2;

1つ目はxを7にし、2つ目は8にします。図で、ステップを数えるのをループの中ではなくループの後にすると、ループが何回実行されても1が出力されます。

2.2 · ブール式

関係演算子

ブール式は、trueかfalseの2つの値のどちらかに評価されます。最も単純なものは、関係演算子で2つの値を比べます。

==と!=は、2つの値が同じか異なるかを調べます。<、>、<=、>=は、数を比べます。int、double、booleanのような基本型では、==は実際の値を比べます。参照型では参照を比べ、2つの変数が同じオブジェクトを参照しているかを調べます（2.6）。

図では、aが7を持ち、bが4, 7, 9の値を取ります。比較のたびにブロックが1つできて、true は赤で示されます。

=は代入し、==は比較します。ブール値の結果は、ほかの値と同じように格納できます：boolean same = a == b;

2.3 · if 文

一方向の選択と二方向の選択

選択文は、文を順に実行する流れを変えます。if 文は、ブール式の値に応じて、異なるコードの部分を実行します。

一方向の選択（if）には部分が1つあり、条件が true のときだけ実行されます。

if (temp >= 30) { System.out.println("hot"); } System.out.println("done");

tempが34のときはhot then doneを出力し、22のときはdoneだけを出力します。最後の行は if の後ろにあるので、常に実行されます。

二方向の選択（if-else）には部分が2つあります。条件が true のときは if の本体、false のときは else の本体です。そのうちのちょうど1つが実行されます。

if (temp >= 30) { System.out.println("hot"); } else { System.out.println("mild"); } System.out.println("done");

図では、2つの気温をこれに通します。34のときトークンは true の道を通ってhotを出力し、22のときは false の道を通ってmildを出力します。その後、どちらもdoneを出力します。

2.4 · 多方向の選択

if、else if、else

多方向の選択（if-else-if）は、一連の条件を順に調べます。最初に true になった条件の部分が実行され、実行される部分は多くても1つです。

if (score >= 90) { grade = "A"; } else if (score >= 80) { grade = "B"; } else if (score >= 70) { grade = "C"; } else { grade = "F"; }

図では、3つの得点を鎖の上から落とします。83はscore >= 90を満たさず、score >= 80を満たして捕まります：成績は"B"です。その下の条件は調べられません。95は最初の関門"A"で捕まります。64は3つとも満たさないので、最後のelseが実行されます："F"。最後の else がなければ、どの条件も満たさない値では、どの部分も実行されません。

最初に true になった条件が採用されるので、順序が大切です。score >= 70を最初に調べると、95は"C"になります。70以上の得点は、すべて最初の関門で止まるからです。最も厳しい条件を最初に置きます。

2.4 · 入れ子の if 文

if の中の if

入れ子の if 文は、if、if-else、if-else-if 文の中にある、if、if-else、if-else-if 文です。

if (age >= 16) { if (hasPermit) { System.out.println("may drive"); } else { System.out.println("needs a permit"); } } System.out.println("done");

内側の条件は、外側の条件が true のときだけ評価されます。図では3人を通します。年齢17で許可証あり：両方を通過してmay driveを出力します。年齢17で許可証なし：外側の判定は通過し、内側で不合格になります：needs a permit。年齢14：外側の判定で不合格になるので、トークンは箱全体を迂回します。hasPermitは調べられることすらなく、出力されるのはdoneだけです。

どの if に else が属するかは、波括弧で決まります。ここでは else が外側の波括弧の中にあるので、if (hasPermit)と対になります。16未満の人には、許可証についてのメッセージがまったく出ません。

2.5 · 複合ブール式

!、&&、||

論理演算子の!（not）、&&（and）、||（or）は、ブール式を組み合わせて、それ自体が真か偽になる1つの式にします。

!aはaが false のとき true で、それ以外は false です。a && bは両方が true のときだけ true です。a || bは、aが true か、bが true か、その両方のとき true です。図では、すべての組み合わせを1行ずつ見ていきます。

優先順位は、!が最初で、次が&&、その次が||です。そのため、a = false、b = true、c = falseのとき、式!a || b && cは(!a) || (b && c)を意味し、結果はtrueです。代わりに(!a || b) && cとまとめると、falseになります。括弧を使うと、順序がはっきりします。

関係演算子は論理演算子より先に働くので、x > 0 && x < 10はまず比較し、その後で組み合わせます。0より大きく10より小さいすべてのxで true になります。

2.5 · 短絡評価

右辺は実行されないことがある

&&や||の左のオペランドだけで結果が決まるとき、Java は右のオペランドを評価しません。これが短絡評価です。

右辺が何を言おうと、false && anythingは false で、true || anythingは true です。そのため右辺はスキップされます。図では2つの式を、最初はx = 4で、次はx = 0で評価します。

x != 0 && 10 / x > 2 x == 0 || 10 / x > 2

x = 4のとき、両方の式の両辺が実行されます。10 / 4は2（整数の除算）で、2より大きくないので、1つ目はfalseで、2つ目もそうです。

x = 0のとき、x != 0は false なので、1つ目はすぐにfalseになります。また、x == 0は true なので、2つ目はすぐにtrueになります。どちらでも10 / xは実行されず、これは好都合です。intを0で割ると、ArithmeticExceptionが投げられるからです。

これにより、左のオペランドが番人になります。逆の順序で書くと、10 / x > 2 && x != 0は先に割り算をして、xが0のときにクラッシュします。

2.6 · 同値なブール式

真理値表とド・モルガンの法則

2つのブール式は、すべての場合で同じ値に評価されるとき、同値です。入力のすべての組み合わせについて1行ずつ書いた真理値表で、それを証明できます。

ド・モルガンの法則は、2つの同値を与えます。

!(a && b) は !a || !b と同値 !(a || b) は !a && !b と同値

括弧の内側に!を入れるには、各部分を否定し、&&を||に、または||を&&に入れ替えます。図では、2番目の式の各列が1番目の式の上にすべり込みます。どの行でも色が一致します。

演算子の入れ替えを忘れると成り立ちません。!(a && b)と!a && !bは、4行のうち2行で異なります。否定された比較は演算子が反転します。!(x > 5)はx <= 5です。したがって、!(x >= 1 && x <= 10)はx < 1 || x > 10と同値です。

2.6 · オブジェクトの比較

== と equals

2つの異なる変数が、同じオブジェクトへの参照を持つことがあります。参照に対する==と!=は、2つのオブジェクトの内容が同じかではなく、同じオブジェクトを参照しているかを調べます。

String s1 = new String("atlas"); String s2 = s1; String s3 = new String("atlas"); String s4 = null;

s2 = s1は参照をコピーするので、s1とs2は1つのオブジェクトを指します。s1 == s2はtrueです。s3は、同じ文字を持つ2つ目のオブジェクトを参照します。s1 == s3はfalseです。

クラスはしばしば、2つのオブジェクトがいつ等しいとみなされるかを示すequalsメソッドを定義し、たいていは属性を比べます。糸のそれは文字を比べるので、s1.equals(s3)はtrueです。文字列の比較にはequalsを使い、==は決して使いません。

参照が何らかのオブジェクトを参照しているかどうかは、nullと==または!=で比べて調べられます。s4 == nullはtrueです。（equalsメソッドのオーバーライドは、このコースの範囲外です。）

2.7 · while ループ

調べ、実行し、また調べる

反復は繰り返しの一形態です。反復文は、ブール式が true である間、コードの部分を0回以上繰り返します。

while ループでは、最初も含めて、本体を1回通るたびに、その前にブール式が評価されます。true の間は本体が実行され、false になるとループが終わって、プログラムはその後ろへ進みます。

int sum = 0; int k = 1; while (k <= 4) { sum += k; k++; } System.out.println(sum);

トレース表は、条件が調べられるたびに変数を記録します。図では、この表を1行ずつ埋めていきます。

条件は5回調べられ、本体は4回実行されます。最後の判定が false になります。ループはk = 5で終わり、10が出力されます。

2.7 · うまくいかないループ

一度も実行されない、終わらない、1つ足りない

ループのバグの多くは、次の3つのどれかです。ループが一度も実行されない、止まらない、または実行が1回多いか1回少ないかです。

ブール式が最初に false なら、本体は一度も実行されません。kが10のときのwhile (k < 5)は、1回調べて先へ進みます（一番上の行）。

無限ループは、ブール式が常に true に評価されるときに起こります。真ん中の行では、kが1, 3, 5, 7, 9、…と進み、6にはならないので、while (k != 6)は false になりません。条件の中の変数を本体が一度も変えないループも、同じことになります。

オフバイワンエラーは、ループが1回多いか1回少なく実行されることです。1から5までを出力するつもりが、一番下のループは1234を出力します。while (k < 5)は5の手前で止まってしまうからです。k <= 5で直ります。

int k = 1; while (k < 5) { System.out.print(k); k++; }

ループは端で確かめましょう。最初の回、最後の回、そして終わらせる判定です。

2.8 · for ループ

初期化、ブール式、更新

for ループは、カウント用ループの3つの部分、つまり初期化、ブール式、更新をヘッダーにまとめたものです。

for (int i = 0; i < 3; i++) { System.out.println(i); }

初期化は、最初の判定の前に1回だけ実行されます。そこで設定される変数がループ制御変数です。ブール式は初期化の直後に評価され、その後は更新のたびに、false になるまで再び評価されます。各回では、更新は本体全体の後、次の判定の前に実行されます。

図のトークンは、初期化 → 判定 → 本体 → 更新 → 判定 …と進みます。各ステーションの下の回数は、初期化1、判定4、本体3、更新3です。出力は0, 1, 2で、それぞれ別の行になります。

for ループは、同値な while ループに書き換えられ、その逆も同じです。

int i = 0; while (i < 3) { System.out.println(i); i++; }

1つ違いがあります。for のヘッダーで宣言されたiは、ループの中にしか存在しませんが、while ループの前で宣言すれば、その後ろにも残ります。

2.9 · 桁と割り切れること

% 10、/ 10、% k

剰余演算子を使う標準的なアルゴリズムが2つあります。整数を1桁ずつ分解することと、ある整数が別の整数で割り切れるかを調べることです。

正のint nについて、n % 10は最後の桁で、n / 10（整数の除算）は、その桁を取り除いたnです。nが0になるまで繰り返します。

int n = 3725; int sum = 0; int max = 0; int odd = 0; while (n > 0) { int d = n % 10; sum += d; if (d > max) { max = d; } if (d % 2 == 1) { odd++; } n /= 10; }

図では、3725の桁を右から5, 2, 7, 3と取り出し、それぞれがdを通ります。

a % b == 0は、aがbで割り切れるときちょうど true です。3725 % 5は0なので、3725は5で割り切れます。3725 % 3は2なので、3では割り切れません。2で同じ判定をすると偶数と奇数に分けられ、ループの中のd % 2 == 1がそうしています。

2.9 · 合計、平均、最大・最小、個数

ループが回るにつれて積み上げる

標準的なアルゴリズムは、ほかにもあります。ループの前で宣言した変数に途中の値を持たせ、ループの中で更新する、合計、最小値または最大値、個数です。

合計は 0 から始めて、値を 1 つずつ加えます: sum += d。3725 のとき、sum は最後に 17 になります。

平均は、合計を値の個数で割ったものです。整数の除算に注意します。

double avg = (double) sum / 4; int avgInt = sum / 4;

avg は 4.25 ですが、avgInt は 4 で、小数部分が切り捨てられます。割る前にキャストします。割った後ではありません。

最大値は、これまでで最も大きい値を保持し、それより大きい値が来るたびに置き換えます: if (d > max)。ここでは max は最後に 7 になります。初期値は最初の値にするか、実際の値がそれより小さくならない値にします。0 でよいのは、数字が負にならないからです。一般には Integer.MIN_VALUE を使います。最小値はその鏡像で、Integer.MAX_VALUE から始めて < を調べます。最小の数字は 2 です。

基準を満たす回数の個数は、0 から始めて、if の中で 1 を加えます。if (d % 2 == 1) は奇数の数字を数え、結果は 3 個です。

2.10 · String のアルゴリズム

反転と部分文字列の個数

String のアルゴリズムは、文字列に沿ってインデックスを進め、各位置で部分文字列を取り出します。新しい文字列を作るか、ある性質をもつ部分文字列を調べたり数えたりするために使います。

文字列を反転するには、1 文字ずつ、それまでに作った文字列の前に置きます。substring(i, i + 1) は、インデックス i の 1 文字です。

String word = "drawer"; String rev = ""; for (int i = 0; i < word.length(); i++) { rev = word.substring(i, i + 1) + rev; }

rev は "d", "rd", "ard", "ward", "eward", "reward" に伸びていきます。(rev = rev + word.substring(i, i + 1) だと、単語がそのままコピーされます。)

基準を満たす部分文字列を数えるには、窓をずらしながら 1 つずつ調べます。

String s = "banana"; int count = 0; for (int i = 0; i < s.length() - 1; i++) { if (s.substring(i, i + 2).equals("an")) { count++; } }

窓 substring(i, i + 2) は "ba", "an", "na", "an", "na" を見ます。2 が一致するので、count は 2 です。最後の窓の開始位置はインデックス 4 なので、i は s.length() - 1 未満で止めなければなりません。もう 1 つ進むと、substring(5, 7) は末尾を越えて StringIndexOutOfBoundsException をスローします。

部分文字列の比較には equals を使います。ある部分文字列が性質をもつか調べるだけなら、同じループを最初に見つかった時点で止められます。あるいは indexOf を使うと、指定した部分文字列が最初に現れる位置が返り、どこにもなければ −1 が返ります。

2.11 · 入れ子の反復

ループの中のループ

入れ子の反復は、あるループの本体の中にあるループです。内側のループは、すべての反復を終えてから、外側のループが次の反復に進みます。

for (int r = 0; r < 3; r++) { for (int c = 0; c < 4; c++) { System.out.print(r * c + " "); } System.out.println(); }

r = 0 のとき、内側のループは c を 0 から 3 まで動かします。そのあと println が行を終え、それから初めて r が 1 になります。図は、行ごとに 1 マスずつ格子を光らせます。内側の本体は 3 × 4 = 12 回実行され、次のように出力します。

0 0 0 0 0 1 2 3 0 2 4 6

内側のループの範囲は、外側の変数に依存させることもできます。ここでは内側のループが r + 1 回実行されるので、反復の回数は 1, 2, 3, 4 です。

int count = 0; for (int r = 0; r < 4; r++) { for (int c = 0; c <= r; c++) { count++; } }

count は 10 で終わり、長方形ではなく三角形になります。

2.12 · 実行時間の非形式的な解析

文が何回実行されるかを数える

文の実行回数は、ある文が実行される回数です。ふつうは非形式的に、いくつかの反復をたどり、ループについて考えて求めます。

for (int i = 0; i < n; i++) { count++; }

i が 0 から n − 1 までのとき、count++ は n 回実行されます。検査 i < n は n + 1 回実行されます。ループを終えるために、もう 1 回多く実行されます。

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { count++; } }

入れ子では、n 回ある外側の反復のそれぞれが、内側のループを n 回実行します。したがって count++ は n × n 回実行されます。n = 6 のとき、それは 6 回と 36 回です。n = 8 のとき、8 回と 64 回です。n が大きくなると、図の数は両方とも増えます。n を 2 倍にすると、片方は 2 倍に、もう片方は 4 倍になります。

回数は、ループの範囲から数えます。for (int i = 1; i <= n; i++) も n 回実行されます。1 から始まる i < n は n − 1 回実行されます。前のページのような三角形は 1 + 2 + … + n 回実行されます。このような回数を比べれば、ストップウォッチを使わずに、あるループがほかより速いと言えます。