共通テスト情報I 二重の繰り返し—内側の回数を外側ごとに分けて数える｜武蔵野個別指導塾

段ごとに札の組を書き出し、内側の回数が変わる処理を、各段の件数と累積値から追跡します。

よくあるのは、高校生が外側の値によって内側の繰り返し回数が変わる処理を、外側の回数と最後の内側の回数を掛けて数えるという場面です。例えば、列ごとに並べる札の枚数が増えるなら、最後の列の枚数をすべての列に当てはめることはできません。外側の1回ごとに、内側でどの組が作られるかを追います。

何を数える問題なのか

二重の繰り返しは、繰り返しの中に別の繰り返しが入る処理です。外側が1回進むたびに、内側の開始から終了までが実行されます。内側の処理を何回行ったかと、外側が何回進んだかは別の数です。まず問われているのが処理回数、出力される組、最終的な変数の値のどれかに印を付けます。

出方の1つは、内側の範囲がいつも同じ場合です。外側の各回で同じ数の組を作るので、外側の回数と内側の回数を掛けられます。もう1つは、内側の終点が外側の値で決まる場合です。各回の内側の回数を並べ、その合計を取ります。さらに、内側の条件を満たす組だけを数える場合は、作られた組と数えられた組を分けて調べます。

掛け算が使えるかは、見た目に二重になっているかではなく、各回の内側の実行回数が等しいかで決まります。範囲の端を含むか、内側に入る前に変数が何に戻るかも読み取ります。以下の処理は学習のための自作記法で、実際の試験の表記と同一であることを前提にしません。

外側の1回をまとまりとして見る

図1のように、外側の値を1つ固定し、その値に対応する内側の値を初めから順に並べます。外側が次の値になると、内側はその回の開始値から再び始まります。組の左側が外側、右側が内側の値です。組は実行の順序も残すので、件数と出力順の両方の確認に役立ちます。

図1では外側が1のとき内側は1、外側が2のとき内側は1と2です。内側の値が前の回の2から続くわけではありません。内側の終点が外側の値に依存するため、回数は1回、2回と変わります。組を行に並べれば、どの行に何個あるかを見落としにくくなります。

以下では「aからbまで」は両端を含み、1ずつ増やします。開始値が終了値より大きい場合は、その繰り返しを0回実行します。「←」は右側の値を左側に代入することを表します。条件の「同じ」は値の比較です。整数除算と剰余は使いません。配列も使わないため添字はありません。インデントは処理がどの繰り返しの内側にあるかを示します。

内側の処理が終わるたびに変数を更新するなら、組ごとの更新を記録します。内側が終わってから更新する行なら、外側の1回につき1回です。出力の行が内側か外側かでも、表示される数の個数と時点が変わります。数式を立てる前に、その行がどの枠に属するか確かめます。

基本例題：段ごとに札を並べる

段番号 i が1から3まであり、段 i に札番号 j を1から i まで付けます。次の処理で出力される組を順に並べ、最後の n を整数で答えてください。組の出力と n の更新は内側で行い、最後の n の出力は両方の繰り返しが終わってから行います。

n ← 0
i を1から3まで繰り返す
  j を1から i まで繰り返す
    組 (i, j) を出力する
    n ← n + 1
n を出力する

最初に n は0です。i が1の回は j が1なので、(1, 1) を出力し、n は1になります。i が2の回は j が1、2となり、(2, 1)、(2, 2) の順に出力します。その2回の更新で n は2、3になります。i が3の回は j が1、2、3となり、(3, 1)、(3, 2)、(3, 3) を出力します。n は順に4、5、6です。

図2のように、行ごとの回数を1、2、3と分けます。合計は1 + 2 + 3で6回です。出力順は上記の6組で、最後の n は6です。各段の札を元の条件で数えると、1段目は1枚、2段目は2枚、3段目は3枚となり、出力した6組と対応します。

