Форум » Динамическое программирование » вопрос по условию! » Ответить
вопрос по условию!
elzara: 152) (А. Богданов) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавь 1 2. Прибавь 2 Первая команда увеличивает число на 1, вторая – на 2. Сколько существует таких программ, которые исходное число 11 преобразуют в число 29, и при этом траектория вычислений содержит либо 17, либо 23, либо 17 и 23 одновременно? Что означает условие 17 либо 23 или либо 17 и 23? как решать такую задачу.
Ответов - 10
Поляков: Подходят 3 варианта 1) есть 17, нет 23 2) нет 17, есть 23 3) есть 17 и есть 23. Остальные не подходят. Проще подсчитать те, которые не подходят, и вычесть из общего количества.
elzara:
bliss61@mail.ru: Мой код def f(x, y): if x == y: return 1 if x > y: return 0 if x < y: return f(x + 1, y) + f(x + 2, y) print(f(11, 17) * f(17, 29) + f(11, 23) * f(23, 29) + f(11,17) * f(17,23) * f(23, 29)) Ответ 8255 , который не сходится с 3861. Ошибок в программе не вижу
Danov: bliss61@mail.ru пишет: print(f(11, 17) * f(17, 29) + f(11, 23) * f(23, 29) + f(11,17) * f(17,23) * f(23, 29)) Ответ 8255 , который не сходится с 3861. Ошибок в программе не вижу а где контроль того, что чисел нет? (нет 23, но есть 17) + (нет 17, но есть 23) + (есть 17 и 23) для первых двух как раз завышение
Поляков: bliss61@mail.ru пишет: Ответ 8255 , который не сходится с 3861. Ошибок в программе не вижу Вы несколько раз учитываете программы, которые проходят и через 17, и через 23.
bliss61@mail.ru: Но в условии не сказано, что когда 23 или 17, то один из низ не проходит через при 23 - 17 и при 17-23. На мой взгляд тогда условие не корректно Сколько существует таких программ, которые исходное число 11 преобразуют в число 29, и при этом траектория вычислений содержит либо 17, либо 23, либо 17 и 23 одновременно
100 balnik: def F(x,y): if x==y :return 1 if x>y or x==17 or x==23:return 0 return F(x+1,y)+F(x+2,y) print(F(11,29))
100 balnik: Там получается сначала ищем все варианты получаем 4181,потом считаем то, что не подходит (код выше) и потом отнимаем 4181-320=3861
Mark12: def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x + 2, y) def f1(x, y): if x > y or x == 17 or x == 23: return 0 if x == y: return 1 return f1(x + 1, y) + f1(x + 2, y) print(f(11, 29) - f1(11, 29))
Ж: f=lambda n,k: f(n+1,k+[n])+f(n+2,k+[n]) if n<29 else n==29 and (17 in k or 23 in k) print(f(11,[]))
полная версия страницы