在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):

    quot = 0

    while div <= num:

        quot += 1

        num -= div

    return quot, num

重复减法不是“针对速度进行了优化”，正如您调用divide(1000000000,3). 我们可以改为使用重复减除数的平方，或除数的平方的平方，或...，直到...除数的平方的平方超过该数字。例如，考虑divide(1000000000,3)上面提到的问题。我们首先制作一个方块列表：

3 * 3 = 9

9 * 9 = 81

81 * 81 = 6561

6561 * 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):

    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，因此最终代码中没有除法。在第一个之后while，divs和sqs堆栈看起来像这样：

divs = [3, 9, 81, 6561, 43046721]

sqs  = [1, 3, 27, 2187, 14348907]

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

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

Answer 3

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，那么它可能(quotient+1)*div太大而不能表示为整数，这可能导致条件得到错误的答案（在许多语言中，至少在某些版本的 python IIRC 中）。