図2の右端は、その段の処理を終えた時点の n です。最後の3を3回分とみなして3 × 3とすると、1段目に2組、2段目に1組を余分に数えます。最後の内側の値が3であることと、どの段でも3回実行することは違います。

同じ処理で外側の終点が0なら、開始値1が終点を超えるため外側は0回です。組は出力されず、初期値の n が0と出力されます。内側に一度も入らない場合でも、繰り返しの外にある最後の出力は実行されます。逆に、出力が内側にしかなければ0回の場合は何も表示されません。

条件に合う組だけを数える

次は外側の各回で内側の範囲が変わり、さらに条件を満たす組を数えます。a を1から4まで、b を1から a まで動かします。組を作るたびに、a と b が同じなら c を1増やします。c は最初に0とし、両方の繰り返しが終わってから出力します。内側の実行回数と最後の c をそれぞれ整数で求めてください。

c ← 0
a を1から4まで繰り返す
  b を1から a まで繰り返す
    もし a と b が同じなら
      c ← c + 1
c を出力する

内側で作る組は、a が1のとき (1, 1)、2のとき (2, 1)、(2, 2)、3のとき (3, 1)、(3, 2)、(3, 3)、4のとき (4, 1)、(4, 2)、(4, 3)、(4, 4) です。内側の実行回数は1 + 2 + 3 + 4で10回です。

条件に合うのは各行の最後の (1, 1)、(2, 2)、(3, 3)、(4, 4) です。c は各行で1回ずつ増え、順に1、2、3、4となります。したがって最後の c は4です。元の範囲に戻すと、各 a について b は1から a まで動くので、b が a と同じになる機会は各行の終点にあります。10回の実行と4回の更新を混同しないことが必要です。

もし条件を「a と b が同じでない」に変えるなら、同じ組の4回では更新されず、残りの6回で更新されます。条件を変えた後も、内側の範囲自体は変わらないので実行回数は10回のままです。反対に、b の終点を a より1小さい値に変えると、a が1の回は b を1から0まで動かすことになり0回です。同じ条件で更新される組はなく、c は0です。条件と範囲のどちらを変えたのかを区別します。

9回という誤答を直す

基本例題で「i が3回、最後に j が3回だから9回」とした場合を考えます。誤りの原因は、各段の内側の回数が等しいと決めたことです。図3のように、3段分をそれぞれ3回として作った一覧には、元の条件 j が i 以下を満たさない組が含まれます。

図3の余分な組は (1, 2)、(1, 3)、(2, 3) です。1段目では j の終点は1、2段目では2なので、これらは実行されません。9組から余分な3組を除けば6組です。図3の右側の回数1、2、3を直接足しても、同じ6回に戻ります。

別の誤りは、内側が終わるたびに n を0に戻すことです。基本例題の初期化は両方の繰り返しより前に1回だけあります。各段の前に移せば最後の段の3回分しか残らず、答えは元の処理と変わります。変数の値を追うときは、更新式に加えて初期化の位置にも印を付けます。

また、内側の終点を含まないと読み替えると、各段の最後の組を落とします。問題で「まで」の意味が定義されているかを確かめ、初回と最終回を具体的な組に戻してください。ここでは両端を含むので、(3, 3) も出力されます。

回数が同じでも確認したいこと

内側の終点に外側の変数が現れなければ、上の基本例より回数をまとめやすくなります。ただし、内側の開始値と終了値の差をそのまま回数とするとは限りません。例えば1から4までなら、1、2、3、4の4回です。端点を両方含むときは、最後の値から最初の値を引いた差に1を加えて数えます。開始値が終点を超える場合は、この計算をそのまま適用せず0回と判断します。

内側の回数が一定でも、途中で条件によって更新される回数は一定とは限りません。外側の値と内側の値を比べる条件なら、外側の値が変わると一致する機会も変わります。処理全体の回数を掛け算で数えた後、更新対象の組を別に選ぶという2段階に分けると、何を数えた数字か明確になります。

