例題1 2数 x と y の最大値を m に求める。
例題2 n個の数 x1,x2,...,xn の最大値
を m に求める。
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)と呼ぶ。
例題 2の平方根を求める。
まず、解が 1よりも大きく2よりも小さいことから、1.1から始めて0.1きざみで 2乗を計算する。以上より、解は 1.4より大きく1.5より小さいことがわかる。 そこで、1.41から始めて0.01きざみで2乗を計算する。
- 1.12 = 1.21
- 1.22 = 1.44
- 1.32 = 1.69
- 1.42 = 1.96
- 1.52 = 2.25
... and so on ...
例 整列した配列の探索。線形探索(linear search) より2分探索(binary search) の方が高速になる。
例2 平方根の計算
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 となるまで 繰り返すのでなく、ある程度の誤差以内に入ったら計算を打ち切るように する。でないと、計算が終了しないこともありうる。