PYTHON - Bisection search麻省理工学院介绍使用Python进行编程PSET1第3部分

Question

我正试图在36个月内为100万美元的房子找到最优惠的储蓄率。储蓄需要在100美元的预付定金内。首付款为总成本的25％。我必须搜索0到10000之间的整数（使用整数除法），然后将它转换为小数百分比（使用浮点除法），以便在36个月后计算current_savings时使用。

这是我的代码无法正常工作（我真的很新的编程）

annual_salary = 150000 
total_cost = 1000000 
low=0 
high=10000 
portion_saved=(low+high)/20000.0 
epsilon=100 
current_savings = 0 
portion_down_payment=0.25*total_cost 
steps = 0 
rate = 0.04 
number_of_months = 0 
semi_annual_raise = 0.07 

while current_savings-portion_down_payment>=epsilon and number_of_months<=36: 
current_savings += annual_salary * portion_saved/12 
current_savings += current_savings * rate/12 
number_of_months += 1 
if number_of_months % 6 == 0: 
annual_salary += annual_salary * semi_annual_raise 

if current_savings<portion_down_payment: 
    low=portion_saved 
else: 
    high=portion_saved 
portion_saved=(low+high)/20000.0 
steps+=1 

print("Best savings rate: ", portion_saved) 
print("Steps in bisection search", steps) 

任何帮助是极大的赞赏！

Answer 1

月收入不随储蓄率各不相同，所以是有意义的只计算一次：

# calculate income per month over 36 months 
base_monthly_salary = 150000 // 12 
semiannual_raise = 0.07 
monthly_incomes = [base_monthly_salary * (1. + semiannual_raise) ** (month // 6) for month in range(36)] 

如果每月储蓄不赚利息，这个问题很简单：

target_amount = 1000000. * 0.25 
savings_rate = target_amount/sum(monthly_incomes) # 0.4659859 

所以你将不得不节省46.6％的收入。

如果每月的储蓄能赚取利息，问题就更加有趣（坏的双关语是绝对有意的）。

def savings_balance(monthly_incomes, monthly_interest_rate, savings_rate): 
    total = 0. 
    for amt in monthly_incomes: 
     # At the end of each month, 
     total *= 1. + monthly_interest_rate # we earn interest on what was already saved 
     total += amt * savings_rate   # and add a fixed fraction of our monthly income 
    return total 

测试一下基于上面我们的计算，

savings_balance(monthly_incomes, 0.0, 0.4659859) # 249999.9467 

所以看起来像我们所期望的。

您可以将此函数看作迭代评估36次多项式。给定已知的monthly_incomes和interest_rate，我们希望找到savings_rate来产生期望的total，即找到polynomial - target == 0的唯一真正的正根。如果interest_rate > 0.没有分析解决方案，那么我们将尝试使用数字解决方案。

target_amount = 1000000. * 0.25 

# Make up a number: annual savings interest = 1.9% 
monthly_interest_rate = 0.019/12. 

# Our solver expects a single-argument function to solve, so let's make it one: 
def fn(x): 
    return savings_balance(monthly_incomes, monthly_interest_rate, x) 

def bisection_search(fn, lo, hi, target, tolerance=0.1): 
    # This function assumes that fn is monotonically increasing! 

    # check the end-points - is a solution possible? 
    fn_lo = fn(lo) 
    assert not target < -tolerance + fn_lo, "target is unattainably low" 
    if abs(target - fn_lo) <= tolerance: 
     return lo 
    fn_hi = fn(hi) 
    assert not fn_hi + tolerance < target, "target is unattainably high" 
    if abs(target - fn_hi) <= tolerance: 
     return hi 

    # a solution is possible but not yet found - 
    # repeat until we find it 
    while True: 
     # test the middle of the target range 
     mid = (lo + hi)/2 
     fn_mid = fn(mid) 
     # is this an acceptable solution? 
     if abs(target - fn_mid) <= tolerance: 
      return mid 
     else: 
      # do we need to look in the lower or upper half? 
      if target < fn_mid: 
       # look lower - bring the top down 
       hi = mid 
      else: 
       # look higher - bring the bottom up 
       lo = mid 

，现在我们运行它像

# From above, we know that 
# when interest = 0.0 we need a savings rate of 46.6% 
# 
# If interest > 0. the savings_rate should be smaller, 
# because some of target_amount will be covered by generated interest. 
# 
# For a small annual_interest_rate over an N year term, 
# the effective accrued interest rate will be close to 
# N * annual_interest_rate/2 -> 1.5 * 1.9% == 2.85% 
# 
# So we expect the required savings rate to be 
# about 46.6% * (1. - 0.0285) == 45.3% 

bisection_search(fn, 0.40, 0.47, target_amount) # 0.454047973 

赋予的45.4％的储蓄率。