冬期講習 2026-2027、募集中。総復習は売りません。90分×完全1対1で、穴だけを塞ぎます 詳しく →
電話 0422-27-7828チャットで質問無料相談を予約

武蔵野個別指導塾の特徴

共通テスト情報I 内側の回数が変わる反復—外側と同じ値を含むかで列挙する組を比べる|武蔵野個別指導塾

学習のイメージ写真 武蔵野個別指導塾
X LINE Facebook

番号の組を列挙するとき、内側の開始位置によって自己の組が混ざる境界を追います。

よくあるのは、高校生が番号の組一覧を作り、異なる番号を選んだつもりなのに同じ番号同士が混ざる場面です。外側の番号を固定して内側の番号を動かすと、開始位置がたった1つ違うだけで、各行の最初に余分な組が現れます。数字はすべて説明のための自作条件です。実際にどの組が出るかを順番に追い、目的の一覧と照合します。

どんな違いを問われるか

一つ目は、内側の開始値を読み、出力される組とその順序を答える型です。外側が進むたびに内側の開始値も変わります。内側の回数が一定だと決めてしまうと、後ろの行を数えすぎます。

二つ目は、同じ処理の開始値だけを変え、増減した組を特定する型です。組の総数だけを比べると、差が偶然合っても、どの組が余分かはわかりません。各組の最初と次の番号を別々に見ます。

三つ目は、目的に合う開始値を選び、境界の場合でも成り立つかを説明する型です。番号が1個なら、異なる番号の組は作れません。一方、同じ番号を2回使ってよい一覧なら、その番号同士の組が1個あります。この小さな場合が、開始値の誤りを見分ける反例になります。

行と列で開始位置を捉える

番号は0から始まり、個数をnとすると最後はn-1です。ここで扱う組は順序を逆にしたものを別に数えず、先の番号をi、後の番号をjに置きます。iとjは配列の値ではなく番号そのものです。同じ番号同士を許すかどうかが、この一覧の条件です。

図1は、内側の開始をiにした場合とi+1にした場合を、上下の段で比べています。上段には自己の組と異なる番号の組、下段には異なる番号の組を示しています。

図1 内側の開始値ごとに自己の組の有無を比べる図

上段の赤枠が自己の組で、緑枠の異なる番号の組は上下に共通します。組を横方向j、縦方向iの格子へ置き直して考えると、自己の組はiとjが等しい対角に、異なる番号の組はその右側に当たります。開始をiからi+1に変えれば、各行の対角の組が1つずつ除かれ、右側の組は残ります。番号が異なれば札の内容が同じでも異なる番号の組なので、要素の中身の一致とは区別します。

Pythonのrange(a, b)はaから始め、bを含まず1ずつ進みます。開始が終点以上なら内側の処理は0回です。外側の各回で内側のrangeを作り直すので、内側が終わった前の行の位置から再開するわけではありません。出力は内側の反復のたびに、その時点のiとjを表示します。

基本例題:3個の番号を列挙する

展示の札に0、1、2の番号があります。次の自作プログラムは、同じ番号同士を含む組を表示します。表示される組を順に答え、内側の開始をi+1に変えた場合も答えてください。nは3で、上端3は含みません。

n = 3
for i in range(0, n):
    for j in range(i, n):
        print(i, j)

外側はiを0、1、2の順に選びます。各行でjの候補を作り、候補がある限り表示してから次の候補へ進みます。表の「終了」は次の候補がなく、内側の反復が終わった時点です。

外側i 内側の候補 順に表示する組 終了時
0 0、1、2 (0, 0)、(0, 1)、(0, 2) 次は上端3なので終了
1 1、2 (1, 1)、(1, 2) 次は上端3なので終了
2 2 (2, 2) 次は上端3なので終了

最初のiは0です。jは0から始まり、0が3未満なので(0, 0)を表示します。次のjは1で、同じく3未満なので(0, 1)を表示します。次の2も3未満なので(0, 2)を表示し、3は含まれないため内側を終えます。外側は1に進み、今度はjを1から作り直します。1と2でそれぞれ表示し、3に達するところで終えます。最後にiが2となり、jは2で1回表示され、次の3で終わります。外側の次の候補3も上端なので、全体が終わります。

