読書メモ:プログラマの数学(4)

数学的帰納法

ある主張が成り立つことを0以上のすべての整数について証明する方法。
数学的帰納法は2つのステップで行う

  1. P(0)が成り立つ ことを証明する(基底)
  2. 0以上のどんな整数kを選んでも、P(k)が成り立つならばP(k+1)も成り立つことを証明する(帰納

ドミノだおしに例えると

  1. 最初のドミノが倒れることを保証する
  2. k番目のドミノが倒れたならばk+1番目のドミノも倒れることを保証する

プログラムで書くと

prove(3);
function prove(n){
    console.log(`いまからP(${n})が成り立つことを証明します`);
    let k = 0;
    console.log(`ステップ1により、P(${n})が成り立ちます`);
    while(k < n){
        console.log(`ステップ2によりP(${n})が成り立つならP(${n+1})も成り立つと言えます`);
        console.log(`従って、P(${n+1})が成り立つといえます`);
        k++;
    }
    console.log(`証明終わり`);
}

印象的だったのは、著者が昔、数学的帰納法がわからなかったというエピソードのところで
「p(k)はいまから証明しようとしている式なのに、それを仮定してしまったら証明にならないはずだ」←そうだった、わたしもそう思ったことある、わかる!
「いま思えばproveの引数n(目標にしている数)とproveのローカル変数kを混同してしたのですね」←ほんとだ〜〜!
という感じで、10年越しくらいにもやっとしていたことがわかってすっきりした〜 プログラムがちょっとでもかけるようになってよかったなぁ

ループ不変条件

ループを構成するときにはループの各回で成り立っている論理式をみつけることが重要! この論理式のことを「ループ不変条件」という。 ループを作るときにはこのループの不変条件はなにか?を考えて作ると誤りが少なくなる

プログラマの数学

プログラマの数学