数学的帰納法
ある主張が成り立つことを0以上のすべての整数について証明する方法。
数学的帰納法は2つのステップで行う
- P(0)が成り立つ ことを証明する(基底)
- 0以上のどんな整数kを選んでも、P(k)が成り立つならばP(k+1)も成り立つことを証明する(帰納)
ドミノだおしに例えると
- 最初のドミノが倒れることを保証する
- 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年越しくらいにもやっとしていたことがわかってすっきりした〜 プログラムがちょっとでもかけるようになってよかったなぁ
ループ不変条件
ループを構成するときにはループの各回で成り立っている論理式をみつけることが重要! この論理式のことを「ループ不変条件」という。 ループを作るときにはこのループの不変条件はなにか?を考えて作ると誤りが少なくなる
- 作者: 結城浩
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2005/03/24
- メディア: 大型本
- 購入: 41人 クリック: 707回
- この商品を含むブログ (396件) を見る