python - python的舍入问题(实现Karatsuba的算法)
问题描述
在我的 python 代码中最难解决舍入问题,该代码应该使用 Karatsuba 的算法 [ 1 , 2 ] 输出 2 个数字的乘积值。这是我的代码:
def mult(num1,num2):
if num1 < 10 or num2 < 10:
return int(num1*num2)
else:
n = len(str(num1))
a = int(str(num1)[:-(int(n/2))])
#print(a)
c = int(str(num2)[:-(int(n/2))])
#print(c)
b = int(str(num1)[-(int(n/2)):])
#print(b)
d = int(str(num2)[-(int(n/2)):])
#print(d)
val1 = mult(a,c)
val2 = mult(b,d)
val3 = mult(a+b,c+d) - val1 - val2
ans = val1*(10**int(n)) + val2 + (val3)*(10**(int(n/2)))
return int(ans)
我将添加所需的任何其他信息,请告诉我在这方面的任何帮助非常感谢谢谢
解决方案
找到了 Karatsuba 算法的一个工作示例: https ://pythonandr.com/2015/10/13/karatsuba-multiplication-algorithm-python-code/
我认为您的问题是您无法以这种方式处理奇数 n。例如,将 100 与 100 相乘:如果将 1.5 舍入到 2,您将得到 100 000 个零,如果将其舍入到 1,您将得到 1000,但缺少零。此外,您应该从两个数字中获取最大位数,而不仅仅是 num1。
我希望下面的代码可以帮助您解决问题:
def karatsuba(x,y):
"""Function to multiply 2 numbers in a more efficient manner than the grade school algorithm"""
if len(str(x)) == 1 or len(str(y)) == 1:
return x*y
else:
n = max(len(str(x)),len(str(y)))
nby2 = n / 2
a = x / 10**(nby2)
b = x % 10**(nby2)
c = y / 10**(nby2)
d = y % 10**(nby2)
ac = karatsuba(a,c)
bd = karatsuba(b,d)
ad_plus_bc = karatsuba(a+b,c+d) - ac - bd
# this little trick, writing n as 2*nby2 takes care of both even and odd n
prod = ac * 10**(2*nby2) + (ad_plus_bc * 10**nby2) + bd
return prod
推荐阅读
- python - 使用 Ajax 的 Django 页面上出现 500 错误
- json - 错误”:“无法处理的实体”,“消息”:“服务器无法解析 JSON”
- reactjs - ReactJS 中的 CSRF 与 Express 和 csurf
- c# - 使用 C# 为 Agora.io 生成动态密钥
- java - 编辑器无法解析 Java 项目中的 Python 文件
- algorithm - 从增量构建的 2D 平面图构建面
- c# - 在 Visual Studio 社区(适用于 Unity)中,如何在评论部分 /* */ 中使用“回车换行”获取自动 TAB?
- sql-server - 查询以检索最便宜的价格和包裹描述
- c# - 在多个 WPF 控件中托管相同的 Win32 窗口
- java - 如何使用 Java 中的自定义异常处理无效数据行?