Question

Помогите, пожалуйста. 1) У исполнителя Калькулятор три команды, которым присвоены номера: 1. прибавь 1 2. прибавь 3 3. прибавь 6 Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 21 преобразуют в число 30? 2) У исполнителя Калькулятор три команды, которым присвоены номера: 1. прибавь 2 2. прибавь 3 3. прибавь 5 Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 20 преобразуют в число 35? 3) У исполнителя Калькулятор три команды, которым присвоены номера: 1. прибавь 1 2. прибавь 4 3. прибавь 5 Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 30 преобразуют в число 46?

Answer 1

1) 25
21 + 3  + 6  = 30
21 + 6  + 3  = 30
21 + 3  + 3  + 3  = 30
21 + 1  + 1  + 1  + 6  = 30
21 + 1  + 1  + 6  + 1  = 30
21 + 1  + 6  + 1  + 1  = 30
21 + 6  + 1  + 1  + 1  = 30
21 + 1  + 1  + 1  + 3  + 3  = 30
21 + 1  + 1  + 3  + 1  + 3  = 30
21 + 1  + 1  + 3  + 3  + 1  = 30
21 + 1  + 3  + 1  + 1  + 3  = 30
21 + 1  + 3  + 1  + 3  + 1  = 30
21 + 1  + 3  + 3  + 1  + 1  = 30
21 + 3  + 1  + 1  + 1  + 3  = 30
21 + 3  + 1  + 1  + 3  + 1  = 30
21 + 3  + 1  + 3  + 1  + 1  = 30
21 + 3  + 3  + 1  + 1  + 1  = 30
21 + 1  + 1  + 1  + 1  + 1  + 1  + 3  = 30
21 + 1  + 1  + 1  + 1  + 1  + 3  + 1  = 30
21 + 1  + 1  + 1  + 1  + 3  + 1  + 1  = 30
21 + 1  + 1  + 1  + 3  + 1  + 1  + 1  = 30
21 + 1  + 1  + 3  + 1  + 1  + 1  + 1  = 30
21 + 1  + 3  + 1  + 1  + 1  + 1  + 1  = 30
21 + 3  + 1  + 1  + 1  + 1  + 1  + 1  = 30
21 + 1  + 1  + 1  + 1  + 1  + 1  + 1  + 1  + 1  = 30

