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

Question

我在hackerrank上研究这个问题

给定一个无符号整数的分子和除数，打印出商和余数。你不能使用divide，不能使用mod，你想优化速度

我最初的想法是（在 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 作为余数。我能够在网上找到正确的解决方案，即：

def divide_problem(num, div):

    quotient = 1

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

        print(num - (quotient * div), "loop")

        quotient += 1

    remainder = num - (quotient * div)

    print(quotient, "quotient")

    print(remainder, 'remainder')

print(divide_problem(31, 5))

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

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

提出该声明的思考过程是什么？

Answer 1

这只是因为remainder不能大于divider。并num - (quotient * div)给出准确的remainder.所以，如果num - (quotient * div)是大的divider，这意味着quotient是不够大。这就是为什么它需要继续这样做直到remainder小于divider.

Answer 2

官方的解决方案只是低效的重复减法实现，用更复杂的乘法代替简单的减法；如果你打算使用重复减法，你至少应该去掉乘法：def divide(num, div):&nbsp; &nbsp; quot = 0&nbsp; &nbsp; while div <= num:&nbsp; &nbsp; &nbsp; &nbsp; quot += 1&nbsp; &nbsp; &nbsp; &nbsp; num -= div&nbsp; &nbsp; return quot, num重复减法不是“针对速度进行了优化”，正如您调用divide(1000000000,3). 我们可以改为使用重复减除数的平方，或除数的平方的平方，或...，直到...除数的平方的平方超过该数字。例如，考虑divide(1000000000,3)上面提到的问题。我们首先制作一个方块列表：3 * 3 = 99 * 9 = 8181 * 81 = 65616561 * 6561 = 43046721我们停在那里，因为下一次平方超过了目标。现在我们在每个余数上重复调用朴素的除法重复减法算法：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。商是：0*3/3 + 0*9/3 + 64*81/3 + 1512*6561/3 + 23*43046721/3 = 333333333我们只执行了 23 + 1512 + 64 = 1599 次减法，而不是官方解决方案的 333,333,333 次减法。这是代码：def divide(num, div):&nbsp; &nbsp; divs, sqs, sum = [div], [1], 0&nbsp; &nbsp; while divs[-1] * divs[-1] < num:&nbsp; &nbsp; &nbsp; &nbsp; divs.append(divs[-1] * divs[-1])&nbsp; &nbsp; &nbsp; &nbsp; sqs.append(sqs[-1] * sqs[-1] * div)&nbsp; &nbsp; while divs:&nbsp; &nbsp; &nbsp; &nbsp; div, sq = divs.pop(), sqs.pop()&nbsp; &nbsp; &nbsp; &nbsp; quot = 0&nbsp; &nbsp; &nbsp; &nbsp; while div <= num:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; quot += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; num -= div&nbsp; &nbsp; &nbsp; &nbsp; sum += (quot * sq)&nbsp; &nbsp; return sum, num第一个while计算并堆叠正方形，以及每个正方形除以div，因此最终代码中没有除法。在第一个之后while，divs和sqs堆栈看起来像这样：divs = [3, 9, 81, 6561, 43046721]sqs&nbsp; = [1, 3, 27, 2187, 14348907]第二个while重复弹出两个堆栈，在第三个中执行朴素的除法重复减法算法while，并累加和。这比官方解决方案快得多，也没有复杂得多。您可以在https://ideone.com/CgVT1i 上运行该程序。

Answer 3

num - (quotient*div) >= div&nbsp;在数学上与&nbsp;((quotient+1) * div) <= num这与您的想法几乎相同，但是您犯了一个错误。当我处理这样的事情时，我总是测试边界条件。您的条件是“如果商数太小quotient*div < num”。所以尝试一些情况，quotient*div == num-1并确保商真的太小。并尝试一些情况，quotient*div == num并确保商确实足够大。现在，这里还有一个级别 2，您可能无需担心。在第二个循环中使用的精确形式 -&nbsp;num - (quotient*div) >= div- 是仔细编写的，不会创建任何大于num和 的中间结果div。这确保即使您使用最大可能的整数num和/或，您也会得到正确的答案div。如果你把它写成((quotient+1) * div) <= num，那么它可能(quotient+1)*div太大而不能表示为整数，这可能导致条件得到错误的答案（在许多语言中，至少在某些版本的 python IIRC 中）。