図2のように行ごとに表示数が3、2、1と減り、合計は6組です。行の初めにある(0, 0)、(1, 1)、(2, 2)が自己の組です。

図2 3個の番号で各行が出力する組の順序

開始だけをi+1にすると、iが0の行は(0, 1)、(0, 2)、iが1の行は(1, 2)です。iが2の行は開始が3で上端と一致するため0回です。結果はこの順の3組であり、元の一覧から自己の3組を除いたものです。図2にある各行の先頭が消えることを照合できます。

標準例題:開始位置だけを変更する

4枚の自作カードに0から3の番号を付けます。基本例のnを4にして、内側の開始をiとする処理とi+1とする処理を比較します。それぞれの出力数と、前者にだけある組を答えてください。上端4は含まず、表示する時点も基本例と同じです。

i iから開始 i+1から開始
0 (0, 0)、(0, 1)、(0, 2)、(0, 3) (0, 1)、(0, 2)、(0, 3)
1 (1, 1)、(1, 2)、(1, 3) (1, 2)、(1, 3)
2 (2, 2)、(2, 3) (2, 3)
3 (3, 3) なし

前者は4、3、2、1組の合計10組、後者は3、2、1、0組の合計6組です。前者にだけあるのは(0, 0)、(1, 1)、(2, 2)、(3, 3)の4組です。たとえば(1, 3)はどちらにもあります。後者で開始を1進めても、1より大きい候補は引き続き最後の3まで選ばれるからです。

異なるカード2枚の組を作る目的なら、後者の6組を元のカードに戻して確認します。各組の番号は異なり、どちらを先に見るかだけが逆の重複もありません。前者には各カード自身との組が含まれるため、その目的では失敗です。逆に自己の組も必要な目的なら、後者は4組を落とします。正しさは行数だけでなく、何を一覧に入れるかによって決まります。

発展例題:番号が0個や1個のとき

自作の札の個数nを0、次に1とします。基本例の開始iと、そこだけをi+1に変えた処理について、それぞれ出力の組と個数を答えてください。nは0以上の整数で、番号は0からn-1です。

nが0なら外側のrange(0, 0)に候補がないため、両方とも表示なし、0組です。存在しない札の自己の組を作ることもありません。nが1なら外側のiは0だけです。開始iではjが0で(0, 0)を表示し1組、開始i+1では開始1が上端1と一致して表示なし、0組です。

この結果は「いつでも両方の出力は同じ」という主張をnが1のときに反証します。一方、nが0では両方同じなので、その入力だけでは違いを示せません。空の場合の一致を根拠に、一般にも同じと決めないことが必要です。

一般のnでも、各行の開始iの版はjがiからn-1まで、開始i+1の版はjがi+1からn-1までです。後者が空の最後の行でも、前者には(i, i)があります。各行で増えるのは(i, i)の1組なので、増分は行数のn組です。nが0なら行自体がなく、増分も0です。式だけでなく各行の候補を比べると、なぜその差になるかを説明できます。

誤答から最初のずれを直す

異なる番号の組を求める問題で、開始をiにしたまま「自己の組は出ない」と答える誤りを考えます。1個の番号0だけで調べると、最初の外側の回はiが0、内側はjが0から始まります。最初の表示は(0, 0)です。目的の一覧は空なので、この最初の表示ですでに食い違います。

図3のように、開始値を1進めれば最初の候補は上端に達し、表示はありません。処理が止まったことと、目的の一覧が空であることが一致します。

図3 1個の番号で自己の組が生じる誤りと修正
観点 開始i 開始i+1
最初のi 0 0
jの開始 0 1
上端1との関係 0は1未満 1は1未満でない
表示 (0, 0) なし
異なる番号の組という目的 失敗 一致

原因は、内側の開始が「次の番号」だと思い込み、代入される実際の値を確かめなかったことです。修正は内側をrange(i+1, n)にすることです。上端や外側を同時に変える必要はありません。複数の場所を一度に変更すると、どの変更が差を生んだかが見えにくくなります。

