关于大数阶乘的程序实现

cfan2021

本帖最后由 最后一片落叶 于 2012-11-9 16:51 编辑

大数阶乘是一个有意思的话题。好像到目前为止，还没有一种方法适合任何的大数阶乘。我也是刚刚接触，觉得挺好玩。所谓的大数就是一个非常大的数，大到计算机不能直接表示，比如计算机只能表示100位的数，而我要求的最后结果可能有300位，那我必须利用只能表示100位的计算机求出300位的准确结果来。这是第一个难点。第二个是对速度的要求。速度不能太慢，算法要有效率。

阶乘估计大家都知道，就是一列数的乘积，符号用！表示。比如4的阶为：4！=4*3*2*1=24.
先写一个简单的求阶乘的程序。
#include "stdio.h"
#include "stdlib.h"

int main(int argc, char* argv[])
{
         long i,n,p;
         printf("n=?");
         scanf("%d",&n);
         p=1;
         for (i=1;i<=n;i++)
                  p*=i;
         printf("%d!=%d/n",n,p);
         return 0;
}
该程序用的循环求阶乘。
再来一个稍微改进一点的程序
#include   <iostream.h>   
  long   int   fac(int   n);   
  void   main()   
  {   
          int   n;   
          cout<<"input   a   positive   integer:";   
          cin>>n;   
          long   fa=fac(n);   
          cout<<n<<"!   ="<<fa<<endl;   
  }   
  long   int   fac(int   n)   
  {   
          long   int   p;   
          if(n==0)   p=1;   
          else   
              p=n*fac(n-1);   
          return   p;   
  }  
该程序用的递归求阶乘。
上面的两个程序都可以求阶乘，但你试一下就知道，只能求12以内的阶乘。当n的值大于12以后，运算结果就不对了。
因为这个时候结果的位数已经超过了int型的最大表示范围，想要继续计算，就要扩大表示范围，把int改为double。但这种方法只是一时的，因为n越来越大，最终也会超过double的表示范围。下面给出求大数阶乘的程序

#include<time.h>

#include<iostream>

using namespace std;

#include<iomanip>

#define N 1000

#define M 128

void main()

{

       clock_tstart, end;

       start= clock();

       staticlong int r[N]={1};

       inti,j;

       intk=0,l=0;

       for(i=1;i<=M;i++)

       {            

              for(j=0;j<=l;j++)

              {                  

                     r[j]=r[j]*i+k;                 

                     k=r[j]/1000;

                     r[j]=r[j]%1000;                    

              }

              if(k!=0)

              {

                     l++;

                     r[j]=k;

                     k=0;

              }

              j=l;

              cout<<i<<"!="<<r[j--];

              for(;j>=0;j--)

              {

                     cout<<",";

                     cout<<setw(3)<<setfill('0')<<r[j];

              }

              cout<<endl;

       }

       end= clock();

       cout<<"Runtime: "<<(double)(end - start) /CLOCKS_PER_SEC<<"S"<<endl;

      

}
这个程序计算的是128的阶乘。这个数已经很大了。想计算其他的值，将128改成其他的数就可以了。这个程序肯定不是最优的，希望大家一起讨论。