这学期我们终于开始学习算法设计。
第一次实验室实现斐波那契的四种算法，递归，非递归，公式法，矩阵相乘法。
当然，这些都是很基础的啦。
上机的时候，受到编译环境的问题（是不是高校都喜欢配置VC6.0？）让我很是郁闷，比如说long long无法用了，要用__int64,而__int64不支持cout操作。最后只能用scanf,printf等等保持统一风格
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<conio.h>
using namespace std;
#define N 2
/*
dicription:实现计算fibonacci的递归算法，线形for循环算法
注意在vc6.0下:
1.只能用__int64,不能使用long long
2.cout对__int64不起作用,只能用printf("%I64d",x);
3.为作方便，我直接将方法写成static,利用类名调用。
*/
//matrix
typedef struct
{
__int64 a[N][N];
}matrix;
matrix mult(matrix &A,matrix &B){
int i,j,k;
matrix c;
for( i = 0; i < N ; i ++ )
for( j = 0; j < N; j ++ )
{
c.a[i][j] = 0;
for( k = 0 ; k < N ; k ++ )
c.a[i][j] +=A.a[i][k] * B.a[k][j];
}
return c;
}
class Fibonacci{
public:
static __int64 fib_rec(int n){ //回归算法
if(n==2||n==1 ) return 1;
return fib_rec(n-1)+fib_rec(n-2);
}
static __int64 fib_line(int n){
__int64 f1=0,f2=1,tmp;
while(n--){
tmp=f1;
f1=f1+f2;
f2=tmp;
}
return f1;
}
static __int64 * fib_line_save(int n){ //线性算法,并保存结果
//从0开始算起
__int64 * fib_v;int i;
if(!( fib_v=(__int64 *)malloc( sizeof(__int64)*(n) ) ) ){
cout<<"内存不足分配";
};
fib_v[0]=fib_v[1]=1; //初始化
for(i=2;i<n;i++){
fib_v[i]=fib_v[i-1]+fib_v[i-2];
}
return fib_v;
}
static __int64 fib_matrix(int n){ //矩阵计算
// Matrix(A)= ┏ 1,1 ┓ ,pow(A,n) =┏ fib(n+1),fib(n) ┓
// ┗ 1,0 ┛ ┗ fib(n) ,fib(n-1)┛
matrix fib_init,fib_res;
fib_init.a[0][0]=1;fib_init.a[0][1]=1;
fib_init.a[1][0]=1;fib_init.a[1][1]=0;
fib_res.a[0][0]=1;fib_res.a[0][1]=0;
fib_res.a[1][0]=0;fib_res.a[1][1]=1;
while( n > 1 )
{
if( n % 2 == 1 ) //为奇数，不满足二分
{
n --;
fib_res = mult(fib_init,fib_res); //乘于单位矩阵，奇数部分一直累乘到p中
}
else
{
n = n / 2;
fib_init = mult(fib_init,fib_init);//两边累乘
}
}
fib_res = mult(fib_init,fib_res);
return fib_res.a[0][1];
}
static __int64 fib_formula(int n){//公式法
double a=pow( (1+sqrt(5.0))/2.0 , n ) ;
double b=pow( (1-sqrt(5.0))/2.0 , n ) ;
double res=(a-b)/sqrt(5.0);
return (__int64)res;
}
};
int main(){
int i;
__int64 *fib_p=Fibonacci::fib_line_save(11);
for( i=1;i<=10;i++){
printf("fib_p : %I64d
", fib_p[i-1]);
printf("fib_rec : %I64d
", Fibonacci::fib_rec(i) ); //test for rec
printf("fib_matrix : %I64d
", Fibonacci::fib_matrix(i)); //test for matrix
printf("fib_line : %I64d
", Fibonacci::fib_line(i) ); //test for line
printf("fib_formula: %I64d
", Fibonacci::fib_formula(i));//test for formula
}
free(fib_p); // free p
cout<<"Enter a big number for the test: ";
scanf("%d",&i);
//test for a big num;
//printf("%I64d
", Fibonacci::fib_rec(80) ); fail.
printf("fib_matrix : %I64d
", Fibonacci::fib_matrix(i)); //test for matrix
printf("fib_line : %I64d
", Fibonacci::fib_line(i) ); //test for line
printf("fib_formula: %I64d
",Fibonacci::fib_formula(i)); //test for formula
cout<<"Press any key to test fib_matrix and fib_line";
getch();
for(i=40;i<=90;i++ ){
printf("fib_matrix : %I64d
", Fibonacci::fib_matrix(i)); //test for matrix
printf("fib_line : %I64d
", Fibonacci::fib_line(i) ); //test for line
printf("fib_formula: %I64d
",Fibonacci::fib_formula(i)); //test for formula
}
return 0;
}
……