Herbert 嘗試爬上斜坡（Heffalumps 很重），所以他的每次 rush 只能使他獲得的距離只有之前 rush 的 95%。這意味著，如果他的第一次沖刺獲得 rush_height_gain 米，那么他的第二次沖刺只會獲得 0.95 * rush_height_gain 米，他的第三次沖刺只會獲得 0.95 * 0.95 * rush_height_gain 米，以此類推。幸運的是，他的背部滑動以同樣的方式減少。
撰寫代碼的傳統方式是：
def num_rushes(slope_height, rush_height_gain, back_sliding):
''' Calculate how many rushes '''
import math
current_height = 0
rushes = 0
i = 0
while current_height < slope_height:
current_height = rush_height_gain * (0.95 ** i)
if current_height < slope_height:
current_height -= back_sliding * (0.95 ** i)
rushes = 1
i = 1
return rushes
- ans = num_rushes(10, 10, 9) print(ans) #result: 1
- ans = num_rushes(100, 15, 7) print(ans) #result: 19
- ans = num_rushes(150,20,9) print(ans) #result: 22
現在我們需要使用遞回來提高效率。我在下面寫的遞回代碼沒有得到上面想要的結果。請指出如何修改它。
def num_rushes(slope_height, rush_height_gain, back_sliding, current_height=0):
if (slope_height-current_height) < rush_height_gain:
return 0
else:
current_height = current_height 0.95*(rush_height_gain-back_sliding)
return num_rushes(slope_height, 0.95*rush_height_gain, 0.95*back_sliding, current_height) 1
- ans = num_rushes(10, 10, 9) 列印(ans)
- ans = num_rushes(100, 15, 7) 列印(ans)
- ans = num_rushes(150,20,9) print(ans) #錯誤結果 - 得到 23
uj5u.com熱心網友回復：
您的遞回版本在檢查是否達到高度之前進行了后滑。這個檢查應該發生在前沖和后滑之間，而不是后滑之后。
這是一個更正，它也避免了額外的引數：
def num_rushes(slope_height, rush_height_gain, back_sliding):
if slope_height <= rush_height_gain:
return int(slope_height > 0)
return 1 num_rushes(slope_height - rush_height_gain back_sliding,
0.95 * rush_height_gain, 0.95 * back_sliding)
注意基本情況：如果slope_height為 0，則無需采取任何步驟，應回傳 0。在前沖達到高度的所有其他情況下，應回傳 1。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/438329.html
上一篇：檢查一棵樹是否為BST