问题
大整数相乘
思路说明
对于大整数计算,一般都要用某种方法转化,否则会溢出。但是python无此担忧了。
Python支持“无限精度”的整数,一般情况下不用考虑整数溢出的问题,而且Python Int类型与任意精度的Long整数类可以无缝转换,超过Int 范围的情况都将转换成Long类型。
例如:
> 2899887676637907866*1788778992788348277389943 5187258157415700236034169791337062588991638L
注意:前面的“无限精度”是有引号的。事实上也是有限制的,对于32位的机器,其上限是:2^32-1。真的足够大了。
为什么Python能够做到呢?请有兴趣刨根问底的去看Python的有关源码。本文不赘述。
在其它语言中,通常用“分治法”解决大整数相乘问题。
但是,这里提供一个非常有意思的计算两个整数相乘的方法,算是做为大整数相乘的演示。
两个整数相乘:阿拉伯乘法。关于这个乘法的详细描述,请看:http://ualr.edu/lasmoller/medievalmult.html
解决(Python)
#!/usr/bin/env python #coding:utf-8 #阿拉伯乘法 def arabic_multiplication(num1,num2): num_lst1 = [int(i) for i in str(num1)] #将int类型的123,转化为list类型的[1,2,3],每个元素都是int类型 num_lst2 = [int(i) for i in str(num2)] #两个list中整数两两相乘 int_martix = [[i*j for i in num_lst1] for j in num_lst2] #将上述元素为数字的list转化为元素类型是str,主要是将9-->'09' str_martix = [map(convert_to_str,int_martix[i]) for i in range(len(int_martix))] #将上述各个list中的两位数字分开:['01','29','03']-->[0,2,0],[1,9,3] martix = [[int(str_martix[i][j][z]) for j in range(len(str_martix[i]))] for i in range(len(str_martix)) for z in range(2)] #计算阿拉伯乘法表的左侧开始各项和 sum_left = summ_left(martix) #计算阿拉伯乘法表的底部开始各项和 sum_end = summ_end(martix) #将上述两个结果合并后翻转 sum_left.extend(sum_end) sum_left.reverse() #取得各个和的个位的数字(如果进位则加上) result = take_digit(sum_left) #翻转结果并合并为一个结果字符串数值 result.reverse() int_result = "".join(result) print "%d*%d="%(num1,num2) print int_result #将int类型转化为str类型,9-->'09' def convert_to_str(num): if num<10: return "0"+str(num) else: return str(num) #计算阿拉伯乘法表格左侧开始的各项之和 def summ_left(lst): summ = [] x = [i for i in range(len(lst))] y = [j for j in range(len(lst[0]))] sx = [i for i in x if i%2==0] for i in sx: s=0 j=0 while i>=0 and j<=y[-1]: s = s+ lst[i][j] if i%2==1: j = j+1 else: j = j i = i-1 summ.append(s) return summ #计算阿拉伯乘法表格底部开始的各项之和 def summ_end(lst): summ=[] y = [j for j in range(len(lst[0]))] ex = len(lst)-1 for m in range(len(y)): s = 0 i=ex j=m while i>=0 and j<=y[-1]: s= s+lst[i][j] if i%2==1: j = j+1 else: j=j i = i-1 summ.append(s) return summ #得到各个元素的个位数,如果是大于10则向下一个进位 def take_digit(lst): tmp = 0 digit_list = [] for m in range(len(lst)): lstm = 0 lstm = lst[m]+tmp if lstm<10: tmp = 0 digit_list.append(str(lstm)) else: tmp = lstm/10 mm = lstm-tmp*10 digit_list.append(str(mm)) return digit_list if __name__=="__main__": arabic_multiplication(469,37)
标签:
python,大整数相乘
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
金钱帮资源网 Copyright www.kbjia.com
暂无“python里大整数相乘相关技巧指南”评论...
稳了!魔兽国服回归的3条重磅消息!官宣时间再确认!
昨天有一位朋友在大神群里分享,自己亚服账号被封号之后居然弹出了国服的封号信息对话框。
这里面让他访问的是一个国服的战网网址,com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后,确实是网易的网址,也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情,因为以前都没有出现这样的情况,现在突然提示跳转到国服战网的网址,是不是说明了简体中文客户端已经开始进行更新了呢?
更新日志
2024年10月08日
2024年10月08日
- 金铲铲之战S9阵容推荐攻略 6套阵容分享
- dnf手游追忆光环外观选哪个 dnf手游追忆光环外观选择推荐
- 怎么获得dnf手游紫色曲玉 dnf手游紫色曲玉获取方法一览
- dnf手游洗点水怎么获得 dnf手游洗点水获取方法介绍
- 万代南梦宫遭中国玩家抵制 《铁拳8》被疯狂刷差评
- 曝侃爷分手登微博热搜 网友:穿衣意见不合?
- 《暗喻幻想:ReFantazio》M站2024高分榜排名第三 超越《最终幻想7:重生》
- 赛季末发育路上分英雄推荐,狄仁杰A就行
- 小乔克制攻略:除了兰陵王还有更多好选
- 王者荣耀:对抗路难度排行,花木兰最能秀
- 群星《新说唱2024 第3期 (下)》[FLAC/分轨][89.04MB]
- 群星《歌手2024 第2期》[320K/MP3][95.59MB]
- 群星《歌手2024 第2期》[FLAC/分轨][260.73MB]
- 《原神》5.0基尼奇一图流养成攻略 基尼奇怎么培养
- 5.1版本up池角色一览,新版本角色卡池