大整数相乘

大整数相乘是个被我们听烂了的经典算法题之一,解法各不同,今天在公司论坛上看到一个挺高端的算法思路,记录并分享下。

如下图示例:999*99的计算方法。

    上图是按照我们小学列算式做乘法的基本方法,但是不考虑进位,只是把算出的结果按相应的位置存放着。

    以图所示为例,将计算结果依次存放在一个result数组中。第一轮存下3个81;第二轮从result数组的第二个元素开始存储,并且和该位置上原来的元素累加,依次计算到第二轮结束,如果有第三轮,还是这样的方式,result数组的第3个位置开始存储,并和之前的数字累加,bulabulabula,直到计算结束,会有个结果存放在result数组中。以本题为里,result = {81,162,162,81}。

    计算结束后,接下来以此处理result数组的每个元素,result[0]=81,81%10=1,81/10=8(进位),那么处理完之后result[0]=1,result[1]=162+8=170,后面的元素不变;下面处理result[1] = 170,170%10=0,170/10=17(进位),那么处理完之后result[0]=1,result[1]=0,result[2]=162+17=179,像这样以此处理下去,最后,result={1,0,9,8,9},反转result,即为你想要得到的最终计算结果了。

    这个只是思路,且result数组得是个挺大的数组,具体用C代码调试就看你的代码水平了。希望我描述的你可以看明白,有更好更简单易懂的方式,欢迎交流哦!

原文地址:https://www.cnblogs.com/stoneJin/p/3491377.html