ジョン・ベントリー：珠玉のプログラミング

概要

序文から引用する。この本の各コラムでは、 プロフェッショナルなプログラミングのもっと魅力的な側面を論じます。

感想

"Programing Pearls 2nd Edition" の邦訳である。 この本を読む時は「急ぎ過ぎないで下さい」という注意書きがある。 私は本を急いで読む癖があるので、自戒しなければならない。 ゆっくり読むいい方法は、章末の練習問題を解いてみることではないかと思っている。 この本は、ゆっくり読むだけの価値が十分にあると思う。

漸化式

第３章の 39 ページの問題 2 をみよう。

定数係数の `k` 次線形漸化式は `c_1, cdots, c_(k+1)` を実数として、

`a_n = c_1a_(n-1) + c_2a_(n-2) + cdots + c_ka_(n-k) + c_(k+1)`

のように定義されます。`k` と `a_1, cdots, a_k、c_1, cdots, c_(k+1) ` と `m` が与えられたときに、 `a_1` から `a_m` を出力するプログラムを考えてください。

なお、書籍では右辺が `c_1a_(n-)1 + c_2a_(n-2) + cdots ` の形になっていた。`a_(n-)1` は誤植で、 ただしくは `a_(n-1)` だろう。

さて、どのようにコードをかけばいいだろうか。 `k = 0` は対象外としてよさそうだ。 まず `k = 1` のときは `a_n = c_1a_(n-1) + c_2` となる。 次に `k = 2` のときは、`a_n = c_1a_(n-2) + c_2a_(n-1) + c_3` となる。

JavaScript では、`a_n` の式は次のようになるだろう。ここでは、`m > k` としてよい。 なぜなら、`m <= k` ならばすでに `a_1, cdots, a_k` は与えられているので計算の必要がないからだ。

for (let n = k + 1; n <= m ; n++) {
  for (let j = 1, a[n] = c[k + 1] ; j <= k; j++) { 
    a[n] += c[j] * a[n - j]
  } 
}

これは時系列解析における自己回帰モデルでもある。そうしたときに、係数が `c` で変数が `a` というのはちょっと気持ちが悪い。こういうときに、安田亨氏のいう、定数はアルファベットの前のほうで、 変数はアルファベットの後ろのほう、という暗黙の了解がよくわかる。

誤植など

誤植は上に挙げたものがある。

数式の記述

数式記述は ASCIIMathML を、 数式表記は MathJax を用いている。

まりんきょ学問所 ＞ コンピュータの部屋 ＞ 設計方法論 ＞ ジョン・ベントリー：珠玉のプログラミング