逆に、自己の組も必要な問題でi+1を使う失敗もあります。1個の入力なら本来の(0, 0)が欠けます。目的に戻して欠落を調べると、余分な組を探すだけでは見逃す誤りも見つかります。空の入力では両版とも正常に終了して出力がないため、空だけの確認ではこの欠落を検出できません。

練習:組の境界を確かめる

各問は自作条件です。番号は0から始まり、n個ならn-1までです。基本例の外側と上端を使い、指定された内側の開始値で表示します。答えは指定された組または整数で書いてください。

  1. 作品札が5枚です。開始をi+1とすると、iが2の行に表示する組を順に答えてください。
  2. 記号板が6枚です。開始をiとすると、iが5の行に表示する組とその個数を答えてください。
  3. 道具札が7枚です。開始をiとした一覧で、開始i+1の一覧にはない組をすべて答えてください。
  4. 説明札が8枚です。開始i+1の一覧に(6, 6)と(6, 7)がそれぞれ含まれるか答え、理由を述べてください。
  5. 模様札が9枚です。開始i+1の一覧の組数と、開始iの一覧との差を整数で答えてください。

練習の答えと途中経過

  1. iが2ならjは3から始まり、上端5の手前の4までです。(2, 3)、(2, 4)の順です。どちらも別の札を指し、番号を逆にした組は同じ行にはありません。開始を2と誤読すると余分な(2, 2)が先頭に入ります。

  2. iは5、jも5から始まり、次の6は上端なので含みません。(5, 5)の1組です。開始をi+1にした場合は開始6が上端と一致し、0組です。最後の行も必ず複数回動くと考えると、この終了を見落とします。

  3. 各行のjの最初だけが違うため、(0, 0)、(1, 1)、(2, 2)、(3, 3)、(4, 4)、(5, 5)、(6, 6)です。計7組で、いずれも実在する番号同士です。他の組はjがiより大きく、両方の開始位置から到達できます。

  4. iが6の行の開始は7で、上端8は含みません。(6, 6)は含まれず、(6, 7)は含まれます。番号6の札と番号7の札を使う後者は、異なる2枚という目的に合います。等号を含む範囲と読み違えると、前者もあると誤答します。

  5. 各行の組数は順に8、7、6、5、4、3、2、1、0です。合計36組です。開始iの版では各行に自己の組が1つ加わるため、差は9組です。36組のそれぞれは異なる2枚の組であり、同じ札の組を追加した45組とは目的が異なります。差だけでなく各行の数を足して、最後の0回も確かめます。

要点

内側がiから始まると自己の組を含みます。 i+1から始まると、同じ行ではそれより大きい番号を選びます。 上端は含まず、開始が上端なら内側は0回です。 差は各行の自己の組で、n個の番号ならn組です。

追跡表のどこを見るか

同じ番号が混ざる理由を説明できないときは、各行の「i」と「jの開始」の列を比べます。開始をi+1と書けていても、その下にiをそのまま写していれば、式の評価時点でずれています。個別指導では、最初の表示の直前までを本人に書いてもらい、どの値を選んだかを確認します。

最後の行の回数が合わないときは、開始と上端の列を見ます。両者が等しいのに1回表示していれば、上端を含まない規則の読み違いです。1個と0個の入力で、余分な自己の組と必要な組の欠落の両方を調べると、目的と出力の対応まで確かめられます。

組を数える際は、表示された順と集合としての内容を区別します。開始値の変更では各行の自己の組が消えますが、残った組の相対的な順序は変わりません。外側が小さい番号から進み、各行でも内側が小さい番号から進むためです。逆順の組を別に求める条件なら、この一覧だけでは不足します。その場合は目的を読み直す必要があり、開始値の変更だけで逆順の組まで得られるわけではありません。

また、同じ内容の札が複数あっても番号が違えば、この処理では異なる番号の組です。反対に、同じ番号を2回使った組は、札に書かれた内容を確認しなくても自己の組です。問題が比較しているのが番号なのか内容なのかを取り違えず、今回の追跡では番号を基準にします。

もう「日東駒専」を目標にしないでください。

武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。

まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。

本気になった日が、入塾の日。

お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。

電話は年中無休。365日、24時間、お電話可能。

チャットで質問チャット
無料相談を予約する 電話 0422-27-7828電話 LINE チャット
で質問