易码技术论坛

 找回密码
 加入易码
搜索
查看: 3583|回复: 20

[源码] 【C语言】求n阶乘核心代码附完全代码

[复制链接]
发表于 2008-4-11 14:38:24 | 显示全部楼层 |阅读模式
        公开并不优秀甚至垃圾的代码实属情非得已,的目的是请手指点,如何才能实现动态内存分配,就是在程序开始运行后根据将要计算的数值大小来分配需要的内存而不用一开始就分配很大的内存,这样在计算比较小的数的阶乘时会比较浪费内存,我也曾考虑过链表,但好像不能用链表来实现,请高手将修改后的代码或修改的思路或别人写的比较优秀的代码发给我,不盛感激。

        受论坛限制,这里只发核心代码,附件里有全部代码。

  1. #define   CAPACITY  100000             //宏定义存储容量,可根据需要修改
  2. #define   ACCURACY  30                 //宏定义结果显示精度,结果位数超过该值则自动采用科学计数法

  3. #include  "conio.h"                    //getch函数头文件
  4. #include  "stdlib.h"                   //system用到的头文件

  5. void GetFactorial(long *a,long n);     //n>12时计算阶乘
  6. long GetRemainder(long n);             //n<=12时的计算阶乘,因为long型最大只能容纳12的阶乘
  7. void Print(long n);                    //输出计算结果到屏幕
  8. long GetPosition(long *a);             //结果在数组中的存储起始位置确定函数

  9. long num;                              //要求阶乘的数
  10. long stor=1;                           //n<=12时存储结果,因为long型最大只能容纳12的阶乘
  11. long storage[CAPACITY]={0};            //n>12时存储结果

  12. void main()
  13. {
  14.     system("cls");                     //系统清屏命令
  15.     printf("\n请输入一个数:");
  16.     scanf("%ld",&num);
  17.     if(num<0)                          //虽然科学家已经将阶乘从自然数扩展到了有理数,但此处不提供负数阶乘的计算
  18.     {
  19.         printf("\n您的输入错误!\n");
  20.         exit(0);
  21.     }
  22.     else
  23.     {
  24.         if(num<=12)
  25.             stor=GetRemainder(num);           //<=12的数用GetRemainder函数计算,因为long型最大只能容纳12的阶乘
  26.             else
  27.             GetFactorial(storage,num);        //当要计算的数>12时用GetFactorial函数计算
  28.         Print(num);                           //计算完成后向屏幕输出结果
  29.     }
  30.     system("pause");                          //系统命令:提示信息
  31.     getch();                                  //程序暂停,没有的话整个程序运行一晃而过看不见输出结果
  32. }
  33. long GetRemainder(long n)                     //num<=12时用来计算阶乘
  34. {
  35.     int i=2;
  36.     long s=1;
  37.     while(i<=n)
  38.         s*=i++;
  39.     return(s);
  40. }
  41. void GetFactorial(long *a,long n)         //num>12时用来计算阶乘
  42. {
  43.     register int i;                       //因为i、j要频繁的用到所以定义为寄存器变量
  44.     register long j;
  45.     long former_address,carry;            //former_address用来存储数组每一位与n相乘后的结果,carry用来存储后位给前位的进位
  46.     long m=479001600;                     //12的阶乘
  47.     int p,s=CAPACITY-9;                   //s用来记录这次计算后应该比前次向高位多扩展多少位数,p用来记录到底应该向高位扩展多少位
  48.     for(i=CAPACITY-1;i>=CAPACITY-9;i--)   //用m也就是479001600来初始化storagr数组,因为任何>12的数的阶乘要以12的阶乘为基础进行计算
  49.     {
  50.         a=m%10;                        //将m对10求余的第一次结果保存到storage的最后一个元素
  51.         m/=10;                            //将m除10后仍保存在m
  52.     }
  53.     for(j=13;j<=n;j++)                    //真正>12的阶乘计算开始了
  54.     {
  55.         p=0;
  56.         carry=j;
  57.         while(carry%10)                   //通过上次结果的最高位向更高位进位的多少来决定下次遍历要向数组低位移动多少位
  58.         {
  59.             carry/=10;
  60.             p++;
  61.         }
  62.         s-=(p+1);                         //以防扩展不够所以多扩展一位
  63.         carry=0;                          //最低位不能接受进位
  64.         for(i=CAPACITY-1;i>=s;i--)
  65.         {
  66.             a*=j;                      //用j乘以storage的每一个有效元素(之所以说“有效”是因为自始至终都有元素没有参加到计算中来)结果仍存储在原位置
  67.             former_address=a+carry;    //本位的数加上低位的进位赋给former_address,作为向高位进位和本位保留的依据
  68.             carry=former_address/10;          //将former_address中个位以上的部分交给carry,让它在下次运算时将这个数进给高位
  69.             a=former_address%10;           //将former_address的个位数字交回给原来的位置
  70.         }
  71.     }
  72. }
  73. void Print(long n)                           //打印结果到屏幕
  74. {
  75.     register int i,j;                        //凡是频繁用到的变量我们都将它定义为寄存器变量
  76.     int signifcant_digits,decimal_point;     //signifcant_digits用来控制小于显示精度的有效位数,即使你将精度位数设的再大程序也不会输出计算结果末尾无意义的0
  77.     decimal_point=0;                         //decimal_point是小数点的控制开关,为0时将不输出小数点
  78.     printf("\n%ld!=",n);
  79.     if(n<=12)
  80.             printf("%ld\n",stor);                //当n<=12时直接打印long型数据stor的值
  81.     else
  82.     {
  83.             i=GetPosition(storage);              //再次强调storage数组不是每个元素都保存着计算结果,所以此处要用GetPosition函数来获得结果开始的位置
  84.             if(CAPACITY-i<=ACCURACY)             //如果计算结果的位数<=输出精度的时候程序将从结果起始位置开始逐个输出storage中的元素值
  85.             while(i<CAPACITY)
  86.                     printf("%ld",storage[i++]);
  87.             else                                 //当输出精度<计算结果位数时输出就没有上面那么简单
  88.             {
  89.                 printf("%ld",storage);
  90.                 signifcant_digits=i+ACCURACY-1;
  91.                 for(j=i+1;j<i+ACCURACY;j++)      //获得实际有效位数及小数点开关值
  92.                     if(storage[j]!=0)
  93.                     {
  94.                         signifcant_digits=j;
  95.                         decimal_point=1;
  96.                     }
  97.                 if(decimal_point)
  98.                 printf(".");
  99.                 for(j=i+1;j<signifcant_digits;j++)               //按比控制精度少一位来打印结果,不全打印是因为最后一位要4舍5入
  100.                     printf("%ld",storage[j]);
  101.                 if(storage[signifcant_digits+1]>4)               //根据控制精度的下一位确定控制精度最后一位是否需要进位
  102.                         printf("%ld",storage[signifcant_digits]+1);
  103.                 else
  104.                     printf("%ld",storage[signifcant_digits]);
  105.                 printf("e+%d",CAPACITY-i-1);                     //最后打印科学记数法的指数部分
  106.             }
  107.     }
  108.     printf("\n");
  109. }
  110. long GetPosition(long *a)                  //获得计算结果在数组中的起始位置
  111. {
  112.     long i=0;
  113.     while(i<=CAPACITY)                     //遍历数组元素,当发现第一个不为0的数字立即退出循环
  114.         if(a[i++]!=0)
  115.             break;
  116.     return i-1;                            //将第一个不为0的数字的序号返回
  117. }
