体系ガイド · 入門

数学的帰納法とループ不変条件:繰り返しの正しさを説明する

初期化・維持・終了の三段階で、配列の合計を求めるループの正しさを確かめます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 例が増えても証明にはならない
  2. 配列の合計で不変条件を作る
  3. 終了条件を目的へつなぐ
  4. 実装の前提も確かめる
  5. 空の入力で初期化を確かめる
  6. この記事をロゲイアに質問する理解を確かめる

例が増えても証明にはならない

最初の何回かで正しい結果になったことと、任意の長さで正しいことは別です。数学的帰納法では最初の場合を示し、ある段階で成り立つと仮定した性質が次の段階へ引き継がれることを示します。計算機のループでも同じ考え方を使えます。何が毎回成り立つのかを、実装の動きを言い換えるだけでなく目的に結び付けて定めます。

配列の合計で不変条件を作る

長さnの配列で、iを次に読む添字、totalを処理済み要素の合計とします。不変条件は「0以上i未満の要素の合計がtotalである」と書けます。最初はi=0なので処理済み要素はなく、total=0と一致します。次の要素a[i]をtotalへ足してiを一つ進めると、新たに処理済みになった範囲の合計と一致し、条件が維持されます。

python
values = [2, 4, 6]
total = 0
for i in range(len(values)):
    # Before this addition, total == sum(values[:i]).
    total += values[i]

終了条件を目的へつなぐ

ループがi=nで終了すると、不変条件によりtotalは配列全体の合計です。ただし「終了したら正しい」という部分正当性だけでは、実際に終了することは示せません。この例では未処理要素数n-iが各反復で一つ減り、負にはならないので終了します。無限ループの可能性がある処理では、こうした減少する量も別に考えます。

実装の前提も確かめる

数学上の整数は無限の大きさを扱えますが、固定幅の整数型では合計が範囲を超える場合があります。配列が別スレッドに書き換えられる場合も、不変条件の前提が崩れます。証明では入力の条件、数値のモデル、変更される状態の範囲を明記します。テストはその前提が実装で守られているかを調べる助けになりますが、証明と同じ役割ではありません。

空の入力で初期化を確かめる

空配列の場合、反復は一度も行われません。それでも初期値0が正しい結果になることを、不変条件と終了条件から説明できます。空入力だけを後から特別扱いする必要はありません。初期化の時点で条件を満たすよう設計すると、通常の場合と境界の場合を同じ論理で扱えます。別の初期値を選んだとき、どの説明が崩れるかも確かめてみましょう。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 14

学習コースから次を選ぶ