Форум » Динамическое программирование » Задача 5076 (Динамическое программирование) » Ответить
Задача 5076 (Динамическое программирование)
Lisizasa: (№ 5076) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавь 1 2. Прибавь 3 3. Умножь на 2 Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 51, и при этом траектория вычислений содержит число 18 и не содержит число 33. Также программа не должна содержать двух команд «Умножь на 2» подряд. Моё решение: [pre2] def foo(s, f, a, k): if s > f: return 0 elif s == a: return 0 elif "33" in k: return 0 elif s == f and ("33" not in k) and s != a: return 1 else: return foo(s + 1, f, a, k + "1") + foo(s + 3, f, a, k + "2") + foo(s * 2, f, a, k + "3") print(foo(2, 18, 33, " ") * foo(18, 51, 33, " ")) [/pre2] Мой ответ: 43416124 Ответ на сайте: 43413100 Где ошибка?
Ответов - 3
zachto: Может быть такой вариант, что вы получаете 18 умножением 9 на 2. Далее новая рекурсия, "счётчик" умножений сбрасывается и вы снова умножаете и получаете 36.
Lisizasa: То есть можно сделать счётчик глобальным, чтобы он не обнулялся?
Поляков: [pre2]def f( start, end, lastCmd ): if start == end: return 1 if start == 33 or start > end: return 0 count = f( start+1, end, 1 ) count += f( start+3, end, 2 ) if start not in [16,17] else 0 count += f( start*2, end, 3 ) if lastCmd != 3 and not(10<=start<=17) else 0 return count print( f( 2, 51, 0 ) )[/pre2]
полная версия страницы