优化阶乘算法的探索

优化阶乘算法的探索优化阶乘算法的探索中国地质大学(武汉)  陈海丰 阶乘(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账号...

(1)


相关推荐

  • JAVA实习生/应届生面试笔试题(一)

    一:单选题1. 下列哪一种叙述是正确的(D )A.abstract修饰符可修饰字段、方法和类B.抽象方法的body部分必须用一对大括号{}包住C.声明抽象方法,大括号可有可无D.声明抽象方法不可写出大括号2. 如下代码publicclassTest{publicintaMethod(){staticinti=0;i++;returni;}publicstatic…

  • awk 用法示例大全[通俗易懂]

    awk 用法示例大全[通俗易懂]文章目录#删除temp文件的重复行awk’!($0inarray){array[$0];print}’temp#查看最长使用的10个unix命令awk'{print$1}’~/.bash_history|sort|uniq-c|sort-rn|head-n10#查看机器的ip列表ifconfig-a|awk’/Bcast/{print$2}’|cut-c5-19#查看机器的每个远程链接机器的连接数netstat-ant

  • 医咖会SPSS免费教程学习笔记—R*C卡方检验

    医咖会SPSS免费教程学习笔记—R*C卡方检验1.R*C卡方检验需要满足的假设(1)两个变量为无序分类变量(2)观测值相互独立(3)任意单元格的期望频数>52.SPSS实操请依次点击:分析—描述统计—交叉表—将变量拖入右侧相应的行和列框中—点击右侧的“统计”)选择“卡方”和“Phi和克莱姆V”—继续点击右侧的“单元格”—选择“实测”,“期望”,“行”,“列”和“调整后标准化”—确定3.两两比较标准化残差的绝对值>3,差异存在统计学意义…

  • Visio2003密钥(office 2003密钥)

    序列号:GWH28-DGCMP-P6RC4-6J4MT-3HFDY序列号:WFDWY-XQXJF-RHRYG-BG7RQ-BBDHM

  • JAVA常见数据结构

    JAVA常见数据结构常见的的数据结构数据存储的常⽤结构有:栈、队列、数组、链表和红⿊树。栈栈:stack,⼜称堆栈,它是运算受限的线性表,其限制是仅允许在标的⼀端进⾏插⼊和删除操作,不允许在其他任何位置进⾏添加、查找、删除等操作。简单的说:采⽤该结构的集合,对元素的存取有如下的特点1.先进后出(即,存进去的元素,要在后它后⾯的元素依次取出后,才能取出该元素)。例如,⼦弹压进弹夹,先压进去的⼦弹在下⾯,后压进去的⼦弹在上⾯,当开枪时,先弹出上⾯的⼦弹,然后才能弹出下⾯的⼦弹。2.栈的⼊⼝、出⼝的都是栈的顶端位置。

  • java之MD5

    java之MD5publicclassMD5{ staticfinalintS11=7; staticfinalintS12=12; staticfinalintS13=17; staticfinalintS14=22; staticfinalintS21=5; staticfinalintS22=9; staticfinalintS23=14; staticfinalintS24=20; stat..

发表回复

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

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