プログラミングの方法

問題の把握

プログラムの状態について考えるとき、 状態を構成するひとつひとつの値が問題ではなく、 その状態で成立する条件式が問題である。

例題1 2数 x と y の最大値を m に求める。

  1. 実行前の状態
    (x = X) and (y = Y)
  2. 実行後の状態
    (x = X) and (y = Y) and ((m = X) and (X >= Y) or (m = Y) and (Y >= X)

例題2 n個の数 x1,x2,...,xn の最大値 を m に求める。

m = max(x1,x2,...,xn)は以下の条件式と等しい。
(m = max(x2,x3,...,xn)) and (m>=x1) or
(m = x1) and (m >= max(x2,x3,...,xn))
および
x1 = max(x1)
これを、プログラム風(?)に書くと、 
int max(int n,int x1,int x2,...,int xn) {
    int m;
    if (n == 1) m = x1;
    else {
        m = max(n-1,x2,x3,...,xn);
        if (x1 > m) m = x1;
    }
    return(m);
}

上のプログラム実行の実際の経過を書くと、

m = xn;
if (xn-1 > m) m = xn-1;
...
if (x1 > m) m = x1;
となる。繰り返しを使えば、 
m = x[n]; i=n-1;
while (i > 0) {
    if (x[i] > m) m = x[i]
    i--;
}
ここでは、whileループの中の最初の時点で、m には それ以前の最大値が入っている、つまり
m = max(xi+1,xi+2,...,xn)
である ことを利用している。 このような、反復実行の一定の場所で常に成り立って いる条件のことをループ不変条件(loop invariant condition) またはループ不変量(loop invariant)と呼ぶ。
  1. 成り立つべきループ不変量を先に考え、それを頼りに反復文を書く ことでプログラミングを容易にする。
  2. ループ不変量は、問題を正確に定式化することで、おのずと現れて くる。（問題と解法の橋渡し役）

逐次接近法

解を直接計算で求められない場合に、近似解からはじめて真の解へ接近させて いく方法。

例題 ２の平方根を求める。

まず、解が 1よりも大きく2よりも小さいことから、1.1から始めて0.1きざみで ２乗を計算する。 以上より、解は 1.4より大きく1.5より小さいことがわかる。 そこで、1.41から始めて0.01きざみで２乗を計算する。

... and so on ...

逐次接近法の改良

解の範囲の絞り込みを、等比級数的なものに改良する。

例 整列した配列の探索。線形探索(linear search) より２分探索(binary search) の方が高速になる。

例２ 平方根の計算

f(x+d) = f(x) + f'(x)*d + ...

を使う。 f(x) = x2 - 2 で、f(x)=0 の根を求めることになるので、 仮の解を a として、
0 = f(a)+f'(a)*d
を d について解けば、 f(a+d) は 0 に近くなる。
これが 0 でなければ、a = a+d を代入し、 再度 d を求める。これを繰り返す。
正確に f(a+d) = 0 となるまで 繰り返すのでなく、ある程度の誤差以内に入ったら計算を打ち切るように する。でないと、計算が終了しないこともありうる。