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

联系邮箱:email@hezehua.net


联系QQ:1907330840

座右铭

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

大数乘法(二)

大数乘法(二)

本文与作者在csdn上的博文【大数乘法(二)】保持同步


首先获取输入的乘数(a)与被乘数(b)字符串,按一般乘法运算过程,先是a的最后一位数字与b的最后一位数字相乘,接着a中用于相乘的数下标递减,直到a中所有数字与b最后一位都相乘过,保存结果后再递减b中的用于相乘的数字的下标,循环下去,直到b中每一位数都与a所有数相乘完。
在这个过程中,怎么遍历出填放结果的位置和处理进位是关键。
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<conio.h>

    int main(){
        char c;
        char *a=(char*)malloc(sizeof(char)*1000);
        char *b=(char*)malloc(sizeof(char)*1000);
        memset(a,'\0',1000);    memset(b,'\0',1000);
        scanf("%s",b);     scanf("%s",a);       
        int lena=strlen(a); int lenb=strlen(b);
        int len=lena+lenb;
        char *result=(char *)malloc(sizeof(char)*(len+1));
        //多开辟一个字节用于存放'\0'便于输出
        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;
            } 
        }
        //第一个位置可能没有填充进位,所以如果第一个字符为'0'就不输出
        if(result[0]=='0')puts(result+1);
        else puts(result);

        free(a);
        free(b);
        free(result);
    }
猜你喜欢
子集生成算法——增量构造法
阅读 957

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

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

大数乘法(一)
阅读 443

常用的大数相乘算法有模拟加减法和分治法,第一种符合我们的运算习惯,第二种用数学方法提高了效率,(具体描述与实现可参考http://www.cnblogs.com/heyonggang/p/3599857.html)而两种各有优势的方法的程序实现都比较复杂,并且不易于初学者理解,于是我琢磨出了一个将...

大数加减
阅读 347

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

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

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

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

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

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

用大数乘法计算阶乘
阅读 425

在比较小的范围内阶乘可以递归实现,而求更大的数的阶乘一般用到long long长整形数,不过,即使这样,在耗时和再大些的阶乘上力有不逮,所以,在输入比较大的情况下,用大数乘法计算阶乘是最好的选择。 计算过程分2步: 1、输入字符串s,将它的值保存到整型n中; 2、从1~i~n-1循环将i转化...