一个较大的数的阶乘，怎么解决啊！ - 编程论坛

#2

newyj2008-03-24 19:51

昨天我也在做这道题呢

#3

zjl1382008-03-24 22:31

这个可以用数组来解决吧，我明天来研究一下，没写过，呵呵！
不过我算法不大行，刚学数据结构一个月，可能做不出来。就算写出来也应该是没什么效率吧，肯定很耗内存的。

#4

PcrazyC2008-03-25 09:10

自己在论坛搜这帖,都不知道发了多少次了

#5

gehouse2008-03-25 13:28

可以利用拆分成字符的方法来解决

#6

handongxue2008-03-25 14:44

主要思想如下

分配一动态内存 int *pout=new int[n];用以存储结果
其中n的计算如下：
int n;double temp=0;
for(double i=1;i<=100;i++)
temp+=log10(i);
n=int(temp+1);

剩下的就是算法的设计了

#7

afraidhlq2008-03-25 18:12

谢谢，好像有人写过一个任意大数加减乘除的类可能有用，我搜来看看

#8

elegant872008-03-25 19:48

c++代码

1！＋...＋100！
int main()
{
double s,t;
s=1.0;
t=1.0;
int i;
for(i=1;1<=100;i++)
{ t=t*i;
s=s+t;
}
cout<<"the sum is "<<s<<endl;
return 0;
}

#9

handongxue2008-03-25 23:18

回复楼上

这个题目考察的是数据结构和算法的设计，不仅仅是简单的循环。如果计算1000，10000等更大数的阶乘，则楼上的方法是不可以的。

#10

handongxue2008-04-09 00:43

刚刚写出来（要用标准c++编译器）

//求一个大数的阶乘

#include <iostream>
#include <fstream>

#include <cmath>
#include <vector>
#include <ctime>
using namespace std;

int zhi(int a,size_t i)  //判断一个整数的第i位的值，从后往前。
{
    size_t m=size_t( log10(double(a)) +1);  //a的位数
    if(i>m || i==0) return 0;

    for(size_t j=1;j<i;j++)
        a=a/10;

    return a%10;
}

void fact(int n)
{
    clock_t t=clock();  //计算所花费的时间。

    bool not_plus=1;
    double m=0;
    for(double i=1;i<=n;i++)
        m+=log10(i);

    size_t s=size_t(m+1),templen=1;

    vector<int> c(s),ctemp(s); c[s-1]=1;

    for(int i=1;i<=n;i++)    //1*2*3.....*99*100
    {
        size_t clen=templen,
               nwide=size_t(log10(double(i))+1);   //判断i的位数

        for(size_t j=1; j<= nwide; j++)  //j代表i的某位
        {
            int x=zhi(i,j),
                ckv=0,  ckj=0,  cky=0,
                ctkv=0, ctkj=0, ctky=0;

            for(size_t k=1;k<=clen;k++)
            {
                ckv=x*c[s-k]+ckj;   //x与c每位相乘再加上进位的值。
                cky=ckv%10;
                ckj=ckv/10;

                ctkv=ctemp[s-k-j+1]+cky+ctkj;
                ctky=ctkv%10;
                ctkj=ctkv/10;

                ctemp[s-k-j+1] = ctky;
            }

            if(j>1 && not_plus) templen++;


            if(ckj>0 || ctkj>0)
            {
                ctemp[s-clen-j]+=ckj+ctkj;  //
                templen++;
                not_plus=0;

            }
            else
                not_plus=1;

        }

        c.swap(ctemp);
        ctemp.assign(s,0);

    }

    ofstream fout("jiecheng.txt");
    if(!fout.is_open())
    {
        cout<<"can't open file jiecheng.txt"<<endl;
    }

    cout<<"\n\n所计算"<<n<<"的阶乘如下(已存为文件)：\n\n";
    fout<<"\n\n所计算"<<n<<"的阶乘如下：\n\n";

    fout<<"结果的位数为：m=="<<int(m+1)<<endl<<endl;
    cout<<"结果的位数为：m=="<<int(m+1)<<endl<<endl;

    for(size_t i=0;i<s;i++)
    {
        if(i%5==0) fout<<ends<<ends;
        if(i%30==0) fout<<endl;
        fout<<c[i]<<ends;
    }
    fout<<endl<<endl;

    for(size_t i=0;i<s;i++)
    {
        if(i%5==0) cout<<ends<<ends;
        if(i%30==0) cout<<endl;
        cout<<c[i]<<ends;
    }
    cout<<endl<<endl;

    t=clock()-t;

    fout<<"计算所花费的时间为："<<t/1000<<"  秒.\n\n\n";
    cout<<"计算所花费的时间为："<<t/1000<<"  秒.\n\n\n";

    fout.close();
}

int main()
{
    cout<<"阶乘计算器....\n\n";
    int a;
    cout<<"Please input a number:\n    a==";
    cin>>a;
    fact(a);

    cin>>a;


}