关于大数阶乘的程序实现
本帖最后由 最后一片落叶 于 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 128void main(){ clock_tstart, end; start= clock(); staticlong int r={1}; inti,j; intk=0,l=0; for(i=1;i<=M;i++) { for(j=0;j<=l;j++) { r=r*i+k; k=r/1000; r=r%1000; } if(k!=0) { l++; r=k; k=0; } j=l; cout<<i<<"!="<<r; for(;j>=0;j--) { cout<<","; cout<<setw(3)<<setfill('0')<<r; } cout<<endl; } end= clock(); cout<<"Runtime: "<<(double)(end - start) /CLOCKS_PER_SEC<<"S"<<endl; }
这个程序计算的是128的阶乘。这个数已经很大了。想计算其他的值，将128改成其他的数就可以了。这个程序肯定不是最优的，希望大家一起讨论。
页:
[1]