Форум » Динамическое программирование » 23 задание » Ответить
23 задание
Мария_1: Константин Юрьевич, объясните, пожалуйста, на примере решения, хотя бы, 173-й задачи задания №23, что значит условие "Также программа не должна содержать двух команд «Умножь на 2» подряд."
Ответов - 2
Поляков: Вот решение 173-й задачи (оно есть на сайте): [pre2] def f( start, end, lastCmd = 0 ): 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 ) )[/pre2]Третий параметр - номер последней выполненной команды. Если он равен 3, то следующей командой не может быть команда 3. Если текущая позиция 16 или 17, то команда 2 (+3) перепрыгивает 18, и поэтому такой вариант блокируется. Команда 3 перепрыгивает 18 из позиций 10...17, поэтому эти варианты тоже блокируются. Для ускорения можно добавить кэширование:[pre2] from functools import lru_cache @lru_cache def f( start, end, lastCmd = 0): 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 ) )[/pre2]
Мария_1: Спасибо большое, Константин Юрьевич!
полная версия страницы