Поиск Bisect, чтобы выбрать лучшую норму сбережений

Question

Привет, я хотел бы получить некоторую помощь по этим вопросам, поставленным в качестве одной из проблем на курсах по компьютерным наукам и питону в MIT OCW. Я знаю, что люди задавали подобные вопросы, и я нашел полезные сообщения, такие как код поиска Bisection не работает, но я все еще застрял!

Я боролся с этой проблемой в течение многих дней и пытался решить ее по-разному, но потерпел неудачу во всех отношениях. Если это вообще возможно, может кто-то просто намекнуть, где я иду не так, вместо того, чтобы сказать мне ответ. Я хотел бы решить эту проблему для себя с небольшой помощью.

Для справки, вопрос является частью 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

По мере того как я боролся, я разбил эту задачу на общую цель, а затем на шаги по решению проблемы.

Цель: попытаться найти наилучшую норму сбережений для достижения первоначального взноса на дом стоимостью 1 млн долларов за 36 месяцев ## Шаги для решения проблемы:
1) сделайте предположение о норме сбережений, которая является средней величиной 0 и 1000
2) рассчитать, как это будет расти за 36 месяцев
3a) если достигнутая сумма превысит 25% от 1 млн. Долл. США в течение 36 месяцев, то новой оценкой должна стать более низкая норма сбережений
...max= догадка (старое предположение) и min=0 и обновление догадки (среднее из высокого и низкого)
... выполнить вычисление в шаге 2 с новым предположением
3b) если сумма не достигает 25% от 1 млн. Долл. США в течение 36 месяцев, то более высокая норма сбережений должна быть новой оценкой
... мин = угадать (старое предположение) и обновить предположение (среднее для высокого и низкого) ... выполнить вычисление на шаге 2 с новым предположением
3c) если сумма достигает 25% от 1 млн. Долл. США в течение 36-месячного срока, выйдите и запишите норму сбережений как наилучшее предположение.
Для простоты: не принимайте проценты и полагайте, что заработная плата остается неизменной

Итак, вот мой код с текущими усилиями по решению этого. (это приводит к тому, что переменная "угадай" стремится к 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

Я знаю, что другие люди задавали подобные вопросы (я смотрел на эти ответы и до сих пор не решил свою проблему), но больше, чем ответ, мне нужна помощь о том, КАК решить эту проблему.

Answer 1

Обновить

Причина, по которой ваш цикл не останавливается, заключается в том, что вы не уделяете ему достаточно времени. То, что вы забыли, это то, что вы имеете дело с decimal тип. С использованием == с decimal Ценности всегда опасны. decimal тип является точным (по умолчанию) до 28 мест, что означает, что вы пытаетесь найти чрезвычайно хорошее приближение для этой задачи, потому что только тогда, когда это правильно до 28 десятичных знаков, (current_savings>downpayment or current_savings<downpayment) оценить False ссылаясь на ваше условие выхода.

По сути, проблема, которая вызывает вашу проблему, состоит в том, что даже когда вы в конечном итоге получаете оценку в $1 000 000,0000000001, python говорит, что она не равна $1 000 000,0000000000, поэтому он продолжает работать, пока не получит следующий 0, но затем он просто добавляет еще один ноль и т. Д., Это будет продолжаться в течение очень очень долгого времени и в редких случаях может никогда не остановиться из-за того, что не все десятичные числа могут быть сохранены как двоичные числа (1 000 000 не входит в число этих случаев).

Итак, как мы решаем это? Есть два варианта. Самый простой - игнорировать центы и просто приводить значения сравнения к int, это будет гарантировать, что любое значение от доли доллара будет принято. Другие варианты - создать диапазон принятых ответов. Скажем, например, я хотел бы сэкономить ровно 1 миллион долларов за эти 36 месяцев, но это вряд ли произойдет. Поэтому вместо этого я согласен на любую сумму в диапазоне от 1 000 000,00 до 1 000 010 долларов (например). Таким образом, мы гарантируем, что любое слишком высокое предположение будет отклонено, и только очень ограниченное количество предположений будет принято.

Независимо от того, по какому маршруту вы идете, обычно хорошей идеей является поставить условие выхода бесконечного цикла наверх, таким образом вы гарантируете, что оно всегда будет оцениваться.

Мое предложение было бы написать такую ​​функцию и использовать ее для вашего состояния, чтобы выйти из цикла (который вы поместите вверху):

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 всегда будет ложным.

Из того, что я вижу, вторая часть ваших условий в операторах if/elif не нужна, ваши calSavings всегда будут рассчитывать 36-месячные сбережения, никогда больше, никогда. Таким образом, если вы удалите это условие из своих операторов if/elif, ваша программа в конечном итоге остановится, и в этот момент она должна принять правильный ответ.

Наконец, причина, почему вы видите 0 в качестве результата ваше разделение в конце. Если вы делаете print(typeof(guess)) вы увидите, что это целое число, 100 также является целым числом, таким образом, это деление приведет к некоторому значению, как 0.3123 который будет усечен до 0, Измените свой вывод на float(guess/100) и это уйдет.

Answer 2

Я надеюсь, что это нормально для меня, чтобы дать ответ на свой вопрос здесь - хотя это не идеальный ответ.

Результаты, которые дает код, кажутся правдоподобными.

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: "))
monthly_salary=starting_annual_salary/12
low=0
high=1000
binary=0
month=1 #set as 1 because the first calculation will occur in month 1
guess=(low+high)//2
current_savings=0
tolerance=500

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

current_savings=calSavings(current_savings,monthly_salary,guess,1)

while True:
    if abs(current_savings-downpayment)<=tolerance: #if the difference between the current savings and downpayment is less than $500
        # record the savings rate as the best guess
        print("The best savings rate is ",guess/10,"%, the amount saved was $",current_savings," in 36 months")
        break #break out of while loop
    elif (current_savings-downpayment)>tolerance: #if amount reached goes over 25% of $1m within 36 months
        #a lower savings rate should be the new guess
        high=guess #high=guess (old guess) and low=low (stays same) and update the guess
        binary=binary+1
        guess=(low+high)//2
        print("The guess was too high, so the new lower savings rate is",guess/10,"%. This is binary-search step",binary)
        current_savings=calSavings(0,monthly_salary,guess,1)
        continue #send new guess up to beginning of while loop to check if conditionals
    elif (downpayment-current_savings)>tolerance: #if amount does not come to within tolerance amount of 25% of $1m within 36 months
        low=guess #to make the guess higher, make low=guess (old guess) and high stay the same
        binary=binary+1
        guess=(low+high)//2
        print("guess is ",guess)
        if guess>=990: #check if the savings rate guess is getting too high
            print("Your wages are too low. You can't save up enough")
            break #exit the while loop because conditions will never be met
        print("The guess was too low, so the new higher savings rate is",guess/10,"%. This is binary-search step",binary)
        current_savings=calSavings(0,monthly_salary,guess,1)
        continue #send new guess up to beginning of while loop to check over the conditionals

Допуск для приемлемого ответа находится в пределах 500 долл., Но если я уменьшу его до 50 долл., Я снова окажусь в бесконечном цикле, где предположение и нижний предел будут одинаковыми. Я счастлив, что достиг определенного прогресса, но сбит с толку тем, что не смогу снизить терпимость, если она снова не заработает.

Кстати, мне не хотелось показаться, что я проигнорировал комментарии Ника о превращении переменных в float, но я объяснил, почему я работал в целых числах в своем комментарии - это кажется правильным?