Todai Entrance Exam: Subject 2014 – Problem 3

(1)

func f(n):

  • if n == 0:
    • return 0
  • if n == 1:
    • return 1
  • return f(n – 1) + f(n – 2)

(2)

func f(n):

  • left = 1
  • right = 0
  • d = 1
  • if d > n:
    • return right
  • while d < n:
    • temp = left
    • left = left + right
    • right = temp
    • d = d + 1
  • return left

(3)

I’mt not sure how the number of bits of the integer is involved here. However, recursive calls use the stack memory and it can incur the stack overflow problem when $ n $ becomes big enough.

I don’t see any drawbacks for the while loop except possible unaware infinite loops.

(4)

It’s super fast. However, the square root $ \sqrt{5} $ does not yield the exact number in floating-point representation, so the Fibonacci number computed this way is only an approximation.

The while loop in (2) is much slower but it yields the exact number and we can also store the computed Fibonacci sequence for later fast using if we wish to.


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *