「1からnまでの総和」 = 「1からn-1までの総和」 + nこれはほぼ正しいのですが、そのままプログラム化すると、うまく行きません。
sum n = (sum (n-1)) + nこれでは、「どんな入力に対しても停止しない関数」になります。
そこで,こうやりましょう.
n <=0 のとき 「1からnまでの総和」 = 0 n > 0 のとき 「1からnまでの総和」 = 「1からn-1までの総和」 + nOCamlのプログラムとして書くと以下のようになります。
let rec sum n = if n <= 0 then 0 else (sum (n-1)) + nこれで OK です.ためしに sum 5 の計算を、手動と OCaml とでやってみてください。
m > n のとき 「mからnまでの総和」 = 0 m <= n のとき 「mからnまでの総和」 = 「mからn-1までの総和」 + nOCamlプログラムとすると、こうなります。
let rec sum2 m n = if m > n then 0 else (sum2 m (n-1)) + nこれで OK です.ためしに sum2 2 5 を計算してみてください.
これを漸化式で書けるでしょうか?
「nが素数である」 = 「n-1が素数である」が真のとき 。。。 そうでないとき。。。ちょっと書けそうもありません。n と n-1 は素数であるかどうかは独立です から、 n-1 が素数かどうかわかったところで、n が素数かどうかはよくわかりません。
そこで、問題を少し変形して、 「n が、2,3,4,...,k のすべてで割り切れないかどうか判定する」としてみましょう。 この問題が解けると、k=n-1 とすれば、元の問題である 「nが素数かどうかを判定する」ことができます。
「n が、2,3,4,...,k のすべてで割り切れない」 = 「n が、k で割り切れない」 かつ 「n が、2,3,4,...,k-1 のすべてで割り切れない」漸化式で書くことができました。 ただし、このままだと、また、停止しない関数になってしまうので、 2<=k であるか、 k < 2 であるかで場合分けしてから、OCamlになおします。 この関数名を notdivall_upto とすると、
let rec notdivall_upto n k = if k < 2 then true else (n mod k <> 0) && (notdivall_upto n (k-1))となります。 ここで e1 && e2 は、論理式でいうところの「e1 かつ e2」を表します。 また、n mod k <> 0 は「n を k で割ったときの余りが 0 でないこと、 つまり、n が k で割り切れないこと」を意味します。 さて、notdivall_upto ができると、素数判定は簡単にできます。
let isprime n = notdivall_upto n (n-1)関数isprime は再帰呼び出しをしていないので、let rec でなくて let で構いません。(let rec でも構いませんが。)
「n 以上の最小の素数」 = 「n-1以上の最小の素数」。。。あれ、うまく書けません。 「n-1以上の最小の素数」が n-1 そのものだったとき、困ります。(そんな計 算をしても「n以上の最小の素数」はまったくわかりませんから。) ここで、人間がなにをやるかを考えてみると、「n以上の最小の素数」を計算 するためには、 まず、n が素数かどうか試して、それが素数でなければ、次に n+1 を試しま すね。なるほど、n-1 でなく n+1 を見にいけばいいのです。「漸化式」風に 書くとこうなります。
「n 以上の最小の素数」 = if (n が素数) then n else 「n+1以上の最小の素数」これは、いわゆる数学的な「漸化式」にはなっていませんが、 ともかく、 OCamlプログラムにしてしまいましょう。
let rec least_prime n = if (isprime n) then n else least_prime (n+1)なんと、これで OK です。このプログラムは引数 n の値がどんどん大き くなっていきますから、(プログラムの定義だけを見ると)止まらないことがあ るように思える関数ですが、我々が知っている数学的知識として、「いくらで も大きい素数がある」ということがあるので、その事実に照らすと、 どんなn を与えても必ず、いつか、停止してn以上の素数を返す関数となって います。
「n の約数のうち、n自身以外で最大のもの」 = 「n-1 の約数のうち、n-1自身以外で最大のもの」。。。。あれ、また、うまく書けません。 n の約数と n-1 の約数は(ほぼ)無関係なので、n-1 の約数の計算が できたところで、それをつかって n の約数の計算をすることはできそうもあ りません。
「n の約数のうち m 以下で最大のもの」 = if 「n が m で割り切れる」 then m else 「n の約数のうち m-1以下で最大のもの」この関数も、計算が止まるかどうかが、ちょっと心配ですが、 考えてみれば、m が 1 まで減ったら、(n は必ず 1 で割り切れるので) そこ で停止します。
OCamlではこう書けます。
let rec largest_factor_upto n m = if (n mod m = 0) then m else largest_factor_upto n (m - 1)これを使って、最初の「n の約数のうち、n自身以外で最大のもの求める」関 数は以下のように書けます。
let largest_factor n = largest_factor_upto n (n-1)