Generic placeholder image
闲敲代码、落灯花
What's past is prologue

联系邮箱:email@hezehua.net


联系QQ:1907330840

座右铭

保持热情,持续学习,每日精进

用大数乘法计算阶乘

用大数乘法计算阶乘

本文与作者在csdn上的博文【用大数乘法计算阶乘】保持同步


在比较小的范围内阶乘可以递归实现,而求更大的数的阶乘一般用到long long长整形数,不过,即使这样,在耗时和再大些的阶乘上力有不逮,所以,在输入比较大的情况下,用大数乘法计算阶乘是最好的选择。
计算过程分2步:
1、输入字符串s,将它的值保存到整型n中;
2、从1~i~n-1循环将i转化为字符串并和s做大数乘法,每次将结果保存在字符数组r中,r初始化等于s,在计算过程中动态开辟的空间大小是strlen(i)+strlen(r);

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>

char* ff(char *a,char *b){//大数乘法
    int lena=strlen(a); int lenb=strlen(b);
    int len=lena+lenb;
    char *result=(char *)malloc(sizeof(char)*(len+1));
    memset(result,'0',len);
    result[len]='\0';   
    for(int i=lena-1;i>=0;i--){
        int t=0,p=0,q=0,temp=0;
        int j;
        for(j=lenb-1;j>=0;j--){
            p=(b[j]-'0')*(a[i]-'0');
            temp=result[i+j+1]-'0'+p%10+t;
            result[i+j+1]=temp%10+'0';
            t=temp/10+p/10;
        }
        if(t){
            result[i+j+1]=result[i+j+1]+t;
        } 
    }
    if(result[0]=='0')return result+1;
    return result;
}

void dd(int n,char *b){//将整数转化为字符串
    int i=0;
    while(n){
        b[i++]=n%10+'0';
        n=n/10;
    }
}

void reserve(char *b){//将字符串逆序
    for(int i=0;i<=(strlen(b)-1)/2;i++){
        int t=b[i];
        b[i]=b[strlen(b)-i-1];
        b[strlen(b)-i-1]=t;
    }
}
int main(){
    char c;
    char *a=(char*)malloc(sizeof(char)*1000);   
    char *b=(char*)malloc(sizeof(char)*1000);
    char *result=a;
    memset(a,'\0',1000);    
    memset(b,'\0',1000);
    scanf("%s",a); 
    int n=atoi(a);      
    if(n==1){
        puts(a);
        return 0;
    };
    for(int i=1;i<n;i++){
        dd(i,b);
        reserve(b);
        result=ff(result,b);            
    }       
    puts(result);
    free(result);
    free(a);
    free(b);
    return 0;
}
猜你喜欢
大数加减
阅读 414

太残忍,半个月不做题,就对题目毫无感觉了,明明思路正确清晰,但敲的代码满满的bug,连输入字符串前要开辟空间都能无视。。。还在输入后就清空了却在后面一个劲的对它操作。。。略怀悲伤地把代码改好了。#include #include #incl...

生成子集——二进制法
阅读 546

用二进制位的0和1表示集合中是否存在该元素要生成0~n的子集,先生成0~n的二进制序列,这些序列的0、1位正好可以对应一个子集中全集在该位置上的元素是否存在,将其作为子集中存在的元素的标记,输出对应元素。#include #include

最近学习算法,对动态规划不太了解,使用的时候照搬转移方程式,知其然不知其所以然,今天看到一篇动态规划的教程,解释得非常通俗,原文在这里[动态规划入门教程] (http://blog.csdn.net/woshioosm/article/details/7438834),下面我用自己的记忆和理解...

算法--大数开方
阅读 533

之前已找到比较好的大数乘法算法,现在我们来解决大数开方问题,如有大数n,求其开方x,则x与n必满足x*x=n;也就是说我们能遍历x找到n的开方,但是问题在于我们是不可能对大数遍历的。如果我们可以确定它的大致范围,仅仅测试几个不容易直接判断的数据就找到目标数据就好了。      1-一个n位数的开...

算法--八皇后问题
阅读 369

在棋盘上放置8个皇后,使得他们不能相互攻击,此时,每个皇后的攻击范围为同行同列和同对角线,要求找出所有解, 回忆之前分析生成排列所用的解答树,我们再把问题简化为四皇后问题,规则不变,写出它的完整解答树 与生成1~n的排列这篇博文中的解答树最大的不同点就是----只有一条或者几条路径可以...

算法--生成可重集排列
阅读 384

在生成1~n的排列一文中,我们获取排列时用了控制不相等来实现让每个数都不重复地出现,所以如果要生成含有重复元素的全排列,对对生成1~n的排列的程序适当修改即可。 首先,把各个元素改成用户输入,输入数组为p,然后把if(a[k]==j)改为if(a[k]==p[j]),a[cur]=j改成a[cur...

大数乘法(二)
阅读 574

乘法运算过程模拟法首先获取输入的乘数(a)与被乘数(b)字符串,按一般乘法运算过程,先是a的最后一位数字与b的最后一位数字相乘,接着a中用于相乘的数下标递减,直到a中所有数字与b最后一位都相乘过,保存结果后再递减b中的用于相乘的数字的下标,循环下去,直到b中每一位数都与a所有数相乘完。 在这个过程...

子集生成算法——增量构造法
阅读 1071

思路是一次选出一个元素放入集合中生成0~n的子集,每次选出最小的值放入集合中,通过从0递增得到下一个位置的值。#include #include #include #include