使用近似解和二分搜索

Question

我想说明一下，这个问题来自 EDX python Comp Sci 入门课程（免费在线课程），我在网上看到了很多答案。我想弄清楚为什么这段特定代码会进入无限循环，而不是完全更改我的代码的方法（除非它根本上是错误的...）

主要是，为什么会失败：

while abs(balance - fixedP*12)  >= epsilon:

该程序的目标是找到最小的每月支付金额，以便我们可以在一年内还清余额。

我下面的代码达到了金额（如果你在 while 循环中间插入一个 print (fixedP) 语句可以找到，但它陷入了无限循环。我相信我的条件失败了，我不能找出原因。当余额变成“29157.09”，我的 (fixedP * 12) 支票也变成 29157.09，我以为 while 循环会停止。但是，它一直卡住。

balance = 320000
annualInterestRate = .2 
#above is given, below is my code

epsilon = 0.01  #precision check
balanceD = balance  #copy of balance
month = 0  #counter
monthlyRate = annualInterestRate/12  #given formula for problem

#bisection search parameters using given forumulas
low = balance / 12
high = (balance * (1+monthlyRate)**12)/12

fixedP = (low + high) / 2.0  #midpoint


while abs(balance - fixedP*12)  >= epsilon:
  unpaid = balance - fixedP
  newB = unpaid + monthlyRate*unpaid
  balance = newB
  month += 1

  if(month == 12 and balance > 0): #set new lower bound since original guess was too low
    low = fixedP
    fixedP = (high + low)/2
    balance = balanceD
    month = 0
  elif(month == 12 and balance < 0): #set new higher bound since original guess was too high
    high = fixedP
    fixedP = (low + high)/2
    balance = balanceD
    month = 0

print('Lowest Payment: ', round(fixedP, 2))

上面的代码达到了固定的每月金额，但在该金额处陷入了无限循环。它永远不会退出 while 循环。你能帮我弄清楚为什么我的 while 循环条件失败了吗？

谢谢。

Answer 1

你的逻辑和其他一切都是正确的。但是你的 while 函数逻辑有点不对，你不应该比较 while abs(balance - fixedP*12) >= epsilon。它应该是：

while balance >= epsilon:

或：

abs(balance - fixedP*(12-month))  >= epsilon:

另外，后面比较时需要用epsilon来比较balance，而不是0。

因为余额应该是从你剩余的月数中扣除的值，所以你不应该在这里使用12。

还有你的代码

balance = 320000
annualInterestRate = .2 
#above is given, below is my code

epsilon = 0.01  #precision check
balanceD = balance  #copy of balance
month = 0  #counter
monthlyRate = annualInterestRate/12  #given formula for problem

#bisection search parameters using given forumulas
low = balance / 12
high = (balance * (1+monthlyRate)**12)/12

fixedP = (low + high) / 2.0  #midpoint


while balance >= epsilon:
    unpaid = balance - fixedP
    newB = unpaid + monthlyRate*unpaid
    balance = newB
    month += 1
    if(month == 12 and balance > epsilon): #set new lower bound since original guess was too low
        low = fixedP
        fixedP = (high + low)/2
        balance = balanceD
        month = 0
    elif(month == 12 and balance < -epsilon): #set new higher bound since original guess was too high
        high = fixedP
        fixedP = (low + high)/2
        balance = balanceD
        month = 0


print('Lowest Payment: ', round(fixedP, 2))

或者，您可以使用 break 函数在获得所需值时退出 while 循环：

balance = 320000
annualInterestRate = .2 
#above is given, below is my code

epsilon = 0.01  #precision check
balanceD = balance  #copy of balance
month = 0  #counter
monthlyRate = annualInterestRate/12  #given formula for problem

#bisection search parameters using given forumulas
low = balance / 12
high = (balance * (1+monthlyRate)**12)/12

fixedP = (low + high) / 2.0  #midpoint


while True:
    unpaid = balance - fixedP
    newB = unpaid + monthlyRate*unpaid
    balance = newB
    month += 1
    if(month == 12 and balance > epsilon): #set new lower bound since original guess was too low
        low = fixedP
        fixedP = (high + low)/2
        balance = balanceD
        month = 0
    elif(month == 12 and balance < -epsilon): #set new higher bound since original guess was too high
        high = fixedP
        fixedP = (low + high)/2
        balance = balanceD
        month = 0
    else:
        break

print('Lowest Payment: ', round(fixedP, 2))

如有任何您不清楚的地方，请随时post。谢谢

Answer 2

我在这里看到的问题更像是一个经济学问题，而不是 Python 问题。

也就是说，为了让您的代码正常工作，我们首先在 while 块之前添加以下行：

series_pw_factor = ((1+monthlyRate)**11 - 1) / (monthlyRate*(1+monthlyRate)**11)

然后我们可以修改你的条件如下：

while abs(balanceD - fixedP*series_pw_factor - fixedP)  >= epsilon:

现在解释经济学如何与这个问题联系起来：

您的 while 条件的问题在于它没有考虑货币的时间价值（即利息）。如果你今天借了 1000 美元的贷款，并且每月（每个月末）支付 200 美元，为期 5 个月，如果利息不为零，你在 5 个月结束时仍然会欠贷款。

虽然问题中没有明确说明，但要获得答案“29157.09”，您必须假设第一笔付款是在第一个月的月初进行的，最后一次付款是在第一个月的月初进行的第 12 个月。

付款结构如下：

初始余额：320000 美元

t = 0 时的付款 1（第 1 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^0 = 29157.09

t = 1 时的付款 2（第 2 月初）：29157.09，

t = 0 时的值为 29157.09 / (1+monthlyRate)^1 = 28679.10

t = 2 时的付款 3（第 3 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^2 = 28208.96

t = 3 时的付款 4（第 4 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^3 = 27746.51

t = 4 时的付款 5（第 5 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^4 = 27291.65

t = 5 时的付款 6（第 6 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^5 = 26844.25

t = 6 时的付款 7（第 7 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^6 = 26404.18

t = 7 时的付款 8（第 8 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^7 = 25971.32

t = 8 时的付款 9（第 9 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^8 = 25545.56

t = 9 时的付款 10（第 10 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^9 = 25126.78

t = 10 时的付款 11（第 11 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^10 = 24714.87

t = 11 时的付款 12（第 12 月初）：29157.09

t = 0 时的值为 29157.09 / (1+monthlyRate)^11 = 24309.71

当您对每笔付款在 t = 0 时的价值求和时，它将等于初始余额 $320000

这里的模式是我们本质上是在解决：

(1) initial_balance = payment*sum(1/(1+monthlyRate)^i) for i in [0,11]

或

(2) initial_balance = (t = 0 时的付款) + payment*sum(1/(1+monthlyRate)^i) for i in [1,11]

在(2)中，'sum(1/(1+monthlyRate)^i) for i in [1,11]'项是称为均匀序列现值因子

这就是变量 series_pw_worth 因子的含义。

while 的条件确保满足 (2)。

利用(2)，我们也可以看出一个单线解O(1)是：

fixedP = balance / (1 + ((1+annualInterestRate/12)**11 - 1) / (annualInterestRate/12*(1+annualInterestRate/12)**11))

使用近似解和二分搜索

Using approximate solutions and bisection search

python

python-3.x

algorithm

bisection