#数据结构-fib

 1 ///////////////////////////////////////////////////////////////////////////////
 2 //
 3 //  FileName    :   fic.c?
 4 //  Version     :   0.10
 5 //  Author      :   Ryan Han
 6 //  Date        :   2013/07/01 10:12:30
 7 //  Comment     :  
 8 //
 9 ///////////////////////////////////////////////////////////////////////////////
10 #include <stdio.h>
11 
12 static long fib(const long n)
13 {
14     return 0 == n || 1 == n ? 1 : fib(n - 1) + fib(n - 2);
15 }
16 
17 int main()
18 {
19     //F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）
20     long lResult = fib(5);
21     printf("The resutl is: %ld
", lResult);
22 }

上面的方法会导致大量的重复计算，为了避免可以用非递归的方式计算：

 1 // 19_2.cc
 2 #include <iostream>
 3 using namespace std;
 4 
 5 size_t fibo(size_t n) {
 6     if (n < 2)
 7         return n;
 8 
 9     size_t f1 = 0;
10     size_t f2 = 1;
11     size_t res;
12     for (size_t i = 2; i <= n; i++) {
13         res = f1 + f2;
14         f1 = f2;
15         f2 = res;
16     }
17     return res;
18 }
19 
20 int main() {
21     size_t n;
22     cout << "please input n:" << endl;
23     cin >> n;
24     cout << "The Fibonacci is: " << fibo(n) << endl;
25     return 0;
26 }