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

Question

我偶然发现了这个解决方案，但我无法理解这到底发生了什么。有人可以解释一下吗！

据我了解，它试图通过计算一半的单元格然后将其加倍来计算 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))

Answer 1

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

Answer 2

假设您将 5 和 6 相乘。然后程序首先计算出最小的数字，即 5。然后，它通过将最小的数字分成两个完整的部分(几乎相等)来调用自己。

minProduct(5,6)=minProduct(2,6)+minProduct(3,6).然后minProduct(2,6)以类似的方式计算成minProduct(1,6)+minProduct(1,6)。现在较小的数字是 1，程序只需返回 6 并计算回值。每个函数调用都会发生这种情况。

minProduct(5,6) =minProduct(2,6)+minProduct(3,6) =minProduct(1,6)+minProduct(1,6)+minProduct(3,6) (Let minProduct(3,6)=18) for cohesion) =6+6+18 =30

为什么要先找出最小的数字？前面的答案准确地处理了为什么使用较小的数字而不是较大的数字。取两个任意数字 2 和 1000。我需要弄清楚 2*1000 是什么。更容易计算出 1000+1000 然后 (2+2+.+2).更少的函数调用意味着更快的算法。

为什么有最小产品(0，a)的条件？你确实明白为什么有minProduct(1，a)的条件。但是 minProduct(0，a) 有一个条件，因为有一个乘以 2 的特殊情况。当您调用 minProduct(2,3) 时。这将解析为 minProduct(2,3) 和 minProduct(0,3)。所以你需要单独处理这个问题。