2)77
20 + 5  + 5  + 5  = 35
20 + 2  + 3  + 5  + 5  = 35
20 + 2  + 5  + 3  + 5  = 35
20 + 2  + 5  + 5  + 3  = 35
20 + 3  + 2  + 5  + 5  = 35
20 + 3  + 5  + 2  + 5  = 35
20 + 3  + 5  + 5  + 2  = 35
20 + 5  + 2  + 3  + 5  = 35
20 + 5  + 2  + 5  + 3  = 35
20 + 5  + 3  + 2  + 5  = 35
20 + 5  + 3  + 5  + 2  = 35
20 + 5  + 5  + 2  + 3  = 35
20 + 5  + 5  + 3  + 2  = 35
20 + 2  + 2  + 3  + 3  + 5  = 35
20 + 2  + 2  + 3  + 5  + 3  = 35
20 + 2  + 2  + 5  + 3  + 3  = 35
20 + 2  + 3  + 2  + 3  + 5  = 35
20 + 2  + 3  + 2  + 5  + 3  = 35
20 + 2  + 3  + 3  + 2  + 5  = 35
20 + 2  + 3  + 3  + 5  + 2  = 35
20 + 2  + 3  + 5  + 2  + 3  = 35
20 + 2  + 3  + 5  + 3  + 2  = 35
20 + 2  + 5  + 2  + 3  + 3  = 35
20 + 2  + 5  + 3  + 2  + 3  = 35
20 + 2  + 5  + 3  + 3  + 2  = 35
20 + 3  + 2  + 2  + 3  + 5  = 35
20 + 3  + 2  + 2  + 5  + 3  = 35
20 + 3  + 2  + 3  + 2  + 5  = 35
20 + 3  + 2  + 3  + 5  + 2  = 35
20 + 3  + 2  + 5  + 2  + 3  = 35
20 + 3  + 2  + 5  + 3  + 2  = 35
20 + 3  + 3  + 2  + 2  + 5  = 35
20 + 3  + 3  + 2  + 5  + 2  = 35
20 + 3  + 3  + 3  + 3  + 3  = 35
20 + 3  + 3  + 5  + 2  + 2  = 35
20 + 3  + 5  + 2  + 2  + 3  = 35
20 + 3  + 5  + 2  + 3  + 2  = 35
20 + 3  + 5  + 3  + 2  + 2  = 35
20 + 5  + 2  + 2  + 3  + 3  = 35
20 + 5  + 2  + 3  + 2  + 3  = 35
20 + 5  + 2  + 3  + 3  + 2  = 35
20 + 5  + 3  + 2  + 2  + 3  = 35
20 + 5  + 3  + 2  + 3  + 2  = 35
20 + 5  + 3  + 3  + 2  + 2  = 35
20 + 2  + 2  + 2  + 2  + 2  + 5  = 35
20 + 2  + 2  + 2  + 2  + 5  + 2  = 35
20 + 2  + 2  + 2  + 3  + 3  + 3  = 35
20 + 2  + 2  + 2  + 5  + 2  + 2  = 35
20 + 2  + 2  + 3  + 2  + 3  + 3  = 35
20 + 2  + 2  + 3  + 3  + 2  + 3  = 35
20 + 2  + 2  + 3  + 3  + 3  + 2  = 35
20 + 2  + 2  + 5  + 2  + 2  + 2  = 35
20 + 2  + 3  + 2  + 2  + 3  + 3  = 35
20 + 2  + 3  + 2  + 3  + 2  + 3  = 35
20 + 2  + 3  + 2  + 3  + 3  + 2  = 35
20 + 2  + 3  + 3  + 2  + 2  + 3  = 35
20 + 2  + 3  + 3  + 2  + 3  + 2  = 35
20 + 2  + 3  + 3  + 3  + 2  + 2  = 35
20 + 2  + 5  + 2  + 2  + 2  + 2  = 35
20 + 3  + 2  + 2  + 2  + 3  + 3  = 35
20 + 3  + 2  + 2  + 3  + 2  + 3  = 35
20 + 3  + 2  + 2  + 3  + 3  + 2  = 35
20 + 3  + 2  + 3  + 2  + 2  + 3  = 35
20 + 3  + 2  + 3  + 2  + 3  + 2  = 35
20 + 3  + 2  + 3  + 3  + 2  + 2  = 35
20 + 3  + 3  + 2  + 2  + 2  + 3  = 35
20 + 3  + 3  + 2  + 2  + 3  + 2  = 35
20 + 3  + 3  + 2  + 3  + 2  + 2  = 35
20 + 3  + 3  + 3  + 2  + 2  + 2  = 35
20 + 5  + 2  + 2  + 2  + 2  + 2  = 35
20 + 2  + 2  + 2  + 2  + 2  + 2  + 3  = 35
20 + 2  + 2  + 2  + 2  + 2  + 3  + 2  = 35
20 + 2  + 2  + 2  + 2  + 3  + 2  + 2  = 35
20 + 2  + 2  + 2  + 3  + 2  + 2  + 2  = 35
20 + 2  + 2  + 3  + 2  + 2  + 2  + 2  = 35
20 + 2  + 3  + 2  + 2  + 2  + 2  + 2  = 35
20 + 3  + 2  + 2  + 2  + 2  + 2  + 2  = 35

3)301
увы все варианты в ответ не поместились

Answer 2

Для решения этих задач можно использовать динамическое программирование, так как нам нужно найти количество способов достичь определенного числа, используя заданные команды. Давайте рассмотрим каждую задачу по отдельности.

1. Преобразование числа 21 в число 30 с помощью команд прибавления 1, 3 и 6:

Создадим массив dp, где dp[i] будет обозначать количество способов получить число i с использованием заданных команд. Изначально все значения dp[i] будут равны 0, кроме dp[21], которое будет равно 1 (начальное число).

Затем мы будем идти по всем числам от 21 до 30 и обновлять значения dp[i] следующим образом:

dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 6]

Таким образом, dp[30] будет содержать количество способов достичь числа 30:

plaintextCopy code
dp[21] = 1
dp[22] = dp[21] = 1
dp[23] = dp[22] + dp[20] + dp[17] = 1 + 0 + 0 = 1
...
dp[30] = dp[29] + dp[27] + dp[24] = 1 + 1 + 1 = 3

Ответ: Существует 3 программы, которые преобразуют число 21 в число 30.

2. Преобразование числа 20 в число 35 с помощью команд прибавления 2, 3 и 5:

Аналогично первой задаче, создаем массив dp и обновляем его значения:

plaintextCopy code
dp[20] = 1
dp[21] = dp[20] = 1
dp[22] = dp[21] + dp[19] + dp[17] = 1 + 0 + 0 = 1
...
dp[35] = dp[34] + dp[32] + dp[30] = 4 + 3 + 1 = 8

Ответ: Существует 8 программ, которые преобразуют число 20 в число 35.

3. Преобразование числа 30 в число 46 с помощью команд прибавления 1, 4 и 5:

Аналогично решаем задачу:

plaintextCopy code
dp[30] = 1
dp[31] = dp[30] = 1
dp[32] = dp[31] + dp[28] + dp[27] = 1 + 0 + 0 = 1
...
dp[46] = dp[45] + dp[42] + dp[41] = 1 + 0 + 1 = 2

Ответ: Существует 2 программы, которые преобразуют число 30 в число 46.