C语言排序(四)——三种方法实现斐波那契数列
一.实验目的:
通过3种算法来实现斐波那契数列,并比较3种算法的运行速率来体会循环,递归和分治是如何提高算法的运行效率的。
二.实验内容:
①利用多种方法实现斐波那契数列分别可用循环,递归和分治3种方法,并由此估算三种算法的时间复杂度,比较三种算法的运行效率。
②首先定义主函数分别定义3个时间变量来作为三种算法的运行时间,并且在主函数里输入斐波那契数列的个数n值。
③定义循环,递归函数来求出斐波那契数列,并用时间函数来计算其运行时间。定义矩阵分治函数来求斐波那契数列和运行时间。对于矩阵分治函数要注意函数的返回值,并且是矩阵相乘不是数字相乘。
④得出结论这三种算法的效率哪个更高。
三 .程序代码:
#include<stdio.h> #include<iostream> #include<cstring> #include<stdlib.h> #include<time.h> using namespace std; const int MAX=10; #define input long long #define Bit(n) 1<<n #define CLR(arr,val) memset(arr,val,sizeof(arr)) class Matrix{ public: Matrix(int r,int c):row(r),col(c){} void Init() { CLR(map,0); map[0][0]=map[0][1]=map[1][0]=1; } void Unit() { CLR(map,0); for(int i=0;i<row;i++) map[i][i]=1; } int Result() const{return map[0][1]%10000;} friend Matrix operator*(const Matrix& ,const Matrix&); int Pow(int); private: input map[MAX][MAX]; int row,col; }; Matrix operator*(const Matrix& M1,const Matrix& M2) { Matrix M(M1.row,M2.col); for(int i=0;i<M1.row;i++) for(int j=0;j<M2.col;j++) { M.map[i][j]=0; for(int k=0;k<M1.col;k++) M.map[i][j]+=M1.map[i][k]*M2.map[k][j]; M.map[i][j]%=10000; } return M; } Matrix M(2,2); int Matrix::Pow(int n) { Matrix temp(2,2); temp.Init(); for(int i=0;Bit(i)<=n;i++) { if(Bit(i)&n) M=M*temp; temp=temp*temp; } return M.Result(); } int facii(int n) { int a[]={0,1}; int i=0,x1=0,x2=1,x3=0; if(n<2) return a[n]; for(i=2;i<=n;i++) { x3=x1+x2; x1=x2; x2=x3; } return x3; } int fibonacci_iteration(int n) { int result[2] = { 0, 1 }; int i = 2; int num = 0; if(n < 2) { return result[n]; } int fib_minusone = 1; int fib_minustwo = 0; for(;i <=n;i++) { num = fib_minusone + fib_minustwo; fib_minustwo = fib_minusone; fib_minusone = num; } return num; } int main() { clock_t start, finish; int n,y,z; double duration; printf("输入要计算的个数:") ; scanf("%d",&n); printf("递归法求斐波那契数列\n") ; start = clock(); y=facii(n); finish = clock(); printf("%d\n",y); duration = (double)(finish - start) / CLOCKS_PER_SEC*1000; printf( "运行时间%f seconds\n", duration ); printf("迭代法求斐波那契数列\n") ; start = clock(); z = fibonacci_iteration(n); finish = clock(); printf("%d\n",z); duration = (double)(finish - start) / CLOCKS_PER_SEC*1000; printf( "运行时间%f s\n", duration ); printf("矩阵法求斐波那契数列\n"); printf("请输入要计算的个数:") ; start = clock(); while(cin>>n,n!=-1) { M.Unit(); cout<<M.Pow(n)<<endl; finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC*1000; printf( "运行时间%f s\n", duration ); } return 0; }四:结果演示:
四.实验结论:
三种方法中二分矩阵的时间复杂度<循环函数的时间复杂度<递归函数的时间复杂度。二分矩阵的时间复杂度效率最高。