コンテンツへスキップ
Topos Uranos
日本語

問題からアルゴリズムへ

要約

この回にはコードがないが、それは手落ちではない。アルゴリズムはプログラムに先立つものであり、何をすべきかを正確に記述できない人は、それを C++ で言い表すこともできない。まず問題の仕様を定めること、つまり、どんなデータを受け取り、どんな結果を出さなければならず、両者をどんな関係が結ぶのかを宣言することを学び、同じ問題文が異なる仕様を許すことを示す。次にアルゴリズムを、有限で、明確で、一般的な手続きとして定義し、引き算の繰り返しによる割り算のアルゴリズムを番号付きの手順で書く。トレース表を使ってアルゴリズムを手で追うことを学ぶが、これはコース全体を通じて、理解するためにもデバッグするためにも第一の道具となる。手順を組み合わせる三つの方法（順次、分岐、反復）を紹介し、あらゆるアルゴリズムはこれらで書かれることを述べ、各周回で減少し、しかも際限なく下がり続けることのできない量によって、反復が停止することを示す方法を学ぶ。

学習目標

  1. 簡単な問題について、入力、出力、およびそれらが満たすべき条件を示して仕様を定める。
  2. アルゴリズムを、あいまいさなく、分岐と反復を明示して、番号付きの手順で記述する。
  3. トレース表を使ってアルゴリズムを手で追い、与えられた入力に対する結果を求める。
  4. 与えられた手続きのなかで順次、分岐、反復を見分け、反復が停止することを示す。

計算問題とは何か

計算問題とは、二種類のデータのあいだの関係である。一方は受け取るデータで、入力と呼ばれ、他方は出さなければならないデータで、出力と呼ばれる。これを解くとは、ある一つの場合に答えを得ることではなく、許されるすべての入力に対して、その関係を満たす出力を生み出す方法を手にすることである。「17 を 5 で割るといくつか」は質問である。「二つの整数が与えられたとき、その商と余りを求めよ」は問題である。整数のすべての組について同時に語っているからである。

ところが日常の言葉は不正確で、同じ問題文がいくつもの意味に取れる。そこで、解く前に仕様を定める。何が入り、何が出て、それぞれがどんな条件を満たさなければならないかを書くのである。仕様は三つの部分からなる。入力は、データをその種類（整数、小数、単語）とともに挙げ、それらに課される条件を挙げる。この条件を事前条件という。解を使う人は、それを守ることを約束する。出力は結果を挙げる。関係、すなわち事後条件は、出力が入力に対して何を満たさなければならないかを述べる。解を書く人は、事前条件が守られている限り、それを保証することを約束する。このことから、仕様は問題を出す人と解く人とのあいだの契約であり、事前条件の外では解は何も約束しないことがわかる。

例三つの数の最大値

日常の問題文：「三つの数のうち最大のものを見つける」。仕様：

  • 入力：三つの数 xx、yy、zz（整数でも小数でもよく、ほかの条件はない）。
  • 出力：一つの数 mm。
  • 関係：mm は三つのデータの一つであり、そのどれも mm より大きくない。つまり m≥xm \geq x、m≥ym \geq y、m≥zm \geq z である。

関係は「三つのうち最大のもの」とは言っていない。それこそ明確にしたかったことだからである。代わりに確かめられる二つの条件を与えている。一つ目は mm がデータの一つであることを求め（これがなければ、数 1000 はほとんどどんな入力に対しても二つ目を満たしてしまう）、二つ目はどのデータもそれを超えないことを求める。さらに仕様は、問題文が残していた疑問をついでに解決する。二つのデータが最大値で並ぶとき、たとえば (4,9,9)(4, 9, 9) では、出力は 99 であり、そこには何の誤りもない。

同じ問題文が異なる仕様を許し、そのどれを選ぶかは決定であって、手落ちではない。最も教訓的なのは整数の割り算の場合である。整数 a≥0a \geq 0 と b>0b > 0 については、誰の意見も一致する。商 qq と余り rr は、次を満たす唯一の整数である。

a=b⋅q+r,0≤r<ba = b \cdot q + r, \quad 0 \leq r < b

たとえば a=17a = 17、b=5b = 5 のとき、q=3q = 3、r=2r = 2 である。17=5⋅3+217 = 5 \cdot 3 + 2 だからである。しかし「二つの整数を割る」という問題文は、aa が負のときどうするかを言っておらず、この問いは無益ではない。a=−7a = -7、b=2b = 2 のとき、もっともな答えが二つあるのである。

例被除数が負のときの割り算の二つの仕様

