如何在二分搜索期间修复无限循环

Question

我的代码通过了测试用例，但如果输入大约 949,000 的任何内容，它就会进入无限循环。

我需要计算节省部分月收入的最佳利率，以便在 36 个月内支付 2 位有效数字的首付。我认为这与我不太了解 epsilon 的计算方式有关 - 我尝试将 epsilon 计算为 0.0001 * total_cost、0.0004 * portion_down_payment 和 0.0001 * annual_income都无济于事。

#House Hunting ps1c

low = int(0)
high = int(10000)
percent_saved = (low + high)/2.0

current_savings = 0
annual_salary = int(input("What is your starting anual salary? "))
total_cost = 1000000
semi_annual_raise = 0.07
portion_down_payment = total_cost * 0.25
epsilon = 100

r = 0.04

total_months = 0
steps = 0
while True:
    current_savings = 0
    monthly_salary = annual_salary/12
    for i in range(1,37):
        current_savings += (current_savings*r/12)
        current_savings += (monthly_salary * (percent_saved / 10000))     
        total_months += 1
        if total_months % 6 == 0:
            monthly_salary += monthly_salary * semi_annual_raise
    steps +=1   

    if abs(current_savings - portion_down_payment) <= epsilon:
        print("Steps in bisectional search: ", steps)
        best_savings_rate = str(percent_saved / 100)
        print("Best savings rate: ", (best_savings_rate + "%"))
        break
    elif (portion_down_payment - 100) - current_savings > 0:
        low = percent_saved
        percent_saved = int((low + high) / 2.0)
    else:
        high = percent_saved       
        percent_saved = int((low + high) / 2.0)

    if percent_saved >= 9999:
        print("It is not possible to afford this in 3 years")
        break

测试用例 1

Enter the starting salary: 150000
Best savings rate: 0.4411  
Steps in bisection search: 12

测试用例 2

Enter the starting salary: 300000
Best savings rate: 0.2206 
Steps in bisection search: 9

测试用例 3

Enter the starting salary: 10000
It is not possible to pay the down payment in three years

我的代码通过了所有测试用例，但是当输入太高时它进入了一个我不知道如何调和的无限循环。

Answer 1

本质上，当年薪变高时，最佳储蓄率就会变小。当最佳储蓄率变得小于您需要的精度水平时

abs(current_savings - portion_down_payment) <= epsilon

变得更高。当您将 percent_saved 转换为

中的整数时

percent_saved = int((low + high) / 2.0)

人为限制精度，代码进入死循环

删除强制转换，代码将始终有效。

如何在二分搜索期间修复无限循环

How to fix infinite loop during bisection search

python

bisection

epsilon

测试用例 1

测试用例 2

测试用例 3