字符串相乘

题目要求

有两个字符串，str1,str2，内容为数值，数值均大于0请编写算法计算两个字符串相乘的结果，不可以使用大数据类型，不可以把字符串直接转成整数来处理。

输入: str1='3'  str2='5'
输出: '15'

输入: str1='32'  str2='15'
输出: '480'

输入: str1='323434223434234242343'  
     str2='15492828424295835983529'
输出:

思路分析

题目要求的很明确，不可以直接把字符串转成整数然后相乘，所以int(str1)*int(str2)是不被允许的。

不止如此，第三个示例里，数值已经非常大，已经超出了2⁶⁴ ，在计算过程中，中间结果也非常的大，在大多数编程语言里，你找不到合适的数据类型来存储这样的数据，因此，只能用字符串来保存。

先来看第一个示例， 3 乘 5， 简单的乘法，在看第二个示例， 32 乘 15 ，小学的时候都学过如何计算乘法，32*5 + 32*10 =480。需要编写一个算法，来实现这个计算过程，但是要注意，32*5的结果必须保存成为字符串"160",为什么不能保存成数值型数据160呢？就32*15来说，保存成数值是没有问题的，可对于第三个示例，在计算中间结果时，得到的结果太大了，根本无法用数值型变量保存，因此必须保存成字符串。

最简单的乘法

我们需要先实现一个简单的字符串乘法，函数定义为

def single_str_multi(str1, single):
    """
    single是一个小于10的数值, 例如 323354 * 4
    :param str1: 基础数值
    :param single: 单个数值
    :return:
    """
    pass

如果总是可以保证single是一个小于10的数值，那么计算起来就简单容易的多了，计算时，反向遍历str1，每个数值分别与single相乘，计算进位和当前位置留下的值，并存入一个列表中，遍历结束后，要注意检查最后一次进位的值，算法实现如下

def single_str_multi(str1, single):
    """
    single是一个小于10的数值, 例如 323354 * 4
    :param str1: 基础数值
    :param single: 单个数值
    :return:
    """
    pre_sum = 0            # 进位
    single = int(single)
    res_lst = []
    for item in reversed(str1):
        # 每次计算都要考虑上一次计算结果的进位
        item_num = int(item) * single + pre_sum
        pre_sum = item_num / 10     # 计算进位
        curr_num = item_num % 10    # 计算当前位置的值
        res_lst.insert(0, str(curr_num))

    if pre_sum > 0:
        res_lst.insert(0, str(pre_sum))

    return ''.join(res_lst)

有了single_str_multi函数做基础，就可以实现最终的字符串相乘算法了，定义函数

def str_multi(str1, str2):
    pass

这一次，反向遍历str2，每次遍历都得到一个单一数值single，这样恰好可以调用single_str_multi 函数，但是需要注意的是每次得到的结果都要根据single的位置补0，如果single是str2的百位，那么计算结果就要乘100。

字符串相加

每次调用single_str_multi函数，得到的都是中间结果，这些结果必须加在一起才能得到乘法的结果，因此，我们还需要一个计算字符串加法的函数，前面的计算二进制加法的练习题已经有过讲解，代码稍作修改即可

def str_sum(str1, str2):
    """
    计算两个字符串的加法
    :param str1:
    :param str2:
    :return:
    """
    # 先补齐
    str_1_length = len(str1)
    str_2_length = len(str2)
    if str_1_length < str_2_length:
        str1 = "0"*(str_2_length - str_1_length) + str1
    else:
        str2 = "0"*(str_1_length - str_2_length) + str2

    # 进行计算
    index = len(str1) - 1
    pre_num = 0         # 记录进位
    res_lst = []        # 记录结果

    # 反向遍历
    while index >= 0:
        item_1 = int(str1[index])
        item_2 = int(str2[index])
        item_sum = item_1 + item_2 + pre_num
        pre_num = item_sum/10
        curr_num = item_sum % 10

        # 新的计算结果插入到结果的第一位
        res_lst.insert(0, str(curr_num))
        index -= 1

    if pre_num == 1:
        res_lst.insert(0, '1')

    return ''.join(res_lst)

字符串相乘

万事具备，之前东风，最后来实现str_multi函数

def str_multi(str1, str2):
    """
    字符串相乘
    :param str1:
    :param str2:
    :return:
    """
    res = '0'
    for index, item in enumerate(reversed(str2)):
        if item == '0':   # 为0时不用计算
            continue
        # 一定要补0
        single_res = single_str_multi(str1, item) + '0'*index
        # 每次相乘结果要相加
        res = str_sum(res, single_res)
    return res

全部代码

def str_sum(str1, str2):
    """
    计算两个字符串的加法
    :param str1:
    :param str2:
    :return:
    """
    # 先补齐
    str_1_length = len(str1)
    str_2_length = len(str2)
    if str_1_length < str_2_length:
        str1 = "0"*(str_2_length - str_1_length) + str1
    else:
        str2 = "0"*(str_1_length - str_2_length) + str2

    # 进行计算
    index = len(str1) - 1
    pre_num = 0         # 记录进位
    res_lst = []        # 记录结果

    # 方向遍历
    while index >= 0:
        item_1 = int(str1[index])
        item_2 = int(str2[index])
        item_sum = item_1 + item_2 + pre_num
        pre_num = item_sum//10
        curr_num = item_sum % 10

        # 新的计算结果插入到结果的第一位
        res_lst.insert(0, str(curr_num))
        index -= 1

    if pre_num == 1:
        res_lst.insert(0, '1')

    return ''.join(res_lst)


def single_str_multi(str1, single):
    """
    single是一个小于10的数值, 例如 323354 * 4
    :param str1: 基础数值
    :param single: 单个数值
    :return:
    """
    pre_sum = 0            # 进位
    single = int(single)
    res_lst = []
    for item in reversed(str1):
        # 每次计算都要考虑上一次计算结果的进位
        item_num = int(item) * single + pre_sum
        pre_sum = item_num // 10     # 计算进位
        curr_num = item_num % 10    # 计算当前位置的值
        res_lst.insert(0, str(curr_num))

    if pre_sum > 0:
        res_lst.insert(0, str(pre_sum))

    return ''.join(res_lst)


def str_multi(str1, str2):
    """
    字符串相乘
    :param str1:
    :param str2:
    :return:
    """
    res = '0'
    for index, item in enumerate(reversed(str2)):
        if item == '0':   # 为0时不用计算
            continue
        # 一定要补0
        single_res = single_str_multi(str1, item)
        if single_res != '0':
            single_res += '0'*index
        # 每次相乘结果要相加
        res = str_sum(res, single_res)
    return res


if __name__ == '__main__':
    print(str_multi('323434223434234242343', '15492828424295835983529'))