Загрузка...Задание КИМ № 23: Динамическое программирование (количество программ)
Раздел № 79: Динамическое программирование: три команды
У исполнителя Калькулятор четыре команды, которым присвоены номера:
1. прибавь 1 2. сделай чётное 3. сделай нечётное 4. умножь на 10 Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1, четвертая умножает на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 15? |
def f (start,end):
if start==end:
return 1
if start>end:
return 0
return f (start+1,end) +f(start*2,end) +f(start*2+1,end)+f(start*10,end)
print(f(1,15))
84
Сайт Полякова