首页 > 代码库 > 09_斐波那契数列
09_斐波那契数列
#include<iostream>
#include<vector>
#include<Ctime>
using namespace std;
long long fibRecursion(unsigned n) {
if(n <= 0) {
return 0LL;
}
if(n == 1) {
return 1LL;
}
if(n >= 2) {
return fibRecursion(n - 1) + fibRecursion(n -2);
}
}
long long fibUnRecursion(unsigned n) {
if(n == 0) {
return 0LL;
}
if(n == 1) {
return 1LL;
}
long long fibNSmaller = 0LL;
long long fibNBigger = 1LL;
long long fibN = 0LL;
unsigned i = 2;
for(i = 2; i <= n; i++){
fibN = fibNSmaller + fibNBigger;
fibNSmaller = fibNBigger;
fibNBigger = fibN;
}
return fibN;
}
int main() {
unsigned i = 0;
clock_t start, finish;
start = clock();
cout<<"fibRecursion(46) = "<<fibRecursion(45)<<endl;
finish = clock();
double duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout<<"execution time duration(fibRecursion):"<<duration<<endl;
start = clock();
cout<<"fibUnRecursion(46) = "<<fibUnRecursion(45)<<endl;
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout<<"execution time duration(fibUnRecursion):"<<duration<<endl;
return 1;
}运行结果：
fibRecursion(46) = 1134903170 execution time duration(fibRecursion):11.603 fibUnRecursion(46) = 1134903170 execution time duration(fibUnRecursion):0.001 -------------------------------- Process exited with return value 0 Press any key to continue . . .从运行结果可以看出，非递归的方式求斐波那契数列效率远高于递归的求法
09_斐波那契数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。