hrefspace

 找回密码
 立即注册
搜索
热搜: PHP PS 程序设计
查看: 310|回复: 0

关于大数阶乘的程序实现

[复制链接]

481

主题

481

帖子

1465

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1465
发表于 2023-9-25 19:55:46 | 显示全部楼层 |阅读模式
本帖最后由 最后一片落叶 于 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改成其他的数就可以了。这个程序肯定不是最优的,希望大家一起讨论。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|hrefspace

GMT+8, 2024-11-1 09:20 , Processed in 0.057036 second(s), 21 queries .

Powered by hrefspace X3.4 Licensed

Copyright © 2022, hrefspace.

快速回复 返回顶部 返回列表