Write an algorithm that can handle n where 1000000 ≤ n ≤ 1500000.
Your algorithm must output the exact integer answer, to full precision. Also, it must correctly handle negative numbers as input.
HINT I: Can you rearrange the equation fib(n + 2) = fib(n + 1) + fib(n) to find fib(n) if you already know fin(n + 1) and fib(n + 2)? Use this to reason what value fib has to have for negative values.
In this kata you will have to calculate
fib(n)
where:Write an algorithm that can handle n where 1000000 ≤ n ≤ 1500000.
Your algorithm must output the exact integer answer, to full precision. Also, it must correctly handle negative numbers as input.
HINT I: Can you rearrange the equation
fib(n + 2) = fib(n + 1) + fib(n)
to findfib(n)
if you already knowfin(n + 1)
andfib(n + 2)
? Use this to reason what valuefib
has to have for negative values.HINT II: See http://mitpress.mit.edu/sicp/chapter1/node15.html
計算費式數列,參數可為負數。
提示1:在已知
fin(n + 1)
與fib(n + 2)
的情況下,透過重新排列fib(n + 2) = fib(n + 1) + fib(n)
就可以推算出 n 為負數時的值。 提示2:http://mitpress.mit.edu/sicp/chapter1/node15.html (用矩陣公式解)。https://www.codewars.com/kata/the-millionth-fibonacci-kata