采用递归形式和非递归形式实现斐波那契数列
复制代码 代码如下:
#include "stdafx.h"
#include
using namespace std;
//递归形式的斐波那契数列
int fibonacciRecursion(int n)
{
if (n == 1 || n ==2)
{
return 1;
}
if (n > 2)
{
return fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2);
}
}
//非递归形式的斐波那契数列
//用一个数组作为辅助的空间
//效率较高
int fibonacci(int n)
{
int temp[2];
temp[0] = 1;
temp[1] = 1;
if (n == 1 || n == 2)
{
return 1;
}
else
{
for (int i = 2; i < n; i ++)
{
int tp = temp[0] + temp[1];
temp[1] = temp[0];
temp[0] = tp;
}
return temp[0];
}
}
测试代码：
复制代码 代码如下:
int _tmain(int argc, _TCHAR* argv[])
{
cout << fibonacci(1) << " " << fibonacci(2) << " " << fibonacci(3) << " " << fibonacci(4) << " "
<< fibonacci(5) << " " << fibonacci(6) << " "<< fibonacci(7) << " "<< fibonacci(8) << " "
<< fibonacci(9) << " " << fibonacci(10) << endl;
cout << fibonacciRecursion(1) << " " << fibonacciRecursion(2) << " " << fibonacciRecursion(3) << " " <<
fibonacciRecursion(4) << " "<< fibonacciRecursion(5) << " " << fibonacciRecursion(6) << " "<< fibonacciRecursion(7)
<< " "<< fibonacciRecursion(8) << " "<< fibonacciRecursion(9) << " " << fibonacciRecursion(10) << endl;
return 0;
}