第一の仕様：余りは決して負にならない、0≤r<b0 \leq r < b。すると −7=2⋅(−4)+1-7 = 2 \cdot (-4) + 1 であり、出力は q=−4q = -4、r=1r = 1 となる。これは数学で学ぶもので、コース「代数と幾何 I」の回「整除と余りのある割り算」で扱われている。

第二の仕様：商は小数を使った割り算の結果から小数部分を捨てたもの、つまり零の方向に丸めたものとし、余りは足りない分で、被除数と同じ符号をもつ。すると −7/2=−3.5-7 / 2 = -3.5 は −3-3 に切り捨てられ、−7=2⋅(−3)+(−1)-7 = 2 \cdot (-3) + (-1) である。出力は q=−3q = -3、r=−1r = -1 となる。

どちらも a=b⋅q+ra = b \cdot q + r を満たし、違いは余りに課す条件にある。どちらも誤りではないが、一方を使いながら他方を使っていると思い込んだプログラムは、負の数で誤った結果を出す。一つ先回りしておこう。C++ が採用しているのは第二のものであり、それは回算術演算で見る。第一のものを期待する人は驚くことになる。

第三の選択肢もあり、実際にはそれがいちばん多い。事前条件によってその場合を除外するのである。仕様が a≥0a \geq 0 を求めるなら、負の数の問題は消える。解決されたからではなく、解を使う人がそれを持ち出さないと約束したからである。してはならないのは、問題を決めないまま放っておくことである。同じ理由で仕様は b>0b > 0 を求める。b=0b = 0 のとき、関係を満たす qq と rr は存在せず、契約はそのことを述べなければならない。

よくある誤りは、例で仕様を定めることである。「17 と 5 に対する出力は 3 と 2」。例は説明にはなるが、仕様にはならない。ほかの入力で何が起きるかを言っていないからである。無数の異なる関係が、一つの場合では一致する。仕様は一般的な条件として書き、例はその後でそれを確かめるために使う。

アルゴリズム

問題の仕様が定まったら、それを解く方法を探す。アルゴリズムとは、事前条件を満たすどんな入力に適用しても、有限回の手順で事後条件を満たす出力を生み出す命令の列である。この定義は三つの要件を含んでいる。

  • 有限性。アルゴリズムは有限個の命令で書かれ、許されるどの入力に対しても、そのうち有限個を実行した後に停止する。ある入力に対していつまでも続く手続きは、その入力に対してはアルゴリズムではない。
  • 明確性。どの命令もただ一つの意味をもち、それを実行する人は、いつでも何をすべきか、次の命令はどれかを知っている。どんな判断も実行する人の裁量に任されない。
  • 一般性。アルゴリズムは、一つの場合だけでなく、許されるすべての入力に対して問題を解く。

いくらか自由な言い方として、明確で停止するが、許されるある入力に対して事後条件を満たさない手続きもアルゴリズムと呼ぶ。厳密には別の問題に対するアルゴリズムであり、仕様を定めた問題に対しては正しくないと言うことにする。この回の問題では、この言い方で、正しくないアルゴリズムを反例によって反駁する。

料理のレシピはアルゴリズムに似ており、そのためよく引き合いに出される。しかし、ほとんどのレシピはアルゴリズムではない。「塩をひとつまみ加える」は明確でない。ひとつまみは量ではないからである。「きつね色になるまで焼く」は、二人の人が別々に下すであろう判断に左右される。「何回か泡立てる」は何回かを言っていない。料理人はこうした隙間を経験で埋めるが、コンピュータには経験がまったくない。このことから、コース全体を支配する要件が導かれる。アルゴリズムは、問題を理解していない人でも、何も推測せずにたどれるものでなければならない。ある手順を実行するのに、それが何のためにあるかを知る必要があるなら、その手順は書き方が悪い。

このコースのアルゴリズムは、まず番号付きの手順で、日本語で、いくつかの約束に従って書く。アルゴリズムの実行中に変わるデータには、qq や rr のように文字や語で名前をつけ、それを変数と呼ぶ。「rr の値を r−br - b にする」と書いて、r−br - b を rr の現在の値で計算し、その結果を rr の新しい値にすることを表す。前の値は失われる。メモをとるときに使う略記では、同じ命令を左向きの矢印で書き、キーボードでは r <- r - b となる。命令は番号の順に実行する。ただし、ある命令が別のことを指示する場合を除く。

例引き算の繰り返しによる割り算

