求某一斐波拉契数算法时间复杂度(logN)代码,C代码库,德仔网

代码语言

代码分类

【C】求某一斐波拉契数算法时间复杂度(logN)

作者:追忆丶梦 / 发布于2015/4/8/ 420


	#include<iostream>
	using namespace std;
	long long map[2][2]={1LL,0LL,1LL,0LL};
	long long E[2][2]={1LL,1LL,1LL,0LL};
	long long fun(long long x);
	void _copy(long long (*by_map)[2],long long (*to_map)[2]);
	void _cal(long long (*map1)[2],long long (*map2)[2],long long (*new_map)[2]);
	int main()
	{
	 long long n;
	 while(cin>>n){
	 cout<<fun(n)<<endl;
	 }
	
	}
	long long fun(long long x)
	{
	
	 if(x==1)
	 {
	 _copy(map,E);
	 }else{
	 long long temp[2][2];
	 _copy(temp,map);
	 fun(x/2);
	 _copy(temp,map);
	 _cal(temp,temp,map);
	 if(x%2==1)
	 {
	 _copy(temp,map);
	 _cal(temp,E,map);
	 }
	 }
	 return map[0][1];
	}
	void _copy(long long (*by_map)[2],long long (*to_map)[2])//将to_map 赋值到 by_map
	{
	 by_map[0][0]=to_map[0][0];
	 by_map[0][1]=to_map[0][1];
	 by_map[1][0]=to_map[1][0];
	 by_map[1][1]=to_map[1][1];
	}
	void _cal(long long (*map1)[2],long long (*map2)[2],long long (*new_map)[2])//MAP1*MAP2=NEW_MAP
	{
	 long long mod_val=10000;
	 new_map[0][0]=((map1[0][0]*map2[0][0])%mod_val+(map1[0][1]*map2[1][0])%mod_val)%mod_val;
	 new_map[0][1]=((map1[0][0]*map2[0][1])%mod_val+(map1[0][1]*map2[1][1])%mod_val)%mod_val;
	 new_map[1][0]=((map1[1][0]*map2[0][0])%mod_val+(map1[1][1]*map2[1][0])%mod_val)%mod_val;
	 new_map[1][1]=((map1[1][0]*map2[0][1])%mod_val+(map1[1][1]*map2[1][1])%mod_val)%mod_val;
	}

试试其它关键字

　斐波拉契数　

同语言下

可能有用的

追忆丶梦贡献的其它代码(1)

.求某一斐波拉契数算法时间复杂度(logN)