Print the n-th Fibonacci number, where fib(0) = 0, fib(1) = 1 and each next number is the sum of the two before it.
What to build
A Fibonacci function fast enough for large inputs.
Requirements
- Read
n. - Print
fib(n), using along long.
Input
One whole number n, with 0 ≤ n ≤ 90.
Output
fib(n).
Constraints
n is from 0 to 90, which is too large for the plain double recursion.
Example
Input:
10
Output:
55
Why it works
The simple two-call version repeats enormous amounts of work. Building up from the two smallest values, or storing results, needs only n steps.
Examples
Example 1 · Input
10
Expected output
55
Example 2 · Input
0
Expected output
0
Hints
Hint 1
fib(0) = 0, fib(1) = 1, fib(n) = fib(n - 1) + fib(n - 2).
Hint 2
Plain recursion is far too slow for n = 90. Keep the last two values in a loop instead.
Hint 3
fib(90) needs long long.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n;
scanf("%d", &n);
long long a = 0, b = 1;
for (int i = 0; i < n; i++) {
long long next = a + b;
a = b;
b = next;
}
printf("%lld\n", a);
return 0;
}