Форум » Динамическое программирование » 23 задание 163 » Ответить
23 задание 163
Волков Д.А.: 163) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавь 1 2. Прибавь 2 3. Умножь на 2 Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 12 и при этом не содержат двух команд «Прибавить 2» подряд? При решении с помощью динамического программирования не сходится ответ, подскажите что не так? [pre2] k = [0]*13 prev = [0]*13 k[1] = 1 for i in range(2, 12+1): if i % 2 == 0 and prev[i-2]>0: k[ i] += k[ i // 2] + k[ i - 1] elif i % 2 == 0: k[ i] += k[ i // 2] + k[ i - 2] + k[ i - 1] if i>2: prev[ i] += 1 elif prev[i-2]>0: k[ i] += k[i - 1] else: k[ i] += k[ i - 1] + k[ i - 2] if i>2: prev[ i] += 1 print(k[12]) print(k) print(prev) [/pre2]
Ответов - 1
Поляков: Волков Д.А. пишет: не содержат двух команд «Прибавить 2» подряд При решении методом динамического программирования сложно (если вообще можно) отследить выполнение этого условия. Лучше применить рекурсию. [pre2] def f( a, b, prev = 0 ): return 0 if a > b else \ 1 if a == b else \ f(a+1, b, 1) + \ (0 if prev == 2 else f(a+2, b, 2)) + \ f(a*2, b, 3) print( f(1, 12) )[/pre2]
полная версия страницы