九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

当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,我就是在这个里面出了问题,请高人给我一些提示。
 

分类:  C++ 
标签:  C++ 

Posted By 九天雁翎 at 九天雁翎的博客 on 2007年05月03日

分享到:

前一篇: 别让习惯害了你,注意size_t变量作循环条件时,逆序是不可行的! 后一篇: 浅谈C++类(8)--重载输入输出操作符