Herbert attempts to climb the slope (Heffalumps are heavy), so each of his rushes gains him only 95% as much distance as his previous rush. This means that if his first rush gains him rush_height_gain metres, then his second rush will only gain him 0.95 * rush_height_gain metres, his third rush 0.95 * 0.95 * rush_height_gain metres, and so on. Fortunately, his back sliding reduces in the same way.
The traditional way to write the code is:
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
Now we need to use recursion to improve the efficiency. The recursive code I wrote below didn't get the desired result as above. Please point out how to revise it.
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) print(ans)
- ans = num_rushes(100, 15, 7) print(ans)
- ans = num_rushes(150,20,9) print(ans) #wrong result - get 23
CodePudding user response:
Your recursive version is doing the backslide before checking that the height is reached. This check should happen between the forward rush and the backslide, not after the backslide.
Here is a correction, which also avoids the extra parameter:
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)
Note the base case: if the slope_height
is zero, no step has to be taken and 0 should be returned. In all other cases where the forward rush reaches the height, 1 should be returned.