Исполнитель А16 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Пр...
Условие:
Исполнитель А16 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2.
Программа для исполнителя А16 – это последовательность команд.
Сколько суще
Решение:
Сколько существует программ, которые преобразуют число 3 в число 10?
Для решения этой задачи можно использовать метод динамического программирования. Мы можем рассмотреть все возможные программы, которые преобразуют число 3 в число 10, и посчитать их количество.
Пусть dp[i] будет количество программ, которые преобразуют число i в число 10. Тогда мы можем выразить dp[i] через значения dp[i-1], dp[i-2] и dp[i/2], так как каждая команда может быть применена к числу i-1, i-2 или i/2.
Исходя из этого, мы можем записать следующее рекуррентное соотношение:
dp[i] = dp[i-1] + dp[i-2] + dp[i/2]
Начальные значения для dp[3] и dp[4] равны 1, так как существует только одна программа, которая преобразует число 3 в число 10 (последовательность команд 3-1-1-1-1-1-1-1-1-1) и только одна программа,...