問題は前の節で仕様を定めたものである。入力は二つの整数 a≥0a \geq 0 と b>0b > 0、出力は二つの整数 qq と rr で、a=b⋅q+ra = b \cdot q + r かつ 0≤r<b0 \leq r < b を満たす。考え方は配ることである。aa から、できる限り bb ずつのまとまりを取り去り、取り去ったまとまりを数え、残ったものが余りである。

  1. qq の値を 00 にし、rr の値を aa にする。
  2. r≥br \geq b が成り立つ間、手順 3 と 4 を繰り返す。成り立たなくなったら手順 5 に進む。
  3. rr の値を r−br - b にする。
  4. qq の値を q+1q + 1 にする。手順 2 に戻る。
  5. qq と rr を出力し、終了する。

手順 2 は毎回なされる問いである。最初の周回の前と、各周回の後に問う。手順 3 と 4 は反復の本体、つまり繰り返される部分をなす。実行する人の裁量に任されるものは何もない。どの時点でも、次の命令はただ一つである。

このアルゴリズムは遅く（百万を三で割るのに三十万周以上かかる）、学校で習う割り算の方法のほうがはるかに速い。しかし正しく、その単純さのおかげで、アルゴリズムについて推論することを学ぶには理想的である。正しいアルゴリズムと効率のよいアルゴリズムの違いには、コースは回アルゴリズムのコストで立ち戻る。

最後に、アルゴリズムをその書き表し方から切り離しておくのがよい。引き算による割り算のアルゴリズムは、日本語で書いても、図で書いても、C++ やほかのどんなプログラミング言語で書いても、同じものである。それを定めるのは演算の列であって、言葉ではない。プログラムとは、機械が実行できる言語でアルゴリズムを書き表したものであり、その実行がどのように起きるかは回プログラム・コンパイラ・C++で説明する。そうであれば、プログラムはまったく異なる二通りの仕方で誤りうる。アルゴリズムが正しくない場合で、このときはどんな言語も救いにならない。あるいはアルゴリズムは正しいが書き方を誤った場合である。この二つを見分けることはデバッグの仕事の半分であり、だからこのコースでは常にまずアルゴリズムを書く。

アルゴリズムを手で追う

アルゴリズムを読むだけでは、それが何をするかを知るには足りない。実行しなければならない。機械がするように、手順を飛ばさず結果を推測もせずに手で追うことは、プログラムを書く人にとって最も役に立つ技能である。これによって、アルゴリズムを書く前にそれを確かめ、プログラムを実行する前にその出力を予測し、うまく動かないプログラムの誤りを見つける。

そのための道具がトレース表である。実行する手順の番号の列、変数ごとの列、必要なら判定する条件の列を設け、実行した手順ごとに一行をとる。各行には、その手順で変わった変数の新しい値を書き、変わらなかったものは空欄にする。こうすれば、ある変数の現在の値は、その列に最後に書かれた値である。条件はその結果とともに書く。

例17 を 5 で割るときのトレース

引き算の繰り返しによる割り算を a=17a = 17、b=5b = 5 で追う。図の矢印は直前に実行した手順を指し、点線は手順 4 が手順 2 に戻ることを示している。

証明

  1. (q,r)=(0,17)(q, r) = (0, 17)

    手順 1：初期値を与える。入力は事前条件を満たす。17≥017 \geq 0 かつ 5>05 > 0 だからである。

  2. (q,r)=(1,12)(q, r) = (1, 12)

    一周目。手順 2 で 17≥517 \geq 5 が確かめられるので、本体を実行する。手順 3 が五のまとまりを一つ取り去り、手順 4 がそれを数える。

  3. (q,r)=(2,7)(q, r) = (2, 7)

    二周目：12≥512 \geq 5 なので、本体をもう一度実行する。

  4. (q,r)=(3,2)(q, r) = (3, 2)

    三周目：7≥57 \geq 5 なので、本体をもう一度実行する。

  5. 17=5⋅3+2,0≤2<517 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5

    手順 2 で条件が成り立たない。2<52 < 5 だからである。アルゴリズムは手順 5 に進み、q=3q = 3 と r=2r = 2 を出力する。出力は事後条件を満たす。

表全体は十二行になる。手順 1、各三行の三つの周回（手順 2、3、4）、成り立たなかった判定、そして出力である。

この表について二つ注意しておく。第一に、周回の数は商 33 に等しく、手順 2 は本体より一回多い 44 回実行された。この形の反復では常にそうなる。最後の判定が成り立たないものだからである。第二に、トレースは、アルゴリズムの文面が一見しただけでは言っていないことを教えてくれる。a<ba < b のとき、たとえば a=3a = 3、b=5b = 5 のとき、条件は最初から成り立たず、本体は一度も実行されず、出力は q=0q = 0、r=3r = 3 となる。これは正しい。3=5⋅0+33 = 5 \cdot 0 + 3 だからである。反復が一度も実行されない場合を忘れることは、アルゴリズムを設計するときに最もよくある誤りの一つであり、小さな入力でのトレースがそれを見つけ出す。

