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

Author

Josuke, 祭音Myyura

Description

The sequence that is defined by , , and the recurrence relation is called the Fibonacci sequence. Answer the following questions on this sequence.

(1) Give a pseudo-code program to calculate using recursive calls according to the recurrence relation.

(2) Give another pscudo-code program to calculate from the recurrence relation without using recursive calls.

(3) Assume that 64-bit integers are used. Explain the drawbacks of each of the methods described in Questions (1) and (2).

(4) The closed-form solution of the Fibonacci sequence is

Explain the merits and drawbacks of the calculation using this form with floating point numbers, as compared to the method described in Question (2).

Kai

(1)

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

Code 1: Calculate using recursive calls

(2)

def Fib(n) :
    result = [0] * (n+1)
    result[1] = 1
    for i = 2 to n+1 :
        result[i] = result[i-1] + result[i-2]
    return result[n]

Code 2: calculate from the recurrence relation without using recursive calls

(3)

The time complexity of Code 1 is (Hint: Solve recurrence relation ).

The space complexity of Code 1 is (Hint: function calls are executed sequentially. Sequential execution guarantees that the stack size will never exceed the depth of the calls' tree, which is ).

The time complexity and space complexity of Code 2 are both , which implies that Code 2 runs much faster than Code 1. But still, Code 2 needs space.

(4)

By using Exponentiation by squaring, can be calculated in , which is faster than Code 2. But due to the inaccuracy of float point numbers, it is hard to calculate the accurate answer of in terms of the closed-form formula of Fibonacci sequence.