An algorithm to show Fibonacci numbers. Fibonacci numbers are infinite natural numbers and begins with:
0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | ... |
(optional) | 0 + 1 | 1 + 1 | 1 + 2 | 2 + 3 | 3 + 5 | 5 + 8 |
Following this, is the next result the sum of two sequential numbers.
1 | /* |
2 |     Fibonacci numbers |
3 |      |
4 |     GMP library required |
5 |      |
6 |     How to compile with GCC under LINUX/UNIX: |
7 |     g++ -lgmp -lgmpxx -o fibonacci main.cpp |
8 |      |
9 | */ |
10 | |
11 | #include <iostream> |
12 | #include <gmpxx.h> |
13 | using namespace std; |
14 | |
15 | int fibonacci_recursive(int); |
16 | mpz_class fibonacci_iterative(int); |
17 | |
18 | int main() { |
19 |     int num; |
20 |      |
21 |     cout << "Fibonacci numbers:" << endl; |
22 |     cout << "Input number: "; |
23 |     cin >> num; |
24 |     if(num < 0) cout << "Error, please type in numbers greater then -1" << endl; |
25 |     else cout << "Fibonacci number is: " << fibonacci_iterative(num) << endl; |
26 |      |
27 |     return 0; |
28 | } |
29 | |
30 | int fibonacci_recursive(int num) { |
31 |     if(num == 0) return 0; |
32 |     if(num == 1) return 1; |
33 |     return fibonacci_recursive(num - 1) + fibonacci_recursive(num - 2); |
34 | } |
35 | |
36 | mpz_class fibonacci_iterative(int num) { |
37 |     mpz_class prev = 1; |
38 |     mpz_class curr = 1; |
39 |     mpz_class next = 1; |
40 |      |
41 |     for(int i = 3; i <= num; ++i) { |
42 |         next = curr + prev; |
43 |         prev = curr; |
44 |         curr = next; |
45 |     } |
46 |     return next; |
47 | } |