gpt4 book ai didi

python - 如何在不使用 * 运算符(或/运算符)的情况下递归地将两个正整数相乘? .您可以使用加法、减法和位移

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:10:39 30 4
gpt4 key购买 nike

我偶然发现了这个解决方案,但我无法理解其中到底发生了什么。谁能解释一下!

据我了解,它试图通过计算一半的单元格然后将其加倍来计算 a*b 网格中的单元格数量。但是我无法理解递归调用。

请不要建议其他解决方案,请尝试解释此解决方案:)

def minProduct(a,b):
bigger = b if a < b else a #a < b ? b : a
smaller = a if a < b else b #a < b ? a : b
return minProductHelper(smaller,bigger)

def minProductHelper(smaller, bigger):
if smaller == 0:
return 0
elif smaller == 1:
return bigger

# Compute half. If uneven, compute other half. If even, double it
s = smaller >> 1 # divide by 2
side1 = minProduct(s,bigger)
side2 = side1
if smaller % 2 == 1:
side2 = minProductHelper(smaller - s, bigger)

return side1 + side2

print(minProduct(5,6))

最佳答案

从某种意义上说,这是一种递归的分而治之算法。向左移 1 有效地将数字除以 2(丢弃任何余数)。 minProductHelper 使用 s = smaller >> 1smaller 除以 2,然后返回 的递归求和>s * bigger(smaller - s) * bigger。由于加法和乘法的特性,您可以得到 ((smaller - s) * bigger) + (s * bigger) == smaller * bigger 这就是您想要的结果。您有两种基本情况,当 smaller01 时,您可以想象调用 minProduct(a ,b) 将继续将 ab 切成两半(然后将这些一半分成两半,等等)直到它所要做的就是对一堆求和涉及 0 和一些数字或 1 和一些数字的产品,无需使用 * 运算符即可确定。较小的数字总是被减半而不是较大的数字,因为这允许用较少的递归调用达到基本情况。

关于python - 如何在不使用 * 运算符(或/运算符)的情况下递归地将两个正整数相乘? .您可以使用加法、减法和位移,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49839547/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com