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

Question

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

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

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

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

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

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, но я объяснил, почему я работал в целых числах в своем комментарии - это кажется правильным?

Answer 2

Обновление

Причина, по которой ваш цикл не останавливается, заключается в том, что вы не уделяете ему достаточно времени. То, что вы забыли, так это то, что вы имеете дело с типом 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 всегда будет False.

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

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