基于python 的 分治算法 解决 大数乘法问题 -- 浅浅记录

分治方法 总的来说 还是递归的调用,将大的问题分解为小的问题

 1 #通过分治 计算 n个0的字符串
 2 def zero(n):
 3     if n==0:
 4         return ""
 5     if n==1:
 6         return "0"
 7     return zero(n//2)+zero(n//2)+zero(n%2)
 8 
 9 #计算大数加法
10 def  add(a,b):
11     if len(a)<=8 and len(b)<=8:
12         return str( int(a)+int(b) )
13     a1="0"
14     a2=a
15     if len(a)>8:
16         a1=a[0:len(a)-8]
17         a2=a[len(a)-8:]
18                                          
19     b1="0"
20     b2=b
21     if len(b)>8:
22         b1=b[0:len(b)-8]
23         b2=b[len(b)-8:]
24 
25     k=add(a2,b2)
26     while(len(k)<8):
27         k="0"+k
28     if len(k)>8:
29         return add( add(a1,b1),"1")+k[1:]
30     return add(a1,b1)+k
31 
32 def chengfa(a,b):
33     if len(a)<=4 and len(b)<=4:
34         return str( int(a)*int(b) )
35     if len(a)>4:
36         k=len(a)//2  #分治的中间值
37         #通过计算超过长度4 下分解
38         return  add( chengfa(a[0:k],b)+zero(len(a[k:] )),chengfa(a[k:],b) )
39     return chengfa(b,a)
40 print(chengfa("999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999","999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999"))

运行结果;

== RESTART: C:\Users\Administrator\AppData\Local\Programs\Python\Python38\w.py =
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001