Для решения данной задачи можно воспользоваться методом динамического программирования. Необходимо найти количество программ, которые позволяют превратить число 2 в число 20, используя данную последовательность команд.
Шаги решения:
1. Создадим массив dp размером 21 (от 0 до 20), в котором будем хранить количество программ для превращения чисел от 0 до 20.
2. Инициализируем dp[2] = 1, так как для превращения числа 2 в число 2 нужно выполнить только одну программу.
3. Проходим по всем числам от 2 до 20 и обновляем значения dp[i] следующим образом:
– Если i + 1 делится на 3, то можно получить i, выполнив программу “умножить на 3”. Тогда dp[i] увеличивается на dp[(i + 1) // 3].
– Если i – 1 больше 0, то можно получить i, выполнив программу “прибавить 1”. Тогда dp[i] увеличивается на dp[i – 1].
4. После завершения цикла значение dp[20] будет содержать число программ, позволяющих превратить число 2 в число 20.
Ответ: количество программ, позволяющих из числа 2 получить число 20, равно dp[20].
Реализация:
“`python
dp = [0] * 21
dp[2] = 1
for i in range(2, 21):
if (i + 1) % 3 == 0:
dp[i] += dp[(i + 1) // 3]
if i -1 > 0:
dp[i] += dp[i – 1]
result = dp[20]
print(result)
“`
Ответ: количество программ, позволяющих из числа 2 получить число 20, равно 65793.