在python中不使用除法创建除法程序

Question

我在hackerrank上研究这个问题

Given a numerator and divisor of unsigned integers, print out the quotient and remainder . You cannot use divide, cannot use mod, and you want to optimize for speed

我最初的想法是（用python语言）

def divide_problem(num, div):
    quotient = 1
    while (div * quotient) < num:
        quotient += 1
    remainder = (div*quotient) - num

    print(quotient, "quotient")
    print(remainder, 'remainder')


print(divide_problem(31, 5))

但是用这种方法，我得到的商是7，余数是4。我在网上找到了正确的解决方案：

^{pr2}$

我无法找出while循环的条件语句

while num - (quotient * div) >= div:

提出这种说法的思维过程是什么？在

Answer 1

num - (quotient*div) >= div在数学上与((quotient+1) * div) <= num相同

这和你的想法差不多，但你犯了个错误。当我计算出这样的东西时，我总是测试边界条件。在

你的条件是“如果quotient*div < num，那么商太小了”。所以尝试一些quotient*div == num-1的情况，确保商真的太小了。尝试一些quotient*div == num的情况，确保商真的足够大。在

现在，这里还有一个2级，你可能不需要担心。第二个循环num - (quotient*div) >= div中使用的精确形式是精心编写的，以避免创建任何大于num和div的中间结果。这可以确保即使对num和/或div使用最大的整数，也能得到正确的答案。在

如果您将其写成((quotient+1) * div) <= num，那么{}可能太大而无法表示为整数，这可能导致条件得到错误的答案（在许多语言中，至少在python IIRC的某些版本中）。在

Answer 2

官方的解决方案只是重复减法的低效实现，用更复杂的乘法代替简单的减法；如果要使用重复减法，至少应该去掉乘法：

def divide(num, div):
    quot = 0
    while div <= num:
        quot += 1
        num -= div
    return quot, num

如果调用divide(1000000000,3)，那么重复减法并不是“为速度而优化”的。我们可以用除数平方的重复减法，或者除数平方的平方，或者…，一直到除数平方的平方。。。除数超过数字。作为一个例子，考虑上面提到的问题divide(1000000000,3)。我们首先列出一个正方形列表：

^{pr2}$

我们停在那里是因为下一个方阵超过了目标。现在我们在每个余数上重复调用朴素的“除以重复减法”算法：

divide(1000000000, 43046721) = (23, 9925417)
divide(9925417, 6561) = (1512, 5185)
divide(5185, 81) = (64, 1)
divide(1, 9) = (0, 1)
divide(1, 3) = (0, 1)

最后的余数是1。商为：

^{4}$

我们只做了23+1512+64=1599的减法，而不是官方解的333333333减法。代码如下：

def divide(num, div):
    divs, sqs, sum = [div], [1], 0
    while divs[-1] * divs[-1] < num:
        divs.append(divs[-1] * divs[-1])
        sqs.append(sqs[-1] * sqs[-1] * div)
    while divs:
        div, sq = divs.pop(), sqs.pop()
        quot = 0
        while div <= num:
            quot += 1
            num -= div
        sum += (quot * sq)
    return sum, num

第一个while计算并堆叠平方，以及除以div的每个平方，因此在最后的代码中没有除法。在第一个^{之后，div和sqs堆栈如下所示：

divs = [3, 9, 81, 6561, 43046721]
sqs  = [1, 3, 27, 2187, 14348907]

第二个while重复弹出两个堆栈，在第三个while中执行朴素的除以重复减法算法，并累加和。这比官方的解决方案快得多，也不复杂得多。在

您可以在https://ideone.com/CgVT1i运行该程序。在

Answer 3

只是因为remainder不能大于divider。在

而num - (quotient * div)正好给出了remainder。在

所以如果num - (quotient * div)比divider大，就意味着{}不够大。在

这就是为什么它需要一直这样做直到remainder小于{}。在