帰納法に関するプログラミング
例1 階乗
自然数 n (≧0)の階乗を計算することを考えます。
n の階乗 f(n) は、以下のように帰納的に定義されます。
- f(0) = 1
- f(n) = f(n-1) * n (n≧1)
この定義から、
f(n) = f(n-1) * n = f(n-2) * (n-1) * n = … = f(0) * 1 * … * (n-1) * n
= 1 * 1 * … * (n-1) * n
となります。
これは、
i = 0 のとき f(i) = 1、
f(i+1) = f(i) * (i+1) を i+1≦n まで繰り返したときの
f(i+1) の値となります。
これを、
1[i=0,i+1≦n] *[i+1] (i+1)
と書くことにします。
xi, yi, zi を
x0 * y0 = z0,
x1 * y1 = z1, …,
xn-1 * yn-1 = zn-1
を満たすものとします。
さらに
z0 = x1,
z1 = x2, …,
zn-2 = xn-1
を満たすとします(これを x0 *(0-1) yi で表します。
0 は zi を、1 は xi を表し、0-1 は
zi+1 = xi を表します)。
y0 = 1,
y1 = y0 + 1, …,
yn-1 = yn-2 + 1
を満たすとします
(これを yi +(0-1) 1 で表します。
また、*(0-1) と +(0-1) の yi の i が同じものであることを
表すために、*(0-1){0} と +(0-1){0} のように、同じ数字を{}で囲んだものを
つけて表します)。
これを yi ≦ n となるまで繰り返します
(これを 1 +(0-1){0} 1 ≦ n で表します)。
これを次のように書くことにします。
1 *(0-1){0} (1 +(0-1){0} 1), 1 +(0-1){0} 1 ≦ n
例2 フィボナッチ数
自然数 n (≧0)に対して、n 番めの
フィボナッチ数 F(n) は、以下のように帰納的に定義されます。
- F(0) = F(1) = 1
- F(n) = F(n-1) + F(n-2) (n≧2)
1[i=0,i+2≦n] +[i+2] 1[i+1]
1 +(0-1,1-2){0} 1, 1 +(0-1){0} 1 ≦ n
例3 二項係数
自然数 m (≧0)と整数 n に対して、
二項係数 b(m, n) は、以下のように帰納的に定義されます。
- b(0, 0) = 1
- b(0, n) = 0 (n≠0)
- b(m, n) = b(m-1, n-1) + b(m-1, n) (m≧1)
1[i=0,i+1≦m;j,j+1≦n] +[i+1;j+1] 1[i;j+1]