当n非常非常大时（比如为1万），求n!问题的学习，解答和疑问。
欢迎转载，但请标明作者 “九天雁翎”，当然，你给出这个帖子的链接更好。
首先说明，这本来是钱能C++程序设计习题及解答中的一个习题。也就是在自然数范围内求n!，其实用他的方法还不能说在自然树范围内，按他的方法，不考虑机子性能，最多可以算到2^32-1（32位机），原题解答如下：
程序1：
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
using namespace std;
//--------------------------------------------------------------------
int getN();
int getBitNum(int n);
char *init(int size);
void calc(char *a,int n);
void display(char *a,int size);
//--------------------------------------------------------------------
int main()
{
int n = getN();
int size = getBitNum(n);
char *pa = init(size);
calc(pa,n);
display(pa,size);
delete []pa;
return 0;
}
//----------------------------------------------------------------------
int getN()
{
int n;
cout <<"请输入n!中的n:";
cin >>n;
while(n<0)
{
cout <<"输入有错，请重输：";
cin >>n;
}
if(n == 0)
exit(1);
return n;
}
//--------------------------------------------------------------------
int getBitNum(int n)
{
double sum = 1.0;
for(int i = 1;i <= n;++i)
sum += log10(double(i));
return int(sum);
}
//--------------------------------------------------------------------
char *init(int size)
{
char *pa = new char[size];
if(!pa)
{
cout<<"Too large factor of"<<size<<endl;
exit(1);
}
pa[0] = 1;
for(int i = 1;i <size;++i)
pa[i] = 0;
return pa;
}
//--------------------------------------------------------------------
void calc(char *a,int n)
{
double bitcount = 1;
int begin = 0;
for(int i = 2;i <= n;++i)
{
long and = 0;
bitcount += log10(double(i));
if(a[begin] == 0)
++begin;
for(int j = begin;j < int(bitcount); ++j)
{
and += i * a[j];
a[j] = char(and % 10);
and /= 10;
}
}
}
//--------------------------------------------------------------------
void display(char *a,int size)
{
int bit = 0;
for(int i = size - 1;i >= 0; --i)
{
if(bit % 50 == 0)
cout <<endl<<"第"<<setw(3)<<(bit/50+1)<<"个50位:";
cout <<(int)a[i];
++bit;
}
cout <<endl;
}
//--------------------------------------------------------------------
程序的运行效率和结构化设计都很不错，这里赞一句清华大学钱能教授的C语言编程水平，注意，仅仅是佩服他的C语言编程水平而已，这根本就不能算是一个好的C++程序，虽然他是在一个C++教程里面给出来的。我把自己按他的算法重新编写了代码，没有他那么好看了，但是因为int明显是正的，所以用了unsigned类型的size_t，这样就让n可接受的范围到了2^32-1。
程序2：
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
using namespace std;
size_t getbit(const size_t &aN);
void init(unsigned char *p,size_t &am);
void compute(unsigned char *p,const size_t &an);
void print(unsigned char *p,const size_t &am);
int main()
{
cout <<"Input the /"n/" you want to compute:";
size_t n;
cin >> n;
if(n == 0) //检验输入
{
cerr<<"Please input a integer more than zero."<<endl;
}
size_t m = getbit(n);
unsigned char *pn = new unsigned char[m];
if(!pn) //检验空间分配
{
cerr<<"The factor is too big."<<endl;
}
init(pn,m); //初始化
compute(pn,n); //计算n!
print(pn,m); //输出
delete []pn;
return 0;
}
//-----------------------------------------------------------
size_t getbit(const size_t &aN)
{
double sum = 1.0;
for(size_t i = 1;i<=aN;++i)
{
sum+=log10(double(i));
}
return size_t(sum);
}
//------------------------------------------------------------
void init(unsigned char *p,size_t &am)
{
p[0]=1;
for(size_t i = 1;i != am;++i)
{
p[i] = 0;
}
}
//------------------------------------------------------------
void compute(unsigned char *p,const size_t &an)
{
double bitcount = 1.1;
size_t begin = 0;
for(size_t i = 2;i<=an;++i)
{
size_t and = 0;
bitcount +=log10(double(i));
if(p[begin]==0)
++begin;
for(size_t j = begin ; j < size_t(bitcount);++j)
{
and += i * p[j];
p[j] = unsigned char(and % 10);
and /= 10;
}
}
}
//----------------------------------------------------------------
void print(unsigned char *p,const size_t &am)
{
size_t bit = 0;
for(size_t i = am;i != 0;--i)
{
if(bit % 50 == 0)
cout <<endl<<"第"<<setw(3)<<(bit/50+1)<<"个50位:";
cout << size_t(p[i-1]);
++bit;
}
cout<<endl;
}
我这里几乎都继承了钱能的算法，哪怕结构都差不多，仅仅是改变成了unsigned，可是竟然有问题，在运行时，当n比较小时（如50），有的时候会出错，大的时候反而不会（比如1000，2000），不知道是为什么。为了方便以后的使用，并体现一点C++的精神，我把这个程序作成一个类，就变成下面这样.
程序3：
Factor.h:
#pragma once
typedef unsigned char unchar;
class Factor
{
size_t n; //求n的n!
size_t m; //n!有多少位
unchar *pc; //动态分配的数组指针
private:
void getbit();
void compute(); //计算n!
void init();
Factor(Factor &);
public:
void print()const; //输出
Factor(const size_t &);
~Factor(void);
};
Factor.cpp
#include "Factor.h"
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
Factor::Factor(const size_t &nval)
{
if(nval == 0) //检验输入
{
cerr<<"Please input a integer more than zero."<<endl;
}
n = nval;
init();
}
Factor::~Factor()
{
delete []pc;
}
void Factor::init()
{
getbit();
pc = new unchar[m];
if(!pc) //检验空间分配
{
cerr<<"The factor is too big."<<endl;
}
pc[0]=1;
for(size_t i = 1;i < m;++i)
{
pc[i] = 0;
}
compute();
}
void Factor::getbit()
{
double sum = 1.0;
for(size_t i = 1;i<=n;++i)
{
sum+=log10(double(i));
}
m = size_t(sum);
}
//------------------------------------------------------------
void Factor::compute()
{
double bitcount = 1.1;
size_t begin = 0;
for(size_t i = 2;i<=n;++i)
{
size_t and = 0;
bitcount +=log10(double(i));
if(pc[begin]==0)
++begin;
for(size_t j = begin ; j < size_t(bitcount);++j)
{
and += i * pc[j];
pc[j] = unchar(and % 10);
and /= 10;
}
}
}
//----------------------------------------------------------------
void Factor::print()const
{
size_t bit = 0;
for(size_t i = m;i != 0;--i)
{
if(bit % 50 == 0)
cout <<endl<<"第"<<setw(3)<<(bit/50+1)<<"个50位:";
cout << size_t(pc[i-1]);
++bit;
}
cout<<endl;
}
main.cpp
#include "Factor.h"
#include <iostream>
using namespace std;
int main()
{
size_t anum;
cout<<"Input the number you want to compute:";
cin >>anum;
Factor a(anum);
cout<<"the "<<anum<<"! is:"<<endl;
a.print();
return 0;
}
主程序仅仅是用来测试，这个类可以比较好的计算n!，问题是还是有些类似程序2的问题，我也是很困惑，难道是因为用了无符号的问题？因为这2个程序和原题答案这是个最大的区别，其他几乎一样。然后我为了用上C++的STL特性，编写了如下代码：
程序4：
Factor.h:
#pragma once
#include <vector>
class Factor
{
size_t n; //求n的n!
std::vector<size_t> vec; //储存结果的vector
private:
void compute(); //计算n!
void init();
Factor(Factor &);
public:
void print(); //输出
Factor(const size_t &);
~Factor(void);
};
Factor.cpp
#include "Factor.h"
#include <iostream>
#include <cmath>
#include <cmath>
#include <iomanip>
using namespace std;
typedef vector<size_t>::iterator iter;
Factor::Factor(const size_t &nval)
{
if(nval == 0) //检验输入
{
cerr<<"Please input a integer more than zero."<<endl;
}
n = nval;
compute();
}
Factor::~Factor()
{
}
//------------------------------------------------------------
void Factor::compute() //这个最主要的函数有问题
{
vec.push_back(1);
for(size_t i = 2;i<=n;++i)
{
size_t and = 0;
for(iter it = vec.begin();it != vec.end();) //每次都计算了end()，但是还是出错，不知道为什么
{
and += i * (*it);
*(it++) = and % 10;
if(and /= 10)
if(it == vec.end())
{
vec.push_back(0); //知道这个操作会改变容器
continue;
}
}
}
}
//----------------------------------------------------------------
void Factor::print()
{
size_t bit = 0;
for(iter it = vec.end();it != vec.begin();--it)
{
if(bit % 50 == 0)
cout <<endl<<"第"<<setw(3)<<(bit/50+1)<<"个50位:";
cout << size_t( *(it-1) );
++bit;
}
cout<<endl;
}
这个程序利用了vector容器的动态添加，不需要一次添加那么多，不过感觉执行效率也许并比不上一次添加那么多，不过程序的大部分理解起来要更简单了，比如不需要提前用对数算好需要多少空间，这可以减轻很多负担，特别是根本不知道怎么算的时候，但是这样做付出了代价，就是主运算函数明显更加复杂，因为你还要在循环里面动态处理vector，我就是在这个里面出了问题，请高人给我一些提示。
Posted By 九天雁翎 at 九天雁翎的博客 on 2007年05月03日