加载中…C/C++Fibonacci数列三种实现方法及比较
(2012-08-07 17:50:00)
标签：
c语言fibonacci斐波那契数列it |
分类： C/C++ |
说明：3种方法都可以求出结果，但效率各不相同（效率依次递减，由于递归法效率很低，故只进行1次试验）
对三种算法进行了测试：
测试环境：处理器AMD Phenom II N830 2.10GHz,2GB内存
数据平移法与递归法：计算Fibonacci(20)10000次，重复试验10次，平移法耗时平均0.0012s（精确到1ms），递归法平均用时2.8480s
数据平移法与数组法：计算Fibonacci(20)10000000次，重复试验10次，平移法耗时平均1.0585s（精确到1ms），数组法平均用时1.4952s
fib（1） = 1；
fib（2） = 1；
fib（n） = fib（n-1） + fib（n-2）
//对大于等于3的任意n
（1）简单变量"数据平移"方法计算Fibonacci数列的第n项（正整数n通过键盘输入）：
说明变量old1=1，old2=1，newItem；新的Fibonacci项newItem总是"距它最近"的前两项（old1与old2）的累加和。
而后通过"old1=old2;
old2=newItem;"进行所谓的"数据平移"。接着计算另一个新的Fibonacci项newItem，
依次循环，直到求出数列的第n项时为止。
（2）使用数组求出Fibonacci数列的第n项（正整数n通过键盘输入）并显示在屏幕上：
说明数组f用来存放Fibonacci数列的各项之值，且仅初始化前两个元素f[0]=1，f[1]=1，
而后通过f[i]=f[i-2]+f[i-1]；依次计算出f[2]到f[n-1]（注意f[n-1]恰为所要求出的第n项）并将该值显示在屏幕上。
数据平移法
#include <stdio.h>
void main()
{
int n,old1(1),old2(1),newItem,i;
printf("请输入n的值:");
scanf("%d",&n);
if(n<3)
{
if(n>0)printf("1");
else printf("输入有误!");
}
else
{
for(i=3;i<=n;i++)
{
newItem=old1+old2;
old1=old2;
old2=newItem;
}
}
printf("Fibonacci(%d)=%d",n,newItem);
}
数组法
#include <stdio.h>
#include <malloc.h>
void main()
{
int n,i;
printf("请输入n的值:");
scanf("%d",&n);
int *f=(int *)malloc(sizeof(int)*n);
f[0]=f[1]=1;
if(n<3)
{
if(n>0)printf("1");
else printf("输入有误!");
}
else
{
for(i=2;i<n;i++)
{
f[i]=f[i-1]+f[i-2];
}
}
printf("Fibonacci(%d)=%d",n,f[n-1]);
free(f);
}
附：递归法（C++）
#include <iostream>
using namespace std;
int Fibonacci(int n)
{
return
n>2?Fibonacci(n-1)+Fibonacci(n-2):1;
}
void main()
{
int n;
cout<<"请输入n的值:";
cin>>n;
cout<<"Fibonacci("<<n<<")="<<Fibonacci(n)<<endl;
}
本文来自lyz810的新浪博客，http://blog.sina.com.cn/s/blog_a9d3c71c01016p32.html
喜欢
0
赠金笔
前一篇：趣味C语言四则运算练习器
后一篇：C语言数据类型转换函数