blob: 47575e16eb0bfc9539a844a6fad540356591cd3b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <iostream>
#include <cassert>
// The following code calls a naive algorithm for computing a Fibonacci number.
//
// What to do:
// 1. Compile the following code and run it on an input "40" to check that it is slow.
// You may also want to submit it to the grader to ensure that it gets the "time limit exceeded" message.
// 2. Implement the fibonacci_fast procedure.
// 3. Remove the line that prints the result of the naive algorithm, comment the lines reading the input,
// uncomment the line with a call to test_solution, compile the program, and run it.
// This will ensure that your efficient algorithm returns the same as the naive one for small values of n.
// 4. If test_solution() reveals a bug in your implementation, debug it, fix it, and repeat step 3.
// 5. Remove the call to test_solution, uncomment the line with a call to fibonacci_fast (and the lines reading the input),
// and submit it to the grader.
int fibonacci_naive(int n) {
if (n <= 1)
return n;
return fibonacci_naive(n - 1) + fibonacci_naive(n - 2);
}
int64_t fibonacci_fast(int n) {
// write your code here
if (n <= 1)
return (int64_t) n;
int64_t fibArray [n+1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int j = 2; j < n+1; j++) {
fibArray[j] = fibArray[j - 1] + fibArray[j - 2];
}
return fibArray[n];
}
void test_solution() {
assert(fibonacci_fast(3) == 2);
assert(fibonacci_fast(10) == 55);
for (int n = 0; n < 20; ++n)
assert(fibonacci_fast(n) == fibonacci_naive(n));
}
int main() {
int n = 0;
std::cin >> n;
// std::cout << fibonacci_naive(n) << '\n';
// test_solution();
std::cout << fibonacci_fast(n) << '\n';
return 0;
}
|
