易码技术论坛

 找回密码
 加入易码
搜索
查看: 669411|回复: 11

如何计算超大N的阶乘,N<100000   C;C++

[复制链接]
发表于 2007-4-26 13:00:42 | 显示全部楼层
就是一个递归算法应该可以搞定了......
具体代码自己想吧......^ ^
 楼主| 发表于 2007-4-30 05:20:10 | 显示全部楼层
不明白。溢出问题如何解决?
发表于 2007-4-30 22:39:15 | 显示全部楼层
如果不嫌慢的话,既然不用long、int之类的语句来定义数据(显然不够长),我认为可以用一个数组来储存数据的各个位(个、十、百、千、万.....),再写一个函数来模拟程序储存数据的过程。
发表于 2007-5-1 16:59:15 | 显示全部楼层
概率论里有一个斯特林公式:
n!≈Sqrt((2*π*n)*(n/e)^n)
n很大,且精确度要求不高时可以一试。
π=3.1415926535897……
e=2.7182818283……
发表于 2007-5-1 19:39:35 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
发表于 2007-5-1 21:22:38 | 显示全部楼层
高精度计算速度比较慢的,可以实现

数字实在是太大了
发表于 2007-5-1 21:29:05 | 显示全部楼层
找了段代码
  1.   /**///////////////////////////////////////////////////////////////////////////
  2.   //    Date created:   2005/07/12
  3.   //    Author:      Confach Zhang
  4.   //    Purpose:      计算n!的值
  5.   /**///////////////////////////////////////////////////////////////////////////
  6.   
  7.    
  8.   using namespace std;
  9. #include "StdAfx.h"
  10. #include <iostream.h>
  11. #include <conio.h>
  12. #include <stdlib.h>
  13. #include <math.h>
  14. #include <stdio.h>
  15. #include <iomanip.h>
  16.   
  17. int GetNumber();                        //输入 n
  18. int GetBitLength(int n);                  //求n!的位数
  19. char* Initialize(int);                    //初始化存储结果的值
  20. void PrintValue(char *a,int size);            //打印值到屏幕
  21. void PrintValue(char *a,int size,char* fileName);  //打印值到文件
  22. char* GetValue(int val);                  //计算
  23. char* SubGetValue(char* ,int);               
  24. int main()
  25. {
  26.     int value=GetNumber();
  27.     char fileName[16];
  28.     int size=GetBitLength(value);
  29.     char *pa = Initialize(size);
  30.     //pa=GetValue();
  31.     pa=GetValue(value);
  32.     PrintValue(pa,size);
  33.     //sprintf(fileName,"%s","10000!.txt");
  34.     sprintf(fileName,"%d!.txt",value);
  35.    
  36.     PrintValue(pa,size,fileName);
  37.     delete []pa;  //note:
  38.     return 1;
  39. }
  40. //函数GetValue
  41. // 求得计算结果
  42. //返回结果
  43. //History:
  44. //1)char* GetValue()
  45. //2)GetValue(int val)
  46. //  参数:val 计算阶乘的值
  47. char* GetValue(int val)
  48. {
  49.     //定义一个数组存储阶乘的值
  50.     //首先得到10000!阶乘的位数
  51.     int VALUE=val;
  52.     int length=GetBitLength(VALUE);
  53.     char *arrValue = new char[length];
  54.     if(!arrValue) {
  55.       cout <<"申请内存失败!" << endl;
  56.       exit(1);
  57.     }
  58.     arrValue[0] = 1;
  59.     for(int i=1; i<length; i++)
  60.       arrValue[i] = 0;
  61.     arrValue=SubGetValue(arrValue,VALUE);
  62.     return arrValue;
  63. }
  64. char* SubGetValue(char* arrValue,int n)
  65. {
  66.     int index=0;
  67.     long carrier=0;
  68.     double bitCount = 1;
  69.     int begin = 0;
  70.   
  71.     for(index=2; index<=n; ++index)
  72.     {
  73.       long multiValue = 0;  
  74.       bitCount += log10((long double)index);
  75.       if(arrValue[begin] == 0)
  76.          begin++;
  77.   
  78.       for(int j=begin; j<int(bitCount); ++j)
  79.       {
  80.          multiValue += (index*arrValue[j]);
  81.          arrValue[j] = char(multiValue % 10);
  82.          multiValue /= 10;
  83.       }
  84.     }
  85.   return arrValue;
  86. }
  87. //得到计算阶乘的值,此函数为新增
  88. int GetNumber()
  89. {
  90.     int n;
  91.     cout << "请输入要计算阶乘的n值: ";
  92.    cin >> n;
  93.    while(n < 0) {
  94.       cout << "输入错误,请重新输入: ";
  95.       cin >> n;
  96.    }
  97.    if(n == 0)
  98.       exit(1);
  99.    return n;
  100. }
  101. //函数GetBitLength
  102. // 求得计算结果的位数,本函数为新增加
  103. //参数
  104. //    n 需要计算的阶乘的数
  105. //返回结果的位数
  106. int GetBitLength(int n)
  107. {
  108.    double sum = 1.0;
  109.    for(int i=1; i<=n; i++)
  110.       sum += log10((long double)i);
  111.    return int(sum);
  112. }
  113. //-----------
  114. //函数:Initialize
  115. //  初始化存储结果的数组
  116. //参数:
  117. //    size    数组的长度  
  118. //返回值
  119. //   初始化后的数组
  120. //-------------
  121. char * Initialize(int size)
  122. {
  123.    char *arrValue = new char[size];
  124.    if(!arrValue) {
  125.       cout << size<<"太大,申请内存失败!" << endl;
  126.       exit(1);
  127.    }
  128.    arrValue[0] = 1;
  129.    for(int i=1; i<size; i++)
  130.       arrValue[i] = 0;
  131.    return arrValue;
  132. }
  133.   
  134. //-----------
  135. //函数:PrintValue
  136. //  将结果输入到屏幕上
  137. //参数:
  138. //    buff    存储结果的数组
  139. //  buffLen  数组的长度
  140. //  fileName  文件名      
  141. //-------------
  142. void PrintValue(char *buff, int buffLen)
  143. {
  144.    int bit = 0;
  145.    int nCol=0;
  146.    for(int i=buffLen-1; i>=0; i--) {
  147.       if(bit % 10 == 0)
  148.       {
  149.         cout << " " ;
  150.         nCol++;
  151.         if(nCol==10)cout<<endl;
  152.       }
  153.        cout << int (buff[i]);  
  154.       bit++;
  155.    }
  156.    cout << endl;
  157.    
  158. }
  159. //-----------
  160. //函数:PrintValue
  161. //  将结果输入到一个文件中
  162. //参数:
  163. //    buff    存储结果的数组
  164. //  buffLen  数组的长度
  165. //  fileName  文件名      
  166. //-------------
  167. void PrintValue(char *buff,int buffLen,char *fileName)
  168. {
  169.     int bit = 0;
  170.    int nCol=0;
  171.    FILE *fp=NULL;
  172.    //-----------------------------
  173.    if (fileName==NULL)      return ;
  174.   fp=fopen(fileName,"wt");
  175.    if (fp==NULL)
  176.    {
  177.       printf("不能创建文件%s",fileName);
  178.       return ;
  179.    }
  180.    for(int i=buffLen-1; i>=0; i--)
  181.    {
  182.       fprintf(fp,"%d",int(buff[i]));
  183.       
  184.       if(bit % 9 == 0)
  185.       {
  186.         fprintf(fp,"%s"," ");
  187.         nCol++;
  188.         if(nCol==8)
  189.         {
  190.           fprintf(fp,"%s","\n");
  191.           nCol=0;
  192.         }
  193.       }
  194.       bit++;
  195.       
  196.   }
  197.    fprintf(fp,"\n");
  198.    fclose(fp);
  199. }
复制代码
发表于 2007-6-5 18:37:25 | 显示全部楼层
循环+高精 Ac
发表于 2007-6-5 22:26:00 | 显示全部楼层
好长.......
发表于 2007-6-5 22:28:55 | 显示全部楼层
编出来机子用得上吗
发表于 2007-6-5 22:30:41 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
 楼主| 发表于 2007-4-17 11:33:37 | 显示全部楼层 |阅读模式
如何计算超大N的阶乘,N<100000

C;C++都可以
您需要登录后才可以回帖 登录 | 加入易码

本版积分规则

Archiver|手机版|小黑屋|EMAX Studio

GMT+8, 2024-3-29 02:29 , Processed in 0.011274 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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