
武蔵野個別指導塾の特徴
共通テスト情報I 探索の発見フラグ—後の不一致で見つかった記録を消す誤りを直す|武蔵野個別指導塾

途中で一致した記号の後に不一致が続いても保持する記録が発見フラグです。
よくあるのは、高校生が記号列の途中で目当ての記号を見つけたのに、末尾が違うという理由で未発見とする場面です。列の最後を調べた結果と、列全体に目当てがあったかという結果は同じとは限りません。途中の一致を覚える変数が、後の不一致でどう変わるかを追います。
以下の列と番号はすべて説明のための自作条件です。整数を記号の種類を表す番号とし、探す番号と同じなら一致とします。発見の有無を扱い、位置を答える探索は扱いません。
要点(結論から)
- found は今回の一致ではなく、調べた範囲に一致があったかを表します。
- 初期値は False、一致時は True、不一致時は値を保持します。
- 一致の後に不一致が来る2要素の列で、発見を消す誤りを反証できます。
どんな形で問われるか
1つ目は、与えられた列に対する最後の真偽値を答える形です。各回で比較する番号と、比較後のフラグを別々に書きます。列の最後の番号と一致するかだけでなく、その前に何が起きたかを残す必要があります。
2つ目は、処理の目的に合わない短い入力を探す形です。「どこかにあるなら発見」という目的に対し、途中で一致してから不一致になる列を試すと、記録が消える処理を見分けられます。短い例であっても、空の列や1要素で誤りが出るかを先に考えると、最小である理由まで説明できます。
3つ目は、不一致のときの代入を変えて処理を修正する形です。修正前後の結果が同じ入力もあります。どの入力でも同じだと決める前に、一致の後に不一致を置いて比較します。いずれの形でも、出力が反復の途中なのか、列を調べ終えた後なのかを確認します。
発見済みは何を覚えるか
フラグは、ある状態を真偽値で記録する変数です。ここでの found は「これまでに調べた範囲に、探す番号が少なくとも1つある」という意味にします。True は発見済み、False はまだ発見していない状態です。反復の前はまだ何も調べていないので False にします。
図1のように、一致すると True に変えます。不一致では、今回の番号は違うとわかりますが、以前に見つけた事実は消えません。したがって found を変更せず、元の値を持ち越します。すでに True の状態で再び一致しても True のままです。

図1の左側は一致がない間、右側は一度でも一致した後を表します。右側から不一致で左側へ戻すと、以前の一致が失われます。このフラグが表すのは現在の要素の一致ではなく、処理済みの範囲全体についての結果です。
例えば処理済みの範囲を先頭から順に広げると、各回の後に「その範囲に対象がある」と found の値が一致します。初期状態では範囲が空で、対象はありません。次の要素が一致なら対象がある状態になり、不一致なら範囲に対象があったかどうかはそれまでと変わりません。この説明は各回で繰り返せるので、最後まで調べた後も列全体に対する答えが残ります。
空の列では比較が1回も行われず、初期値の False がそのまま答えです。1要素の列では、その1要素が一致なら True、不一致なら False です。重複していても、発見の有無だけを尋ねるなら一致の回数は答えに影響しません。
基本例題:見つけた後に違う番号が来る
記号番号の列を [4, 7, 4, 2]、探す番号を 4 とします。次の処理は先頭から末尾まで調べ、終了後に発見の有無を出力します。添字は0から始まり、有効な添字は0から3までです。各回の表には、その要素の比較と代入を終えた直後の値を記入します。出力される真偽値を答えてください。
items = [4, 7, 4, 2]
target = 4
found = False
i = 0
while i < len(items):
if items[i] == target:
found = True
i = i + 1
print(found)
items は記号番号の列、target は探す番号、i は今から調べる添字です。len(items) は要素数です。条件 i < len(items) は末尾の添字3を含み、その次の4は含みません。found は各回の比較の前から保持されます。
| 時点 | i | 調べる番号 | 一致 | 比較後の found | 更新後の i |
|---|---|---|---|---|---|
| 反復前 | 0 | まだない | まだない | False | 0 |
| 1回目 | 0 | 4 | 真 | True | 1 |
| 2回目 | 1 | 7 | 偽 | True | 2 |
| 3回目 | 2 | 4 | 真 | True | 3 |
| 4回目 | 3 | 2 | 偽 | True | 4 |
初回の条件は 0 < 4 で真です。添字0の番号4が一致し、found に True を入れた後、i を1にします。2回目は 1 < 4 が真で、番号7は不一致です。代入は行わないため found は True のまま、i は2になります。
3回目の番号4も一致するので、True を再び代入します。4回目の番号2は不一致ですが、そこでも found は変わりません。i が4になった後の条件 4 < 4 は偽です。反復を終えてから True を1回出力します。