复制代码

[ 本帖最后由 CJJR 于 2008-5-1 19:08 编辑 ]

N阶乘5_1.rar

3.84 KB, 下载次数: 371

发表于 2008-4-11 15:08:39 | 显示全部楼层
代码走样了
提供一个txt文件吧
 楼主| 发表于 2008-4-11 15:28:09 | 显示全部楼层
感谢提示,已加入。
发表于 2008-4-11 18:09:22 | 显示全部楼层
估计只有ACM才会出这样的题
发表于 2008-4-17 11:03:00 | 显示全部楼层
你利用对数计算一下238609294!是多少位数先。。。
在n大于某个数的时候用这个算法已经失去意义了(太慢)
如果n不是很大,可以考虑一下10000进制。
发表于 2008-4-17 22:41:27 | 显示全部楼层
汗,纯数学搞理论的说不定有用。
发表于 2008-4-18 08:19:34 | 显示全部楼层
用十进制算很符合人的思路,但不符合计算机的思路
要想快,用二进制
发表于 2008-4-18 10:51:05 | 显示全部楼层
猛一看以为是我写的……汗
开个玩笑。
发表于 2008-4-18 14:48:23 | 显示全部楼层
倒是可以弄个bigInt的库。。
发表于 2008-4-18 15:05:41 | 显示全部楼层
恩。
我有一个支持1024位整数的库
 楼主| 发表于 2008-4-18 18:46:51 | 显示全部楼层
