我在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:提出該聲明的思考過程是什么？
3 回答
慕森王
TA貢獻1777條經驗 獲得超3個贊
這只是因為remainder不能大于divider。
并num - (quotient * div)給出準確的remainder.
所以，如果num - (quotient * div)是大的divider，這意味著quotient是不夠大。
這就是為什么它需要繼續這樣做直到remainder小于divider.
郎朗坤
TA貢獻1921條經驗 獲得超9個贊
官方的解決方案只是低效的重復減法實現，用更復雜的乘法代替簡單的減法；如果你打算使用重復減法，你至少應該去掉乘法：
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
我們停在那里，因為下一次平方超過了目標?，F在我們在每個余數上重復調用樸素的除法重復減法算法：
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 上運行該程序。
茅侃侃
TA貢獻1842條經驗 獲得超22個贊
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 中）。
添加回答
舉報
0/150
提交
取消