Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера. 1.  Прибавить 1. 2.  Прибавить 2. 3.  Прибавить 3. Программа для исполнителя  — это последовательность команд. Сколько существует программ, для которых при

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

Нам нужно найти количество программ, которые начинают с числа 1 и заканчиваются на числе 35, при этом проходя через число 7. Мы можем разбить задачу на две части: 1. Найти количество способов добраться от 1 до 7. 2. Найти количество способов добраться от 7 до 35. Для подсчета количества способов, которыми можно добраться от 1 до 7, мы можем использовать рекурсию. Обозначим f(n) как количество способов добраться до числа n. - f(1) = 1 (начальная позиция) - f(2) = f(1) = 1 (только один способ: 1 + 1) - f(3) = f(2) + f(1) = 2 (два способа: 1 + 2 или 1 + 1 + 1) - f(4) = f(3) + f(2) + f(1) = 4 - f(5) = f(4) + f(3) + f(2) = 7 - f(6) = f(5) + f(4) + f(3) = 13 - f(7) = f(6) + f(5) + f(4) = 24 Таким образом, количество способов добраться от 1 до 7 равно f(7) = 24. Теперь нам нужно найти количество способов добраться от 7 до 35. Мы можем использовать тот же подход: - g(7) = 1 (начальная позиция) - g(8) = g(7) = 1 - g(9) = g(8) + g(7) = 2 - g(10) = g(9) + g(8) + g(7) = 4 - g(11) = g(10) + g(9) + g(8) = 7 - g(12) = g(11) + g(10) + g(9) = 13 - g(13) = g(12) + g(11) + g(10) = 24 - g(14) = g(13) + g(12) + g(11) = 44 - g(15) = g(14) + g(13) + g(12) = 81 - g(16) = g(15) + g(14) + g(13) = 149 - g(17) = g(16) + g(15) + g(14) = 274 - g(18) = g(17) + g(16) + g(15) = 504 - g(19) = g(18) + g(17) + g(16) = 927 - g(20) = g(19) + g(18) + g(17) = 1705 - g(21) = g(20) + g(19) + g(18) = 3136 - g(22) = g(21) + g(20) + g(19) = 5768 - g(23) = g(22) + g(21) + g(20) = 10609 - g(24) = g(23) + g(22) + g(21) = 19513 - g(25) = g(24) + g(23) + g(22) = 35890 - g(26) = g(25) + g(24) + g(23) = 66012 - g(27) = g(26) + g(25) + g(24) = 121415 - g(28) = g(27) + g(26) + g(25) = 223317 - g(29) = g(28) + g(27) + g(26) = 410744 - g(30) = g(29) + g(28) + g(27) = 755476 - g(31) = g(30) + g(29) + g(28) = 1389537 - g(32) = g(31) + g(30) + g(29) = 2555757 - g(33) = g(32) + g(31) + g(30) = 4700770 - g(34) = g(33) + g(32) + g(31) = 8646064 - g(35) = g(34) + g(33) + g(32) = 15902591 Таким образом, количество способов добраться от 7 до 35 равно g(35) = 15902591. Теперь, чтобы найти общее количество программ, которые начинаются с 1, проходят через 7 и заканчиваются на 35, мы просто перемножим количество способов добраться от 1 до 7 и от 7 до 35: Общее количество программ = f(7) × g(35) = 24 × 15902591 = 381622464 Таким образом, существует 381622464 программ, которые при исходном числе 1 приводят к числу 35 и содержат число 7.