一つの場合のトレースは、アルゴリズムが正しいことを証明しない。一つの場合を確かめるだけである。しかし、よく選んだトレース（ふつうの場合、境界の場合、反復が一度も実行されない場合）は誤りの大部分を見つけ出し、うまくいかないトレースは誤りがどこにあるかを示す。場合から証明へ進む方法は、回正しいループの設計で教える。

順次、分岐、反復

近くから見ると、アルゴリズムはごくわずかな部品で組み立てられている。基本的な命令（変数に値を与える、結果を出力する）と、それらを組み合わせる三つの方法がある。

  • 順次：一つの命令の後に別の命令を、順番に実行する。割り算の手順 3 と 4 は順次である。まず引き、次に数える。
  • 分岐：ある条件が成り立つかどうかに応じて、ある部分か別の部分を（あるいはある部分か何もしないかを）実行する。「y>my > m ならば mm の値を yy にする」は分岐である。
  • 反復：ある条件が成り立つ間、ある部分を何度も実行する。割り算の手順 2 は、その本体とあわせて反復である。

どの形も入口と出口を一つずつだけもち、その内部はまた三つのどれであってもよい。反復の本体は分岐を含むことができ、分岐の枝は反復を含むことができ、以下同様である。そうであれば、三つの形でどんなに複雑なアルゴリズムも組み立てられる。互いにかみ合う少数の部品でどんな建物でも組み立てられるのと同じである。それらであらゆるアルゴリズムを表せるということは、プログラミングの理論でよく知られた結果である（1966 年にコラド・ベームとジュゼッペ・ヤコピーニが証明した）。ここでは証明しないが、コース全体がそれを裏づける。このコースで書くプログラムは、どれほど長くても、この三つの形以外には何も使わない。それらは C++ では、分岐には if、反復には while または for として書かれ、回分岐と回ループで扱う。

アルゴリズムの形を見るのに便利な記法がフローチャートである。命令はそれぞれ長方形、条件はそれぞれ出口を二つもつひし形で表し（成り立つ場合を図では 11、成り立たない場合を 00 と記す）、矢印が次の手順を示す。これは記法であって目的ではない。小さなアルゴリズムを一目で見渡すには役立つが、規模が大きくなると使えず、大きなプログラムを図を描いて書く人はいない。

例三つの形とその組み合わせ

図は三つの形を一般的な命令 AA と BB、条件 cc で描き、それからそれらを組み合わせて、引き算の繰り返しによる割り算の図にする。

証明

  1. A;BA ; B

    順次：AA を実行し、次に BB を実行する。入口も出口も一つだけである。

  2. c=1⇒A,c=0⇒Bc = 1 \Rightarrow A, \quad c = 0 \Rightarrow B

    分岐：cc が成り立てば AA を実行し、そうでなければ BB を実行する。二つの枝は一つの出口で合流する。

  3. c,A,c,A,…,cc, A, c, A, \ldots, c

    反復：cc を判定し、成り立てば AA を実行して再び cc を判定する。成り立たなければ抜ける。条件は本体より一回多く判定される。

  4. a=b⋅q+r,0≤r<ba = b \cdot q + r, \quad 0 \leq r < b

    組み合わせ：引き算の繰り返しによる割り算は順次（初期値、反復、出力）であり、その反復は本体として別の順次（引く、数える）をもつ。

日常の言葉で書かれた手続きのなかで三つの形を見分けることは、それをプログラムに翻訳する第一歩である。分岐のしるしは「もし」「…の場合は」「…に応じて」であり、反復のしるしは「…の間」「…まで」「それぞれの…について」「…の回数だけ」である。こうした言葉が一つもない手続きは順次であり、大きさの変わる入力（数のリスト、文章）を扱わなければならないのなら、反復が欠けている。

停止するか

有限性はアルゴリズムの定義の一部であり、それが失われうる場所は反復だけである。五つの手順からなる順次は五つの手順を実行し、分岐はその枝の一つを実行する。しかし反復は、条件が成り立つ回数だけ本体を実行し、条件がいつか成り立たなくなることを前もって保証するものは何もない。

