問題
大整數(shù)相乘
思路說明
對于大整數(shù)計算，一般都要用某種方法轉(zhuǎn)化，否則會溢出。但是python無此擔憂了。
Python支持“無限精度”的整數(shù)，一般情況下不用考慮整數(shù)溢出的問題，而且Python Int類型與任意精度的Long整數(shù)類可以無縫轉(zhuǎn)換，超過Int 范圍的情況都將轉(zhuǎn)換成Long類型。
例如：
>>> 2899887676637907866*1788778992788348277389943
5187258157415700236034169791337062588991638L
注意：前面的“無限精度”是有引號的。事實上也是有限制的，對于32位的機器，其上限是：2^32-1。真的足夠大了。
為什么Python能夠做到呢？請有興趣刨根問底的去看Python的有關(guān)源碼。本文不贅述。
在其它語言中，通常用“分治法”解決大整數(shù)相乘問題。
但是，這里提供一個非常有意思的計算兩個整數(shù)相乘的方法，算是做為大整數(shù)相乘的演示。
兩個整數(shù)相乘：阿拉伯乘法。關(guān)于這個乘法的詳細描述，請看：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，轉(zhuǎn)化為list類型的[1,2,3]，每個元素都是int類型
num_lst2 = [int(i) for i in str(num2)]
#兩個list中整數(shù)兩兩相乘
int_martix = [[i*j for i in num_lst1] for j in num_lst2]
#將上述元素為數(shù)字的list轉(zhuǎn)化為元素類型是str，主要是將9-->'09'
str_martix = [map(convert_to_str,int_martix[i]) for i in range(len(int_martix))]
#將上述各個list中的兩位數(shù)字分開：['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)]
#計算阿拉伯乘法表的左側(cè)開始各項和
sum_left = summ_left(martix)
#計算阿拉伯乘法表的底部開始各項和
sum_end = summ_end(martix)
#將上述兩個結(jié)果合并后翻轉(zhuǎn)
sum_left.extend(sum_end)
sum_left.reverse()
#取得各個和的個位的數(shù)字（如果進位則加上）
result = take_digit(sum_left)
#翻轉(zhuǎn)結(jié)果并合并為一個結(jié)果字符串數(shù)值
result.reverse()
int_result = "".join(result)
print "%d*%d="%(num1,num2)
print int_result
#將int類型轉(zhuǎn)化為str類型，9-->'09'
def convert_to_str(num):
if num<10:
return "0"+str(num)
else:
return str(num)
#計算阿拉伯乘法表格左側(cè)開始的各項之和
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
#得到各個元素的個位數(shù)，如果是大于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)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
