fiblong.cpp

实现超长位数的Fibnach数列的计算程序

/**********************************************************
*****                                                  ****
*****任意位数斐波那挈数列计算程序                      ****
*****                                                  ****
*****王平  2004年10月31日                              ****
*****                                                  ****
**********************************************************/
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
int n;
void Regular(vector<long>& v){
	long carry=0,m;
	vector<long>::iterator it;
	it=v.end();//
	while(it!=v.begin()){
		m=*it+carry;
		*it=m%100000000;
		carry=m/100000000;
		it--;
	}//cout<<"\n*it="<<*it<<endl;
	m=*it+carry;
	if(m>100000000){
		*it%=100000000;
		v.insert(v.begin(),m/100000000);
	}
	else *it=m;
}

void print(vector<long>& v){
	cout<<"\nFib("<<n<<")=";
	vector<long>::iterator it;
	it=v.begin();cout<<*it++;
	while(it!=v.end()) cout<<setfill('0')<<setw(8)<<*it++;
	cout<<endl;
}
vector<long> Fib(int m){
	vector<long> f0,f1;
	f0.insert(f0.begin(),0);
	f1.insert(f1.begin(),1);
	if(m==0) return f0;
	if(m==1) return f1;
	vector<long> fc;
	fc.resize(f1.size());
	copy(f1.begin(),f1.end(),fc.begin());
	for(int i=2;i<=m;i++){
		vector<long>::iterator it0,itc;
		it0=f0.begin();itc=fc.begin();
		if(f1.size()==f0.size())
			while(it0!=f0.end()) {*itc+=*it0++;itc++;}
		else while(it0!=f0.end()) {itc++;*itc+=*it0++;}
		Regular(fc);
		f0.resize(f1.size());
		copy(f1.begin(),f1.end(),f0.begin());
		f1.resize(fc.size());
		copy(fc.begin(),fc.end(),f1.begin());
	}
	return fc;
}


int main(){
	while(1){
		long k;
		cout<<"\nPlease input k: "<<endl;
		cin>>k;
		if(k==-1) return 0;
		for(n=0;n<k+1;n++) {print(Fib(n));}
	}
}