我在hackerrank上研究這個(gè)問(wèn)題給定一個(gè)無(wú)符號(hào)整數(shù)的分子和除數(shù)，打印出商和余數(shù)。你不能使用divide，不能使用mod，你想優(yōu)化速度我最初的想法是（在 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))但是通過(guò)這種方法，我得到 7 作為商，4 作為余數(shù)。我能夠在網(wǎng)上找到正確的解決方案，即：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))我無(wú)法找出 while 循環(huán)的條件語(yǔ)句while num - (quotient * div) >= div:提出該聲明的思考過(guò)程是什么？
3 回答
慕森王
TA貢獻(xiàn)1777條經(jīng)驗(yàn) 獲得超3個(gè)贊
這只是因?yàn)?code>remainder不能大于divider。
并num - (quotient * div)給出準(zhǔn)確的remainder.
所以，如果num - (quotient * div)是大的divider，這意味著quotient是不夠大。
這就是為什么它需要繼續(xù)這樣做直到remainder小于divider.
郎朗坤
TA貢獻(xiàn)1921條經(jīng)驗(yàn) 獲得超9個(gè)贊
官方的解決方案只是低效的重復(fù)減法實(shí)現(xiàn)，用更復(fù)雜的乘法代替簡(jiǎn)單的減法；如果你打算使用重復(fù)減法，你至少應(yīng)該去掉乘法：
def divide(num, div):
quot = 0
while div <= num:
quot += 1
num -= div
return quot, num
重復(fù)減法不是“針對(duì)速度進(jìn)行了優(yōu)化”，正如您調(diào)用divide(1000000000,3). 我們可以改為使用重復(fù)減除數(shù)的平方，或除數(shù)的平方的平方，或...，直到...除數(shù)的平方的平方超過(guò)該數(shù)字。例如，考慮divide(1000000000,3)上面提到的問(wèn)題。我們首先制作一個(gè)方塊列表：
3 * 3 = 9
9 * 9 = 81
81 * 81 = 6561
6561 * 6561 = 43046721
我們停在那里，因?yàn)橄乱淮纹椒匠^(guò)了目標(biāo)?，F(xiàn)在我們?cè)诿總€(gè)余數(shù)上重復(fù)調(diào)用樸素的除法重復(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)
最后的余數(shù)是1。商是：
0*3/3 + 0*9/3 + 64*81/3 + 1512*6561/3 + 23*43046721/3 = 333333333
我們只執(zhí)行了 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
第一個(gè)while計(jì)算并堆疊正方形，以及每個(gè)正方形除以div，因此最終代碼中沒(méi)有除法。在第一個(gè)之后while，divs和sqs堆?？雌饋?lái)像這樣：
divs = [3, 9, 81, 6561, 43046721]
sqs = [1, 3, 27, 2187, 14348907]
第二個(gè)while重復(fù)彈出兩個(gè)堆棧，在第三個(gè)中執(zhí)行樸素的除法重復(fù)減法算法while，并累加和。這比官方解決方案快得多，也沒(méi)有復(fù)雜得多。
您可以在https://ideone.com/CgVT1i 上運(yùn)行該程序。
茅侃侃
TA貢獻(xiàn)1842條經(jīng)驗(yàn) 獲得超21個(gè)贊
num - (quotient*div) >= div 在數(shù)學(xué)上與 ((quotient+1) * div) <= num
這與您的想法幾乎相同，但是您犯了一個(gè)錯(cuò)誤。當(dāng)我處理這樣的事情時(shí)，我總是測(cè)試邊界條件。
您的條件是“如果商數(shù)太小quotient*div < num”。所以嘗試一些情況，quotient*div == num-1并確保商真的太小。并嘗試一些情況，quotient*div == num并確保商確實(shí)足夠大。
現(xiàn)在，這里還有一個(gè)級(jí)別 2，您可能無(wú)需擔(dān)心。在第二個(gè)循環(huán)中使用的精確形式 - num - (quotient*div) >= div- 是仔細(xì)編寫(xiě)的，不會(huì)創(chuàng)建任何大于num和 的中間結(jié)果div。這確保即使您使用最大可能的整數(shù)num和/或，您也會(huì)得到正確的答案div。
如果你把它寫(xiě)成((quotient+1) * div) <= num，那么它可能(quotient+1)*div太大而不能表示為整數(shù)，這可能導(dǎo)致條件得到錯(cuò)誤的答案（在許多語(yǔ)言中，至少在某些版本的 python IIRC 中）。
添加回答
舉報(bào)
0/150
提交
取消