反復が停止することを示すには、変数から計算される量で、二つの条件を満たすものを探す。反復が続く間は自然数（負でない整数）であること、そして各周回で狭義に減少することである。そうであれば、反復は停止する。自然数の狭義減少列は無限には続かない。各周回で少なくとも一は下がり、自然数 nn から零までには nn 段より多くの段はないからである。この量を変量または限界関数と呼び、回正しいループの設計でこれを系統的に使う。

例引き算による割り算の変量

引き算の繰り返しによる割り算では、変量は rr である。反復が続く間 r≥b>0r \geq b > 0 であるから、rr は自然数である。各周回で rr の値は r−br - b になり、b>0b > 0（事前条件）なので、新しい値は真に小さい。したがって反復は停止し、しかも高々 aa 周の後に停止する（実際には、ちょうど qq 周、つまり商の回数の後に停止する）。

事前条件 b>0b > 0 がどこで使われたかに注意しよう。b=0b = 0 でアルゴリズムを実行すると、手順 3 は rr を変えず、条件 r≥0r \geq 0 は常に成り立ち、反復は決して停止しない。アルゴリズムが誤っているのではなく、契約が除外していた入力を与えられたのである。また bb が負であれば、rr は周回ごとに増えていく。事前条件は飾りではない。推論が成り立つためにちょうど必要なものである。

変量の二つの条件はどちらも必要であり、どちらについても誤りやすい。自然数 nn が偶数かどうかを判定しようとする次の手続きを考えよう。「n≠0n \neq 0 である間、nn の値を n−2n - 2 にする。零に達したら、nn は偶数だった」。量 nn は各周回で減るが、それでも nn が奇数なら手続きは停止しない。n=5n = 5 のとき 33、11、−1-1、−3-3 を通り、条件 n≠0n \neq 0 は決して成り立たなくならない。満たされていないのはもう一方の条件である。nn は自然数でなくなる。反復の条件が、零より下がるのを妨げないからである。修正は、n≥2n \geq 2 である間繰り返し、最後に残った値 00 か 11 によって判定することである。こうすれば nn は各周回で自然数である。n≥2n \geq 2 のときにしか引かないからである。しかも減少する。手続きは停止する。

反復が停止するかどうかを判定するのは、いつも易しいとは限らない。有名な例がある。自然数 n≥1n \geq 1 から始めて、n≠1n \neq 1 である間、nn が偶数なら二で割り、奇数なら 3n+13n + 1 で置き換える。n=6n = 6 のとき列は 6,3,10,5,16,8,4,2,16, 3, 10, 5, 16, 8, 4, 2, 1 となり、停止する。停止しない nn を見つけた人はおらず、コンピュータで膨大な数の値について確かめられている。しかし、いつも停止することを証明できた人もいない。これがコラッツ予想であり、数学の未解決問題である。各周回で減少する量は一つも知られていない。プログラムを書く人にとっての教訓は控えめで、しかも揺るがない。停止することを示せないアルゴリズムは、まだ完成していない。

よくあるエラー

  • あいまいな手順。「何回か繰り返す」「うまくいくまで」「適当な数をとる」。どの手順も問題を理解しなくても実行できなければならない。そうでなければ書き方が悪い。
  • 反復が一度も実行されない場合を忘れる。条件が先頭にある反復は、どれも本体を零回実行することがありうる。その場合にアルゴリズムが何を出力するかを常に問わなければならず、最小の入力でのトレースがその答えを出す。
  • 例で仕様を定める。「17 と 5 なら 3 と 2 になる」は仕様ではない。関係は一般的な条件として書き、例はそれを説明する。
  • アルゴリズムとそのプログラムを混同する。うまく動かないプログラムは、アルゴリズムが誤っていることも、その書き表し方が誤っていることもある。先にアルゴリズムを書かなかった人は、二つのうちどちらを探せばよいかわからない。
  • 停止を当然とみなす。ある量が減るだけでは足りない。反復が続く間、自然数でもなければならない。

例題

例題 1三つの数の最大値、同点を含めて

最初の節の三つの数の最大値の仕様を満たすアルゴリズムを書き、入力 (7,2,5)(7, 2, 5) と (4,9,9)(4, 9, 9) について手で追え。