図2のように、最後の番号2が不一致でも、先頭と3番目に番号4があります。出力 True は記号列に戻しても目的に合います。2回目と4回目の True は、その回の一致を表しているのではなく、そこまでの発見を表しています。
標準例題:末尾だけで判断できるか
列を [8, 3, 5]、探す番号を 5 とします。基本例題の処理で、各回の比較後の found と、終了後の出力を答えてください。添字は0から2で、出力は反復後です。
最初の8と次の3は不一致なので、found は順に False、False です。最後の5で一致し、True になります。終了後の出力は True です。列に戻ると、末尾に番号5があるので発見という答えは目的に合います。
この入力では、不一致のたびに False を代入する誤った処理でも、最後の一致で True になります。正しい出力が1回得られたことだけでは、途中の発見を保持できると証明できません。末尾の5と先頭の8を入れ替えて [5, 3, 8] とすると、一致の後に不一致が続きます。正しい処理では True が残りますが、不一致で消す処理は False を出力します。
発展例題:初期化する場所が変わるとどうなるか
列を [6, 1, 9]、探す番号を 1 とします。基本例題の処理で found = False を反復の前から取り除き、代わりに if の直前、つまり各回の本体の先頭に置きます。列は空でないものとして、各回の本体末尾の found と出力を答えてください。
添字0では最初に False が入ってから6を比較し、不一致なので False です。添字1では再び False にしてから1を調べ、一致によって True です。添字2では比較の前に False へ戻り、9は不一致なので False です。反復後の出力は False となります。列の中央に1があるため、列全体については誤った答えです。
この変更は else で不一致時に戻す処理とは文の位置が違いますが、各回の開始時に過去の記録を捨てる点で同じ問題を生みます。さらに、空の列では本体が1回も動かないので、そのまま print(found) を実行すると、この独立したプログラムでは found が定義されておらず NameError になります。空の場合を未発見と返すには、反復の前に初期化する必要があります。
1つの変数をいつ初期化するかは、その変数がどの範囲の情報を持つかに関わります。各要素の一致だけを表す変数なら毎回作り直せますが、列全体の発見を表す変数なら、次の要素を調べても前の値が必要です。位置を保存する変数ではなく、真偽値の意味を先に定めてから代入箇所を読みます。
誤答を反例から直す
次は一致なら True、不一致なら False を代入する誤った処理です。基本例題の if 部分にある代入の後ろへ、次の else を加えたものとします。
else:
found = False
各回に現在の一致結果を found へ書くので、空でない列では最後の要素の一致結果が残ります。目的の「列中のどこかにある」とは異なります。列 [4, 2]、対象 4 で比べてみます。どちらも反復前は False で、先頭から順に全要素を調べ、最後に出力します。
| 比較した番号 | 目的に合う処理 | 誤った処理 |
|---|---|---|
| 4 | True | True |
| 2 | True | False |
最初の食い違いは番号2を調べた直後です。誤った処理は2が不一致である事実を、4を見つけた記録への否定と取り違えています。図3のように、不一致時には代入を行わないよう修正します。修正後の True は、実際に先頭の4に対応します。

図3の上段と下段は、同じ2要素に対する比較後の値です。空の列なら両方とも初期値 False で、1要素ならその要素の一致結果が列全体の答えになります。そのため、発見を消す誤りを出すには少なくとも2要素が必要です。先頭が一致し、次が不一致のこの列は、その条件を満たす最小の反例です。
誤った処理がいつも間違うわけではありません。全要素が不一致なら両方とも False、最後が一致なら両方とも True です。違いが出るのは、最後が不一致で、その前に一致がある場合です。見つけた後に処理を続ける設計では、不一致の操作が過去を消さないことを点検します。
練習:列ごとに出力を判定する
各問は自作の記号番号の列です。添字は0から始まり、左から右へ全要素を調べ、終了後に真偽値を1回出力します。断りがない限り基本例題の正しい処理を使います。空の列では found の初期値を出力します。
- 列
[11, 12, 13]から番号12を探します。各回の比較後のfoundと出力を答えてください。 - 列
[14, 15, 16]から番号17を探します。各回の比較後のfoundと出力を答えてください。 - 空の列
[]と1要素の列[18]から、それぞれ番号18を探します。2つの出力を順に答えてください。 - 列
[21, 22, 21, 23]から番号21を探します。不一致でFalseに戻す誤った処理と正しい処理の各回の値と出力を、それぞれ答えてください。 - 番号24を探すとき、列
[25, 24, 26]に対して誤った処理が出す値と、食い違いが初めて起きる添字を答えてください。正しい出力も答えてください。
練習の答えとたどり方
-
比較後は
False, True, True、出力はTrueです。11は不一致、12が一致、13は不一致ですが、12を見つけた状態を持ち越します。列の添字1に実際に12があるので発見です。 -
比較後は
False, False, False、出力はFalseです。14、15、16を順に確認すると、どれも17ではありません。初期値は一度も変わらず、未発見が列全体と一致します。 -
空の列の出力は
False、[18]の出力はTrueです。空では条件が初回から偽で、比較する要素がありません。1要素の列では添字0が18なので、一致後の値がそのまま出力されます。 -
誤った処理は
True, False, True, Falseと変化し、出力はFalseです。正しい処理はTrue, True, True, Trueで、出力はTrueです。添字0と2に21があるので、発見という後者が目的に合います。2回目の22で誤った処理が初めて記録を消し、次の一致で一度回復しても末尾の23でまた消します。 -
誤った処理の出力は
False、正しい出力はTrueです。最初の25では両方False、次の24では両方Trueです。添字2の26が不一致となった直後に初めて値が分かれます。添字1に24があるので、正しい出力は列の条件を満たします。
要点
foundは今回の一致ではなく、調べた範囲に一致があったかを表します。- 初期値は
False、一致時はTrue、不一致時は値を保持します。 - 一致の後に不一致が来る2要素の列で、発見を消す誤りを反証できます。
- 出力の時点と、空の列で反復が動かないことも確認します。
どの列を見ればつまずきが見えるか
追跡表で比較の真偽は正しいのに found が不一致のたびに False になるなら、現在の比較と発見済みの意味を混同しています。一致後の不一致の行に注目し、その行の前に見つけた番号が列のどこにあるかを示してから、代入文の有無を確かめます。
個別指導で確認する箇所は、初期値、各比較後のフラグ、反復後の出力の3か所です。空の列で初期値が残るか、末尾で初めて一致する列だけで判断していないかも、本人の表と実行順を照らして点検します。発見の記録は、次の不一致を通過して初めてその役割を果たします。
もう「日東駒専」を目標にしないでください。
武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。
まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。
本気になった日が、入塾の日。
お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。
電話は年中無休。365日、24時間、お電話可能。



