时间戳

首页 > 解决方案 > 平分搜索以选择最佳储蓄率

python - 平分搜索以选择最佳储蓄率

问题描述

嗨，我想要一些关于这个问题的帮助，这些问题是 MIT OCW 计算机科学和 Python 课程的问题之一。我知道有人问过类似的问题，我发现有用的帖子，例如Bisection search code doesn't work，但我仍然卡住了！

我已经为这个问题苦苦挣扎了很多天，并试图以不同的方式解决它，但都失败了。如果可能的话，有人可以暗示我哪里出错了，而不是告诉我答案。我想在一些帮助下为自己解决这个问题。

作为参考，问题是 C 部分，这里：https ://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0001-introduction-to-computer-science-and-programming-in -python-fall-2016/assignments/MIT6_0001F16_ps1.pdf

由于我一直在努力，我将这项任务分解为一个总体目标，然后分解为解决问题的步骤。

目标：尝试找到最佳储蓄率，以实现 36 个月内首付 100 万美元的房子##解决问题的步骤：
1）猜测储蓄率，即 0 和 1000 的平均值
2) 计算在 36 个月内将如何增长
3a) 如果达到的金额在 36 个月内超过 100 万美元的 25%，那么较低的储蓄率应该是新的猜测
...max=guess（旧的猜测）和 min=0并更新猜测（高和低的平均值）
...使用新的猜测运行步骤 2 中的计算
3b）如果金额在 36 个月内未达到 100 万美元的 25%，那么更高的储蓄率应该是新的猜测
...min=guess（旧猜测）并更新猜测（高低的平均值） ...使用新猜测运行步骤 2 中的计算
3c) 如果金额在第 36 个月期限内达到 100 万美元的 25%，则退出并记录储蓄率作为最佳猜测。
为简单起见：假设没有利息并假设工资保持不变

所以这是我目前正在努力解决这个问题的代码。（它导致“猜测”变量趋于 0，然后无限循环）

total_cost=1000000 #cost of house
portion_down_payment=0.25 #fraction of cost needed for downpayment on house
downpayment=total_cost*portion_down_payment

starting_annual_salary=float(input("Enter the starting salary: "))
low=0
high=1000
bisect_steps=0
month=1 #set as 1 because the first calculation will occur in month 1 
guess=(low+high)//2
current_savings=0

def calSavings(current_savings,monthly_salary,guess,month):
    while month<37:
        monthly_savings=monthly_salary*(guess/1000)
        current_savings+=monthly_savings
        month+=1
    return(current_savings) 

current_savings=calSavings(current_savings,monthly_salary,guess,1)
while True:
    current_savings=calSavings(current_savings,monthly_salary,guess,1)
    if current_savings>downpayment and month<=35: #if amount reached goes over 25% of $1m within 36 months
        #a lower savings rate should be the new guess
        high=guess #max=guess (old guess) and min=0 and update the guess
        bisect_steps+=1
        guess=(low+high)//2
        print("The guess was too high, so the new lower guess is",guess," This is bisect step",bisect_steps)
        continue #send new guess up to beginning of while loop to calculate 
    elif current_savings<downpayment and month>=36: #if amount does not reach 25% of $1m within 36 months
        low=guess
        bisect_steps=+1
        guess=(low+high)//2
        print("The guess was too low, so the new higher guess is",guess," This is bisect step",bisect_steps)
        continue #send new guess up to beginning of while loop to calculate 
    elif current_savings>=downpayment and month==36: #if amount reaches 25% of $1m in the 36th months then quit
        # record the savings rate as the best guess
        print("The best savings rate is ",guess/100,"%, the amount saved was ",current_savings," in ",month," months")
        break #break out of while loop

我知道其他人也问过类似的问题（我已经查看了这些答案，但仍然没有解决我的问题），但不仅仅是一个答案，我想要关于如何解决这个问题的帮助。

标签： pythonsearchbinary-searchbisection

解决方案

更新

你的循环没有停止的原因是你没有给它足够的时间。您忘记的是您正在处理decimal类型。使用==withdecimal值总是很危险的。该decimal类型（默认情况下）精确到 28 位，这意味着您正在尝试为这个问题找到一个非常好的近似值，因为只有当它正确到 28 位小数时才会(current_savings>downpayment or current_savings<downpayment)评估False调用您的退出条件。

基本上，导致你的问题的问题是，即使你最终得到 1,000,000.0000000001 美元的估计值，python 说这不等于 1,000,000.0000000000 美元，所以它一直持续到它得到下一个 0，但它只是添加另一个零等等. 这将持续很长时间，并且在极少数情况下可能永远不会停止，因为并非所有十进制数都可以存储为二进制数（1,000,000 不在这些情况中）。

那么，我们如何解决这个问题呢？有两种选择。最简单的方法是忽略 cents 并将您的比较值转换为int，这将确保任何价值相差一美元的值都将被接受。其他选项是创建一系列可接受的答案。例如，我想在这 36 个月内节省 100 万美元，但这不太可能发生。因此，相反，我将结算 1,000,000.00 美元 - 1,000,010.00 美元（例如）范围内的任何金额。这样，我们确保任何过高的猜测都会被拒绝，并且只接受非常有限的猜测。

无论您走哪条路线，通常最好将无限循环的退出条件放在顶部，这样您就可以保证始终对其进行评估。

我的建议是编写一个这样的函数，并将其用于您的条件以退出循环（您将其放在顶部）：

def are_decimals_equal(a, b):
    accuracy = 0.0001
    return abs(a-b) < accuracy

这将认为 0.00009（以及小于该值的所有小数）等于 0.0000。

原来的

首先，请注意，您所做的不是二分法，而是二分搜索。

现在的问题是，您永远不会在主循环中更改月份的值。这意味着，一旦current_savings>downpayment评估为 False，您的程序将进入无限循环，因为在它可以评估为 True 之后没有任何条件，因为month>=36它将始终为 False。

据我所知，if/elif 语句中的条件的第二部分是不必要的，您的 calSavings 将始终计算 36 个月的节省，不会更多，也不会更少。因此，如果您从 if/elif 语句中删除该条件，您的程序最终将停止，此时它应该确定正确的答案。

最后，您将0其视为输出的原因是您最后的部门。如果你这样做print(typeof(guess))，你会看到它是一个整数，100 也是一个整数，因此这个除法将导致一些值，比如0.3123它会被截断为0. 将您的输出更改为float(guess/100)，这将消失。

推荐阅读