解答

  1. m=xm = x

    考え方：入力を順に見ていき、これまでに見た最大のものを変数 mm に保持する。第一の手順：mm の値を xx にする。その後、mm は見たデータの最大値である。見たデータは xx だけである。

  2. m=max⁡(x,y,z)m = \max(x, y, z)

    第二の手順：y>my > m なら mm の値を yy にする。第三の手順：z>mz > m なら mm の値を zz にする。第四の手順：mm を出力する。これは順次に並んだ三つの命令で、そのうち二つは別の枝をもたない分岐である。

  3. (x,y,z)=(7,2,5)⇒m=7(x, y, z) = (7, 2, 5) \Rightarrow m = 7

    (7,2,5)(7, 2, 5) のトレース：第一の手順の後 m=7m = 7。第二の手順では 2>72 > 7 は偽で、mm は変わらない。第三の手順では 5>75 > 7 は偽で、mm は変わらない。77 が出力される。

  4. (x,y,z)=(4,9,9)⇒m=9(x, y, z) = (4, 9, 9) \Rightarrow m = 9

    (4,9,9)(4, 9, 9) のトレース：第一の手順の後 m=4m = 4。第二の手順では 9>49 > 4 なので mm は 99 になる。第三の手順では 9>99 > 9 は偽で、mm は変わらない。99 が出力され、これは正しい。同点は特別な扱いを必要としない。

  5. m≥x,m≥y,m≥zm \geq x, \quad m \geq y, \quad m \geq z

    根拠：各手順の後、mm は見たデータの一つであり、そのどれもそれを超えない。これは第一の手順の後で正しく、どの分岐もそれを保つ。新しいデータのほうが大きければそれが mm となり、そうでなければそれは mm を超えない。最後には三つとも見ており、mm は事後条件を満たす。

  6. (x,y,z)=(4,9,9)⇒p∈{2,3}(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}

    仮に y≥my \geq m と書き、y>my > m としなかったとしても、結果は同じである。同点のときには等しい値を代入するからである。>> と ≥\geq のどちらを選ぶかが問題になるのは、最大値の位置も求められる場合である。>> では同点の位置のうち最初のものが、≥\geq では最後のもの（式ではそれを pp と呼ぶ）が出力される。

例題 2うるう年、反例による修正

グレゴリオ暦では、年は 44 で割り切れるときうるう年である。ただし 100100 で割り切れる年は除き、それらはさらに 400400 でも割り切れるときに限りうるう年である。ある学生がアルゴリズム「年が 44 で割り切れるならはいを出力し、そうでなければいいえを出力する」を提案する。これが誤る年を見つけ、正しいアルゴリズムをその仕様とともに書け。

解答

  1. (4∣n∧¬(100∣n))∨400∣n(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n

    仕様。入力：整数 n≥1583n \geq 1583（グレゴリオ暦は 1582 年 10 月から施行されている）。出力：はいまたはいいえ。関係：出力がはいとなるのは、nn が 44 で割り切れて 100100 で割り切れないとき、または 400400 で割り切れるとき、そしてそのときに限る。

  2. 1900=4⋅475,1900=400⋅4+3001900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300

    提案されたアルゴリズムは大部分の年で正しく、そのため正しく見える。これを反駁するには、100100 で割り切れて 400400 で割り切れない年が一つあれば足りる。19001900 は 44 で割り切れ、アルゴリズムははいと言う。しかし 19001900 年はうるう年ではなかった。

  3. 400∣n,100∣n,4∣n400 \mid n, \quad 100 \mid n, \quad 4 \mid n

    修正したアルゴリズムは、連鎖する三つの分岐からなる。手順 1：nn が 400400 で割り切れるなら、はいを出力して終了する。手順 2：nn が 100100 で割り切れるなら、いいえを出力して終了する。手順 3：nn が 44 で割り切れるならはいを出力し、そうでなければいいえを出力する。

  4. 2000,1900,2024,20232000, \quad 1900, \quad 2024, \quad 2023

    問いの順序は本質的である。最も特殊な規則から最も一般的な規則へと進む。もし先に 44 について問えば、19001900 年は例外に達する前にはいを受け取ってしまう。各場合から一つずつ、四つの年についてのトレース：20002000（手順 1：はい）、19001900（手順 2：いいえ）、20242024（手順 3：はい）、20232023（手順 3：いいえ）。

  5. 4∣1900∧¬(400∣1900)4 \mid 1900 \wedge \neg (400 \mid 1900)

    この教訓は暦だけのものではない。アルゴリズムはただ一つの反例で反駁され、反例はふつうの場合ではなく、規則の境目で探す。20242024、20202020、20162016 で試しても、何も見つからなかっただろう。

例題 3引き算による割り算は何周するか

引き算の繰り返しによる割り算を、a=20a = 20、b=5b = 5 の場合と a=0a = 0、b=7b = 7 の場合について手で追え。次に、許されるどの入力に対してもアルゴリズムがちょうど qq 周の後に停止し、その出力が事後条件を満たすことを示せ。

解答

  1. 20=5⋅4+020 = 5 \cdot 4 + 0

    a=20a = 20、b=5b = 5 のトレース：rr は 2020、1515、1010、55、00 と変わり、qq は 00、11、22、33、44 と変わる。五回目の判定 0≥50 \geq 5 は成り立たない。出力：q=4q = 4、r=0r = 0。ここでの境界の場合は割り切れる割り算である。四周目が行われるのは 5≥55 \geq 5 だからであり、そのため条件は ≥\geq でなければならず、>> ではいけない。

  2. 0=7⋅0+00 = 7 \cdot 0 + 0

    a=0a = 0、b=7b = 7 のトレース：最初の判定 0≥70 \geq 7 が成り立たない。本体は一度も実行されない。出力：q=0q = 0、r=0r = 0 で、これは正しい。

  3. b⋅(q+1)+(r−b)=b⋅q+r=a\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}

    保たれる関係。最初の周回の前は b⋅q+r=b⋅0+a=ab \cdot q + r = b \cdot 0 + a = a である。各周回で rr は bb だけ減り、qq は 11 だけ増えるので、b⋅q+rb \cdot q + r は変わらない。したがって、この等式は各周回の後で成り立つ。

  4. r0>r1>r2>⋯≥0r_0 > r_1 > r_2 > \cdots \geq 0

    停止性。反復が続く間 r≥b>0r \geq b > 0 であり、rr は自然数である。各周回でそれは b≥1b \geq 1 だけ減る。自然数の狭義減少列は有限である。反復は停止する。

  5. a=b⋅q+r,0≤r<ba = b \cdot q + r, \quad 0 \leq r < b

    停止したとき、条件は成り立たなかった。r<br < b である。さらに r≥0r \geq 0 である。bb を引くのは r≥br \geq b のときだけだからである。保たれる関係とあわせれば、出力は事後条件を満たす。そして qq は周回を数えているので、周回の数は商である。

