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

别让习惯害了你,注意size_t变量作循环条件时,逆序是不可行的!

欢迎转载,但请标明作者 “九天雁翎”,当然,你给出这个帖子的链接更好。

在自己编写求自然数内n的n!时碰到的问题。

#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 - 1;i >= 0;--i)
 {
  if(bit % 50 == 0)
   cout <<endl<<"第"
   <<setw(3)<<(bit/50+1)<<"个50位:";
  cout << size_t(p[i]);
  ++bit;
 }
}
首先声明的是,我是在学习用数组处理这个问题,所以没有用vector,而是动态分配了数组,求位数用的是(n!=10^M)估算算法,每一位只保存结果的一位,为了节省空间用unsigned char保存一位数,在在vc2005下编译通过了,不过运行却得不出结果,还有假如在最后把输出的for(size_t i = am;i >= 0;--i)改为
for(int i = am;i >= 0;--i),结果会好一点,但是还是得不出正确结果,正准备找高手说明下问题。还有用size_t为什么似乎会导致这里的死循环,而int不会?
最后我发现,把print()定义成这个样子,反而又可以。所以比较肯定的说是输出函数的问题,但是我实在不知道是什么问题。
void print(unsigned char *p,const size_t &am)
{
 cout <<size_t(p[2])<<size_t(p[1])<<size_t(p[0])<<endl;
}

最后我老实编了一个正常简单的逆序循环发现也不可以,我刚开始甚至还怀疑是不是size_t就没有正常的“--”自减运算符,然后编小程序证明不是,而且在循环条件〉=3,2,1时都没有问题,就到了大于0就不行了,我这时才突然醒悟过来,其实size_t 就是unsigned int啊,一个没有符号的整数在C++里面就意味着一个永远为正的数,我的行为就像是等一个数的绝对值,一个数开2次方根,一个数的平方去小于零一样可笑!呵呵,大家可不要犯我一样的错误啊。然后我把print()改成下面这个样子后,果然一切都正常了。

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;
}

 

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

Posted By 九天雁翎 at 九天雁翎的博客 on 2007年04月30日

前一篇: 警惕!C++里面“=”不一定就是等于(赋值)。 后一篇: 当n非常非常大时(比如为1万),求n!问题的学习,解答和疑问。