Python模拟大整数乘法的小学竖式计算过程

让我们先看个图回顾一下小学学过的计算整数乘法的竖式计算过程

然后再来看如何使用Python来模拟上面的过程,虽然在Python中计算任意大的数字乘法都没有问题,但下面的代码作为一个算法的理解还是不错的,并且几乎可以直接翻译成C语言。

from random import randint

def mul(a, b): '''小学竖式两个整数相乘的算法实现''' #把两个整数分离开成为各位数字再逆序 aa = list(map(int, reversed(str(a)))) bb = list(map(int, reversed(str(b)))) #n位整数和m位整数的乘积最多是n+m位整数 result = [0] * (len(aa)+len(bb)) #按小学整数乘法竖式计算两个整数的乘积 for ia, va in enumerate(aa): #c表示进位,初始为0 c = 0 for ib, vb in enumerate(bb): #Python中内置函数devmod()可以同时计算整商和余数 c, result[ia+ib] = divmod(va*vb+c+result[ia+ib], 10) #最高位的余数应进到更高位 result[ia+ib+1] = c

#整理,变成正常结果 result = int(''.join(map(str,reversed(result)))) return result

#测试 for i in range(1000): a = randint(1, 1000000000) b = randint(1, 10000) r = mul(a, b) if r != a*b: print(a, b, r, 'error')

原文发布于微信公众号 - Python小屋(Python_xiaowu)

原文发表时间:2016-12-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python专栏

浅尝Python快速排序

1314
来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

702
来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

1846
来自专栏chenjx85的技术专栏

leetcode-39-组合总和(有趣的递归)

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

1182
来自专栏take time, save time

你所能用到的数据结构(五)

七、骚年,这就是你的终极速度了吗? 在介绍了前面的几个排序算法之后,这一次我准备写写快速排序,快速排序之所以叫快速排序是因为它很快,它是已知实践中最快的排序算...

2805
来自专栏程序员叨叨叨

5.2 数组类型

在着色程序中,数组通常的使用目的是:作为从外部应用程序传入大量参数到 Cg 的顶点程序中的形参接口,例如与皮肤形变相关的矩阵数组,或者光照参数数组等。

591
来自专栏抠抠空间

算法基础

1124
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

1081
来自专栏Golang语言社区

深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

3365
来自专栏生信技能树

R语言中的排序,集合运算,reshape,以及merge总结

不想排版,心情也不好,但是这个知识点很重要,尤其是学习R语言的朋友,请仔细看~ 一直以来我都是随便看了点R的编程教程,因为我学了一点点C,所以还算有基础,现在基...

31711

扫码关注云+社区