オンライン演習

演習 1周回を数える

次のアルゴリズムを手で追い、それが出力する値を欄に書け。数字だけを書くこと。

  1. nn の値を 2929 にし、kk の値を 00 にする。
  2. n>1n > 1 が成り立つ間、手順 3 と 4 を繰り返す。成り立たなくなったら手順 5 に進む。
  3. nn が偶数なら nn の値を n/2n / 2 にし、奇数なら nn の値を n+1n + 1 にする。
  4. kk の値を k+1k + 1 にする。手順 2 に戻る。
  5. kk を出力する。

ブラウザは答えをその場で確認しますが、採点はしません。

ヒント

表を作ろう。最初の周回で nn は 2929 から 3030 に変わる。nn が変わるたびに一周と数え、nn が 11 になるまで続ける。

演習 2足りない条件

次のアルゴリズムは略記で書かれており、引き算の繰り返しによる割り算の商と余りを計算するはずだが、反復の条件が欠けている。下線の並んだ部分を正しい条件で置き換えよ。ほかは何も変えないこと。

ブラウザは答えをその場で確認しますが、採点はしません。

ヒント

a=10a = 10、b=5b = 5 でアルゴリズムを手で追ってみよう。余りがちょうど 55 でも、二周目は行われなければならない。

練習問題

各問題にはヒントがあり、自分で取り組んでから開くとよい。また答えがあり、ヒントを開いた後に現れる。

演習問題 1三つの数の並べ替えの仕様

問題「三つの数を並べ替える」の仕様（入力、出力、関係）を書き、問題文が決めていなかったどんな決定をそれが迫るかを指摘せよ。次に、入力 (5,2,5)(5, 2, 5) に対して、仕様が二つの出力 (2,5,6)(2, 5, 6) と (2,5,5,5)(2, 5, 5, 5) を退け、(2,5,5)(2, 5, 5) を受け入れることを確かめよ。

ヒント

「並んだ」出力は、入力と何の関係もないかもしれない。出力の数と入力の数を、重複するものも含めて結びつけるのはどんな条件か。昇順か降順か。狭義か否か。

答え

入力：三つの数 xx、yy、zz。出力：三つの数 uu、vv、ww。関係：u≤v≤wu \leq v \leq w であり、(u,v,w)(u, v, w) は (x,y,z)(x, y, z) の並べ替えである。つまり、同じ値を同じ重複のまま含む。問題文が決めていなかった決定：向き（ここでは小さいものから大きいものへ）。順序が狭義でないこと（≤\leq であって << ではない。値が重複すると狭義の順序は不可能だからである）。そして出力が並べ替えでなければならないこと。(2,5,6)(2, 5, 6) は並んでいるが、なかった 66 を含んでいる。(2,5,5,5)(2, 5, 5, 5) は値が四つある。(2,5,5)(2, 5, 5) は両方の条件を満たす。並べ替えの条件がなければ、(0,0,0)(0, 0, 0) はどんな入力に対しても正しい出力になってしまう。

