字符串相乘

题目要求

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

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

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

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

思路分析

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

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

先来看第一个示例, 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'))

扫描关注, 与我技术互动

QQ交流群: 211426309

加入知识星球, 每天收获更多精彩内容

分享日常研究的python技术和遇到的问题及解决方案