本帖最后由 最后一片落叶 于 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改成其他的数就可以了。这个程序肯定不是最优的,希望大家一起讨论。 |