演習問題 2数の桁を右から左へ

自然数 nn を受け取り、その桁を最後の桁から最初の桁へと出力する（40724072 なら 22、77、00、44 を出力する）アルゴリズムを、1010 で割った商と余りだけを使って、番号付きの手順で書け。40724072 と 00 について手で追い、すべての nn について停止することを示せ。

ヒント

1010 で割った余りが最後の桁であり、商はその桁を除いた数である。条件を問うのが桁を出力する前か後かを決め、n=0n = 0 のとき、つまり一桁の数のとき何が起きるかを見よ。

答え

正しいアルゴリズムの一つ：(1) nn を 1010 で割った余りを出力する。(2) nn の値を、nn を 1010 で割った商にする。(3) n>0n > 0 なら手順 1 に戻り、そうでなければ終了する。問いは本体の後にあるので、本体は少なくとも一回実行される。n=0n = 0 のときは 00 が出力され、これがその唯一の桁である。もし先頭で問うなら（「n>0n > 0 である間」）、n=0n = 0 のときは何も出力されない。反復が一度も実行されない場合を忘れる誤りである。40724072 のトレース：22、77、00、44 が出力され、nn は 407407、4040、44、00 と変わる。停止性：変量は nn で、自然数である。手順 1 に戻るのは n>0n > 0 だからであり、n≥1n \geq 1 のとき 1010 で割った商は nn より真に小さいので、nn は各周回で狭義に減少する。

演習問題 3硬貨でのおつり

5050、1010、11 単位の硬貨が、いくらでも使えるとする。仕様：入力は自然数 mm、出力は三つの自然数 c50c_{50}、c10c_{10}、c1c_1 で、50c50+10c10+c1=m50 c_{50} + 10 c_{10} + c_1 = m を満たし、硬貨の枚数 c50+c10+c1c_{50} + c_{10} + c_1 ができるだけ少ないもの。ある人が次のアルゴリズムを提案する。これが誤る入力を見つけ、それぞれの欠陥を説明し、修正せよ。

  1. c50c_{50}、c10c_{10}、c1c_1 の値を 00 にする。
  2. m≥50m \geq 50 なら、c50c_{50} の値を c50+1c_{50} + 1 にし、mm の値を m−50m - 50 にする。
  3. m>10m > 10 である間：c10c_{10} の値を c10+1c_{10} + 1 にし、mm の値を m−10m - 10 にする。
  4. m>0m > 0 である間：c1c_1 の値を c1+1c_1 + 1 にし、mm の値を m−1m - 1 にする。
  5. c50c_{50}、c10c_{10}、c1c_1 を出力する。
ヒント

硬貨の合計は常に mm である。誤りうるのは枚数のほうである。1010 のちょうどの倍数と、100100 を超える金額を試し、手順 2 が手順を組み合わせるどの方法を使っているか、そしてどれを使うべきかを考えよ。

答え

欠陥は二つある。第一に、手順 3 は m>10m > 10 を使っている。m=10m = 10 のとき、1010 の硬貨を一枚も出さずに 11 の硬貨を十枚出し、一枚で済むところをそうしない。第二に、手順 2 は反復が必要なところで分岐になっている。m=120m = 120 のとき、書かれたままのアルゴリズムは 5050 の硬貨を一枚、1010 を六枚、11 を十枚（計十七枚）出し、手順 3 を修正した後でも 5050 を一枚と 1010 を七枚（計八枚）出すことになり、5050 を二枚と 1010 を二枚（計四枚）にはならない。入力 m=100m = 100 は両方の欠陥を示す。アルゴリズムは 5050 を一枚、1010 を四枚、11 を十枚の計十五枚を出すが、二枚で足りる。修正：手順 2 は「m≥50m \geq 50 である間、…」、手順 3 は「m≥10m \geq 10 である間、…」とする。こう修正すると、アルゴリズムは常に入る最大の硬貨をとり、この三種類の硬貨ではそれで枚数が最小になる。mm の一の位は 11 の硬貨でしか払えず、残りはできるだけ 5050 の硬貨で払うのが得である。1010 の硬貨五枚は 5050 の硬貨一枚と同じ値だからである。ほかの硬貨、たとえば 11、33、44 で m=6m = 6 を払う場合には、常に最大のものをとっても最小にはならない（4+1+14 + 1 + 1 に対して 3+33 + 3）。