优化阶乘算法的探索

优化阶乘算法的探索优化阶乘算法的探索中国地质大学(武汉)  陈海丰 阶乘(factorial)是基斯顿·卡曼(ChristianKramp,1760–1826)于1808年发明的运算符号。阶乘,也是数学里的一种术语,是指从1乘以2乘以3乘以4一直乘到所要求的数。例如所要求的数是4,则阶乘式是1×2×3×4,得到的积是24,24就是4的阶乘。如果所要求的数是n,则阶乘式是1×2×3×……×n,设

大家好,又见面了,我是你们的朋友全栈君。

优化阶乘算法的探索

中国地质大学(武汉)   陈海丰

 

阶乘(factorial)是基斯顿·卡曼(Christian Kramp, 1760 – 1826)于1808年发明的运算符号。阶乘,也是数学里的一种术语,是指从1乘以2乘以3乘以4一直乘到所要求的数。例如所要求的数是4,则阶乘式是1×2×3×4,得到的积是24,24就是4的阶乘。如果所要求的数是n,则阶乘式是1×2×3×……×n,设得到的积是x,x就是n的阶乘。在表示阶乘时,就使用“!”来表示,如n阶乘,就表示为n!。
    根据阶乘的定义,我们不难得到求解阶乘的递推式。

            …………………………………(1)

当n值很小时,在计算机中可以直接用整型数据的运算就可以解决了,可是当n值很大,比如n=10000时计算结果就不能用现有的数据类型来存放了,因为它的位数已远远超过了现有的数据类型(如10000!有35660位)。为了解决所有数据类型都无法存放这样一个庞大的数据,目前大家采用的是将一个大数一位一位的存放到一个字符型数组或整型数组中,然后要运算时对其每一位进行单独运算,这样就解决了庞大数据的存放问题。但具体怎样对两个都比较大的数的作乘法运算呢?这就要利用大整数的高精度运算。如A,B都是位数比较多的大整数,现在要作A*B运算。小学时我们作45*12是先把12中的2与45的个位5相乘,再把2与45的十位4相乘,然后同样再把12中的1与45中的每一位从低到高依次相乘。在这里我们也可以模拟45*12,把A中每一位从低到高与B中的个位相乘,与后再与B中的十位相乘,依次类推,最后把所有的结果对应相加就可以得到所要求的结果了。

具体代码(一):

#include <stdio.h>

#include <string.h>

 

char a[40000], b[10];

int c[40000];

int main()

{    

    int n;

     while(scanf(“%d”, &n) != EOF){

        int la, lb, lc, i, j, k, k1;

        if(n == 0 || n == 1){

              printf(“1/n”);

              continue;

         } //几种特殊情况

        if(n == 2){

              printf(“2/n”);

              continue;

         }

        a[0] = 50;   //初始化使是最先相乘的数从开始

         for(k1 = 3;k1 <= n;k1++){                  

              k = k1;          

              for(j = 0;k;j++){

                   b[j] = k % 10 + 48;

                   k /= 10;

              }          

              la = strlen(a);

              lb = strlen(b);  

              memset(c, 0, sizeof(c));      

              for(i = 0;i < la;i++){

                   for(j = 0;j < lb;j++){          

                       c[i + j] += (a[i] – 48) * (b[j] – 48);

                       //循环相乘,结果存放到另一数组中         

                       c[i + j + 1] += c[i + j] / 10;   //进位         

                       c[i + j] %= 10;

                       lc = i + j + 1;   //当前位     

                   }

              }

              if(c[lc] == 0) lc–;    

              for(i = lc;i >= 0;i–)

                   for(i = lc;i >= 0;i–) a[i] = c[i] + 48;

                   //将结果复制到数组a中,再和b数组相乘

         }

         for(i = lc;i >= 0;i–){   //输出结果时从数组的最后一个开始输出

              printf(“%c”, a[i]);

        }

         printf(“/n”);    

         memset(a, 0, sizeof(a)); //将数组全部初始化

         memset(b, 0, sizeof(b));        

     }

     return 0;

}

上面程序可以计算大数的阶乘,但是效率非常的低,如10000!的阶乘需要2000Ms左右,所以这种算法并不能解决实际问题。考虑到上面的程序是一位一位的把一个大数存放下来,然后相乘时也是一位一位的进行的。然后我想到定义一个整型的数组,每一位不是存放一位而是存放五位,这样相加,相乘的次数就是原来的 ,10000!运算时间是200Ms,是原来的 。

具体代码(二):

 

#include<stdio.h>

 

int main()  

