Форум » Динамическое программирование » Тема 23 задача 5403 » Ответить
Тема 23 задача 5403
ganilova: Моё решение [pre2] def f(x, k): if x == 100 and k % 2 == 1: return 1 if x > 100 or k > 50: return 0 p1 = f(x + 2, k + 1) p2 = f(x * 2, k + 1) p3 = f(x ** 2, k + 1) return p1 + p2 + p3 print(f(1, 0)) [/pre2] Выдает 29431 вместо 1025, причем если меняю условие в строке if x > 100 or k > 50: например на if x > 100 or k > 100: то ответ 80781 чего по идее не должно быть. Подскажите пожалуйста, что я делаю не так?
Ответов - 6
zachto: По условию можно бесконечное число раз возводить единицу в квадрат
ganilova: Спасибо!
flo23: Покажите, пожалуйста, итоговую правильную программу
flo23: Если у вас получилось правильно решить данную задачу, то не могли бы вы показать верное решение?
MrAndrewson: Из первой 1 можно сделать числа 3, 2 и 1. Чтобы посчитать количество программ для первой 2 и 3, можно воспользоваться кодом [pre2]def f(st, fn, ln): if st > fn: return 0 if st == fn and ln % 2 == 0: return 1 return f(st + 2, fn, ln + 1) + f(st * 2, fn, ln + 1) + f(st ** 2, fn, ln + 1) print(f(2, 100, 0) + f(3, 100, 0)) [/pre2] Но что мешает первые две команды сделать 3 3, т.е. возвести единицу дважды в квадрат и снова получится та же ситуация, еще столько же программ. Более того, из первой единицы, полученной возведением в квадрат тоже есть программы, ведущие в 100 за нечетное количество команд. Такое решение будет давать верный ответ, но оно неверное, потому что не учитывает возведение в квадрат 1 [pre2]def f(st, fn, ln): if st > fn: return 0 if st == fn and ln % 2 == 1: return 1 if st != 1: return f(st + 2, fn, ln + 1) + f(st * 2, fn, ln + 1) + f(st ** 2, fn, ln + 1) else: return f(st + 2, fn, ln + 1) + f(st * 2, fn, ln + 1) print(f(1, 100, 0)) [/pre2]
Danov: Замечание верное. Добавим в условие уточнение "команды, которые увеличивают число" Решение: [pre]def f(a,k=0): return a<100 and \ f(a+2,k+1)+f(a*2,k+1)+ (a>1 and f(a*a,k+1))\ or a==100 and k%2 print(f(1))[/pre]
полная версия страницы