确实数字太大速度会很慢,理论最大为1932735283,我发现WINDOWS自带的计算器算这个也很慢,我在网上搜了一个代码特别短的程序也是求n! ,速度非常快,但是最大只能求到1000000!,而且答案不准确。
/******这是我在网上找到的*******/
#include   <stdio.h>   
#include   <math.h>   
#include   <stdlib.h>   
#include   <string.h>      
   
//   读浮点数的指数   
#define   get_exp(p)   (atoi(p+strlen(p)-3))   
   
main()   
{   
  unsigned  char  pr[100];   
  unsigned  long  n,re;   
  unsigned  long  register  i;   
  double  r;   

  while(1)
  {
     printf("input n:");   
     scanf("%ld",&n);   //n不是整数会死循环   
     if(!n)
        break;
     r=1.0;   
     re=0;   
     //开始计算   
     for(i=2;i<=n;i++)
     {
        r=r*i;
        if(r>=1.0e+300)   
        {   
           r=r/1.0e+300;   
           re=re+300;   
        }
     }
     sprintf(pr,"%d!=%.20e",n,r);   
     sprintf(pr+strlen(pr)-3,"%ld",get_exp(pr)+re);   
     printf("%s\n",pr);
  }
}

说实话,我看不懂这段代码的原理,希望大家指点迷津。
发表于 2008-4-18 19:08:15 | 显示全部楼层
11楼的代码就是暴力计算,没有啥说的,顺便指出.20应该改成.16
发表于 2008-4-18 19:12:22 | 显示全部楼层
原帖由 leesoft 于 2008-4-18 08:19 发表
用十进制算很符合人的思路,但不符合计算机的思路
要想快,用二进制

用二进制的话不方便输出
如果真的要做到快,可以考虑取一组两两互素的数.在能表示的范围内,任意两个数相乘都能够在至多O(n)的时间内乘出来.
如果是普通乘法,考虑FFT,两个k进制n位的乘法可以在O(n+eps)时间内计算.
发表于 2008-4-18 19:25:50 | 显示全部楼层
楼上好专业。
发表于 2008-4-18 22:13:08 | 显示全部楼层
用二进制会很快
至于输出问题,很简单:
用16进制输出非常容易,不论述了
用10进制可以连续除10求余,尽管慢了点,但比起用10进制求阶乘快对了
发表于 2008-4-19 10:25:24 | 显示全部楼层
怎么专业的数学.....
发表于 2008-4-19 22:19:46 | 显示全部楼层
二进制就是比10进制快
 楼主| 发表于 2008-4-20 11:17:15 | 显示全部楼层
谢谢大家的建议,请暂时不要给我提示,我要自己让它快起来。
发表于 2008-4-20 11:26:44 | 显示全部楼层
没必要重新发明轮子吧
 楼主| 发表于 2008-4-24 21:10:03 | 显示全部楼层
现在速度达到原来的3倍,但还是不够,LEE老大说的二进制还有bailiang说的什么俩俩互素的数都怎么弄啊?

[ 本帖最后由 CJJR 于 2008-4-24 21:11 编辑 ]
您需要登录后才可以回帖 登录 | 加入易码

本版积分规则

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

GMT+8, 2024-3-29 05:18 , Processed in 0.013722 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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