{    

     int n;

     printf(“请输入一个整数N(0~20000):/n”);    

     while(scanf(“%d”, &n) != EOF){      

         int s[16000] = {0}, j, i, k = 0, t = 0, p = 0;

         long sum = 0;        

         s[0] = 1;  

         for(j = 1;j <= n;j++){  

              for(i = 0;i <= t;i++){  

                   sum = s[i] * j + p;  

                   p = 0;  

                   if(sum > 99999){  

                       s[i] = sum % 100000;   //每一位存放位         

                       p = sum / 100000;          

                       if(t == i){

                            t++;

                            s[t] = 0;

                       }  

                   }  

                   else s[i]=sum;  

              }  

         }  

         printf(“%d!=”, n);

         printf(“%d”, s[t]);  

         for(i = t – 1;i >= 0;i–){    

              printf(“%05d”,s[i]);  

         }  

         printf(“/n/n”);

         printf(“请再输入一个整数N(0~20000):/n”);

     }  

     return 0;  

}

 

当然在程序中可以把存放大数的数组定义成长整型(long)则每一个数组元素可以存放更多位,10000!的运行时间可以缩短到50Ms。在实践中算法的可行性是非常重要的,算法要不断的优化才能有机实际作用,所以要学会优化算法,提高自己的编程能力。

 

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/cschf/archive/2008/05/28/2491623.aspx

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164010.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • MATLAB学习笔记 plotyy双y轴

    MATLAB学习笔记 plotyy双y轴一、线型设置:t=0:0.1:8;[ax,h1,h2]=plotyy(t,sin(t),t,cos(t));% plotyy(X1,Y1,X2,Y2):以左、右不同纵轴绘制X1-Y1、X2-Y2两条曲线。set(h1,’linestyle’,’-‘,’marker’,’o’,’color’,’r’);set(h2,’linestyle’,’:’,’marker’,’x’,’color’…

  • Cover Letter常用范式和模版

    Cover Letter常用范式和模版摘自:https://zhuanlan.zhihu.com/p/26708261;http://muchong.com/html/201401/6920446.html1.什么是Coverletter?CoverLetter,即投稿信,是论文投递时与论文一起发送给编辑的信件,其目的是让编辑在阅读你的论文之前,简单了解你文章的基本情况。Coverletter是编辑对论文的第一印象,也是初步评判你论文是否可以被期刊接收的重要依据(如果编辑看完Coverletter之后一点兴趣也没有,就没有下文了

  • MySQL常用SQL语句大全

    MySQL常用SQL语句大全MySQL数据库是一个十分轻便的数据库管理系统,相比大型的数据库管理系统如Oracle、MS-SQL,MySQL更拥有轻便、灵活、开发速度快的特色,更适用于中小型数据的存储与架构。MySQL之所以能够被数以万计的网站采用,也是由此而来。

  • # 创业计划书-样例参考五千套(一)[通俗易懂]

    # 创业计划书-样例参考五千套(一)[通俗易懂]创业计划书-%9C第五届“挑战杯”创业计划书(决赛版)创业计划书-(大赛通知)关于对第三届中国“互联网+”大学生创新创业大赛“的实施方案_项目计划书知识图谱创业计划书-(大赛章程)“创青春”全国大学生创业大赛章程创业计划书-(对外)企业研究开发项目计划书–样本创业计划书-(计划书模板)“创青春”创业大赛商业计划书模板_计划书模板创业计划书-(评审规则)第二届中国“互联网+”大学生创新创业大赛全国总决赛评审规则创业计划书-(评审规则)第三届中国“互联网+”大学生创新创业大赛全国总决赛评审规则创业

  • CVE-2014-0160:心脏出血(心血)漏洞

    CVE-2014-0160:心脏出血(心血)漏洞0x00漏洞介绍是一个出现在加密程序库OpenSSL的安全漏洞,该程序错误属于缓冲区过读,即可以读取的数据比应该允许读取的还多0x01漏洞成因由于未能在memcpy()调用受害用户输入内容作为长度参数之前正确进行边界检查。攻击者可以追踪OpenSSL所分配的64KB缓存、将超出必要范围的字节信息复制到缓存当中再返回缓存内容,这样一来受害者的内存内容就会以每次64KB的速度进行泄露0x02…

  • 秒懂mysql中的group by用法

    秒懂mysql中的group by用法文章转载自:https://blog.csdn.net/u014717572/article/details/80687042先来看下表1,表名为test:执行如下SQL语句:SELECTnameFROMtestGROUPBYname你应该很容易知道运行的结果,没错,就是下表2:可是为了能够更好的理解“groupby”多个列“和”聚合函数“的应用,我建议在思考的过程中…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号