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％的儲蓄率。