sizeof.cpp

一个求大数阶乘的算法

// sizeof.cpp : Defines the entry point for the console application.
//

#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<ctime>
#include<cstdlib>
#define MAX 10000

using  namespace std;
typedef vector<unsigned int>  myvec;

//typedef myvec  *pvec;
inline void vecset(myvec  &vec)
{
	int i,ix=vec.size();
	if(ix<1)
		return;
	for(i=0;i<ix-1;i++)
	{
		if(vec[i]<MAX)
			continue;
		else{
			vec[i+1]+=vec[i]/MAX;
			vec[i]%=MAX;
		}
	}
	while(vec[ix-1]>=MAX)
	{
		vec.push_back(vec[ix-1]/MAX);
		vec[ix-1]%=MAX;
		ix++;
	}
}
void vecadd(myvec  &vec1,myvec  &vec2)
{
	int ix1=vec1.size(),ix2=vec2.size();
	if(ix1>=ix2)
	{
		for(int i=0;i<ix2;i++)
		{
			vec1[i]+=vec2[i];
		}
		vecset(vec1);
	}
	else
	{
		vec1.resize(ix2);
		for(int i=0;i<ix2;i++)
		{
			vec1[i]+=vec2[i];
		}
		vecset(vec1);
	}
}
void vecmove(myvec  &vec,int n)
{
	if(n>0)
	{
		int ix=vec.size(),ix2;
		vec.resize(ix+n);
		ix2=vec.size();
		for(int i=ix-1,j=ix2-1;i>=0;i--,j--)
		{
			vec[j]=vec[i];
		}
		for(int k=0;k<n;k++)
		{
			vec[k]=0;
		}
	}
}
void vecmul(myvec  &vec1,myvec  &vec2)
{
	
	int ix1=vec1.size(),ix2=vec2.size();
	int ze1=0,ze2=0;
	while(!vec1[ze1])ze1++;
	while(!vec2[ze2])ze2++;
	myvec temp(ix1-ze1),answer;
	for(int i=ze2;i<ix2;i++)
	{
		for(int j=ze1;j<ix1;j++)
		{
			temp[j-ze1]=vec1[j]*vec2[i];
		}
		vecset(temp);
		vecmove(temp,i-ze2);
		vecadd(answer,temp);
		temp.resize(ix1-ze1);
	}
	vecmove(answer,ze1+ze2);
	vec1=answer;
}
void vecmul(myvec  &vec1,unsigned int num)
{
	int ix1=vec1.size();
	for(int j=0;j<ix1;j++)
	{
		vec1[j]*=num;
	}
	vecset(vec1);
}
int main()
{
	unsigned int n,s=1;
	char p[20];
	cout<<"\t\t求阶乘!\n\n"<<"输入N：";
	cin>>n;
	cout<<endl;
	_itoa(n,p,10);
	strcat(p,"!.txt");
	int t1=clock();
	myvec answer;
	answer.push_back(n);
	for(int i=1;i<n;i++)
	{
		vecmul(answer,i);
		if(!(i%(n/10))||i==n-1)
		{
			static i=1;
			cout<<"\b\b\b";
			cout<<10*(i++)<<"%";
		}
		
	}
	int t2=clock();
	cout<<"\n\n计算时间："<<t2-t1<<"ms"<<endl;
	ofstream fout(p);
	if(!fout)
	{
		cout<<"文件打开失败!";
	}
	fout<<"计算时间："<<t2-t1<<"ms"<<endl;
	fout<<n<<"!=\n";
	fout<<answer[answer.size()-1]<<' ';
	for(int j=answer.size()-2;j>=0;j--)
	{
		
		fout.width(4);
		fout.fill('0');
		fout<<answer[j]<<' ';
		if(!(j%15))
			fout<<endl;
		
	}
	cout<<"\n结果已写入文件，按任意键退出...";	
	rewind(stdin);
	getchar();
	return 0;
}