東京大学情報理工学系研究科電子情報学専攻 2013年8月実施専門第3問

标签：

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

$f(0)=0$ , $f(1)=1$ および漸化式 $f(n)=f(n-1)+f(n-2)$ $(n>1)$ で表される数列はフィボナッチ数列と呼ばれる。これについて以下の問いに答えよ。

(1) 漸化式に従い、再帰呼び出しを使って $f(n)$ を計算するプログラムを擬似コードにより記述せよ。

(2) 漸化式に従い、再帰呼び出しを使わずに $f(n)$ を計算するプログラムを擬似コードにより記述せよ。

(3) 64ビット整数を用いて計算する場合、(1) および (2) それぞれの方法の問題点を述べよ。

(4) フィボナッチ数列の一般項は

f(n)=\frac1{\sqrt5}\left[\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right]

となることが分かっている。この式に従って浮動小数点数を用いて計算する場合、(2) の方法と比較し利害得失を述べよ。

数列由 $f(0)=0$ 、 $f(1)=1$ 以及递推关系

f(n)=f(n-1)+f(n-2)\qquad(n>1)

定义，称为斐波那契数列。回答下列问题。

(1) 按照上述递推关系，写出使用递归调用计算 $f(n)$ 的伪代码。

(2) 再写一段依据同一递推关系、但不使用递归调用来计算 $f(n)$ 的伪代码。

(3) 假设使用 $64$ 位整数，分别说明 (1)、(2) 两种方法的缺点。

(4) 斐波那契数列的闭式为

f(n)=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right].

与 (2) 的方法相比，说明使用浮点数按该闭式计算的优点与缺点。

Fib(n):
    if n <= 1:
        return n
    return Fib(n - 1) + Fib(n - 2)

Fib(n):
    if n <= 1:
        return n
    a = 0
    b = 1
    for i = 2 to n:
        c = a + b
        a = b
        b = c
    return b

(1) は同じ値を繰り返し計算し、 $\varphi=(1+\sqrt5)/2$ とすると時間は $\Theta(\varphi^n)$ 、再帰スタックの空間は $O(n)$ となる。(2) は時間 $O(n)$ 、追加空間 $O(1)$ だが、計算時間は $n$ に比例して増える。

両者とも64ビット整数の範囲を超えると正しい値を表せない。符号付き整数では

f(92)=7540113804746346429\le2^{63}-1 <f(93)=12200160415121876738

より、 $n\ge93$ でオーバーフローする。符号なし整数でも $f(94)>2^{64}-1$ となる。

一般項では過去の全項を順に求める必要がなく、累乗を二乗法で計算すれば浮動小数点演算の回数は $O(\log n)$ となる。また、通常の浮動小数点形式では64ビット整数より大きい値を近似的に扱える。

一方、 $\sqrt5$ や累乗の丸め誤差が蓄積・増幅し、整数値が厳密に得られる保証はない。最寄りの整数に丸めても、誤差が $1/2$ 以上なら誤答となる。十分大きい $n$ では浮動小数点数もオーバーフローする。(2) は整数の表現範囲内なら厳密である。