第六天：《LeetCode一天一例》-----大数乘法（python实现）

迈不过友情╰ 2022-03-08 13:48 188阅读 0赞

# 大数乘法 #

>       题目：  a = '45755564532435735465878576'      b = '8765434234657373'， a和b代表两个整数，我们想实现的就是将a和b进行相乘。两个大数相乘的结果一般都非常大，不是一个整型所能容纳的。。我们可以将计算结果用字符串或者列表的形式给出。。

### 分析： ###

我写的这段代码可能对于大数乘法来说，不是最优的。但却是最好理解的。 下面讲解一下思路，因为上面那个数太大了，举个简单例子解释，我们让a = '24355', b ='432' ， 过程如下：  
       ***第一步：*** 从b的最低位开始（就是末尾2开始），拿出一个b中的元素与a中的所有元素进行相乘，这里不光要乘，还有考虑移位，如b中的倒数第二个元素（也就是拿出的第二个数）与a中的数进行相乘时，最低位要填充个零（下图的红色方块）。 b中倒数第三个元素与a中所有元素相乘时，最低位要填充两个零，以此类推。。  注意: 这里先不进行进位

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70][]

***第二步：*** 在第一步中运算的结果前面给它填充零，主要是为了最后好运算。如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1][]

***第三步：***就是把第二步中  图里面的最下面三行进行加法运算， 竖着加

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 2][]

***第四步：***考虑进位的问题 ， 从上图红框中的最低位开始，也就是从10开始  依次判断，将当前数除以10的余数放在当前位，商累加到前一位。。最后结果就出来了

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 3][]

黄色框中即为运算的结果

### 代码实现： ###

def big_data_mult(a, b):
        a = list(a)
        b = list(b)
        # 把a拿着和b的每一位去乘 ，每乘一次， 结果向左移一位()
    
        # 列表的头插list.insert(0, item)
        temp = []
        temp_sub = []  # 存的是每次a与b中一位乘的结果
        for i in range(len(b)-1, -1,  -1):
            if len(b)-1 == i:  # 第一下乘 不需要移位
                pass
            else:
                # 插入k个零
                k = 1
                while k <= len(b) - 1 - i:
                    temp_sub.insert(0, 0)
                    k += 1
            for j in range(len(a)-1, -1, -1):
                # 拿b中一位与a中所有为进行相乘
                temp_sub.insert(0, int(b[i]) * int(a[j]))
            temp.append(temp_sub)
            temp_sub = []
        return temp
    
    def fill_list(max_len, temp):
        temp_fill = []
    
        for item in temp:
            if len(item) < max_len:
                i = 0
                n = len(item)
                while i < max_len - n:
                    item.insert(0, 0)
                    i += 1
            temp_fill.append(item)
        return temp_fill
    
    def get_result(temp_fill, maxlen):
        result = [0] * (max_len+1)
    
        # 将各列先累加起来 等会处理进位
        for i in range(max_len-1, -1, -1):
            for item in temp_fill:
                # 对因为累加起来  最后考虑进位
                result[i+1] += item[i]
    
        # 现在处理进位
        for i in range(len(result)-1, -1, -1):
            if result[i] >= 10:
                result[i-1] += result[i] // 10
                result[i] = result[i] % 10
    
        return result
    
    
    if __name__ == "__main__":
        # a作为乘数， b作为被乘数
        a = '45755564532435735465878576'
        b = '8765434234657373'
        # 拿着b中的数与a中的每一位去乘
        temp = big_data_mult(a, b)
    
        # 现在的任务是找出temp中最长的那个串，将其他不够的进行填充   其实不用找了 肯定是temp的最后一个
        max_len = len(temp[-1])  # 找出了最长。然后在其他的头部填充，将其所有元素的长度搞成一致的
    
        temp_fill = fill_list(max_len, temp)
        # 这个打印的是填充好的所有行
        print("打印填充好的数组:\n")
        for i in temp_fill:
            print(i)
        # 将其对应位累加即可
        result = get_result(temp_fill, max_len)
        print(result)

### 输出结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 4][]

![20190315125551515.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70]: /images/20220308/229059c9fbe14ce792763c8c69dbd5d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1]: /images/20220308/fe7bb7404aa948298a566e6fc45240df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 2]: /images/20220308/0e94e04e55ed486188ec0dcf4fc5abb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 3]: /images/20220308/5f58cd130f2646248ad40d6afcb10d24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 4]: /images/20220308/a2331cec2fbe4627b02d0d45e86d2bd9.png
[20190315125551515.png]: /images/20220308/c2dfd5dfce6440d9a73db2df4a8d7242.png