組の順番を問われる場合には、件数だけでは答えになりません。外側の値を固定して内側を最後まで進めてから、次の外側の値に移ります。組の左右を逆に書いたり、内側の値を固定して外側を先に進めたりすると、同じ組が含まれていても出力順が変わります。最後の組だけでなく、行が切り替わる位置も追うと、順序の読み違いを見つけられます。

変数の最終値を問われた場合は、出力直前の値を答えます。途中で同じ変数を表示する処理があれば、その時点の値と最後の値は別に記録します。0回の繰り返しでは更新が起きないため、初期値が残ります。処理の範囲を越える値まで推測せず、問題に定義された開始と終了に従って判断します。

自分で追う4問

次の各問でも、範囲は両端を含み1ずつ増え、開始値が終点を超えると0回です。代入は「←」、同じかどうかは値の比較です。整数除算、剰余、配列は使いません。組は左に外側、右に内側の値を書きます。

問1

外側 p を1から2まで、内側 q を1から4まで繰り返し、内側で組 (p, q) を1回ずつ出力します。組の総数を整数で答え、最後の組も示してください。

問2

外側 x を1から4まで、内側 y を1から x まで繰り返し、内側で組 (x, y) を作ります。x が2の回と4の回の組をそれぞれ順に示し、全体の組の総数を整数で答えてください。

問3

外側 r を1から3まで、内側 s を2から r まで繰り返します。内側を実行するたびに、最初は0の t を1増やします。両方の繰り返しの後に出力する t を整数で答え、各 r の回数も示してください。

問4

外側 u を1から3まで、内側 v を1から2まで繰り返します。最初は0の w を、組を作るたびに u と v が同じなら1増やします。内側の実行回数と、両方の繰り返しの後の w をそれぞれ整数で答えてください。

答えと追跡の道筋

問1は8組、最後は (2, 4) です。p が1でも2でも q は1、2、3、4と動きます。各回4組なので4 + 4、または2 × 4で8組です。最後は外側の最終値2と内側の最終値4の組です。どちらの行も4組あることを元の範囲から確かめられます。

問2の x が2の回は (2, 1)、(2, 2)、4の回は (4, 1)、(4, 2)、(4, 3)、(4, 4) です。各行の個数は順に1、2、3、4なので、総数は10組です。x が3の回も3組あることを含めて数えます。終点は毎回 x に変わるため、4行に最後の4組を掛けることはできません。

問3は各 r の回数が順に0、1、2で、出力される t は3です。r が1の回は s が2から1までなので0回です。r が2の回は (2, 2) の1回、r が3の回は (3, 2)、(3, 3) の2回です。更新後の t は1、2、3と進みます。組を元の範囲に戻すと、どの s も2以上で、それぞれの r 以下です。

問4は内側が6回実行され、w は2です。u の各値について v は1、2なので、2回ずつ3行あります。同じ値になる組は (1, 1) と (2, 2) です。u が3の行には v が3の組がないため更新されません。6組を並べて照合すれば、条件を満たす2組と満たさない4組を区別できます。

手元に残す要点

外側を1回固定し、内側の開始と終了を確かめます。 内側の回数が各回で同じなら掛け算、変わるなら各回を足します。 条件付きの更新は、内側の実行回数と分けて数えます。 0回の行と、出力や初期化の位置を見落とさないようにします。

つまずいた位置を見つける

答えが合わないときは、まず外側の最初と最後の回について、内側の値を実際に書き出します。そこで回数が違えば、一定回数とみなして掛けた箇所に戻れます。回数は合うのに変数が違う場合は、初期値と更新が実行される組を表に加えます。

個別指導で確かめる際も、答えの数字だけでなく、どの組で値が変わったかを説明できるか見ます。0回の行で更新しない理由まで追えれば、範囲と処理の位置を使って別の条件にも対応できます。組の一覧は、繰り返しの回数を判断する根拠になります。