Question

Исполнитель Прибавитель преобразует число на экране. У исполнителя две команды, которым присвоены номера: 1. Прибавить 1 2. Увеличить старшую цифру числа на 1 Первая команда увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа. Например, число 23 с помощью такой команды превратится в число 33. Если старшая цифра числа равна 9,то вторая команда оставляет это число неизменным. Программа для исполнителя Прибавителя – это последовательность команд. Сколько существует программ, которые число 15 преобразуют в число 36?

Answer 1

1- прибавить 1
2- увеличить на 1

решение:
1. 1 2 2
2. 2 2 1
3. 1 1 1 1 1 1 1 1 1 1 2
4. 2 1х11
5. 1х21
6. 2 1х21
ответ 6

Answer 2

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

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

Построим таблицу DP (динамического программирования), где DP[i][j] будет обозначать количество программ, которые преобразуют число i в число j.

Теперь заполним таблицу DP значениями. Начнем с базовых случаев:

1. DP[i][i] = 1 для всех i, так как единственная программа, которая не меняет число, это пустая программа.
2. DP[i][j] = 0, если i > j, так как невозможно преобразовать число большее, чем текущее.

Затем начнем заполнять таблицу для более сложных случаев:

Для каждой ячейки DP[i][j], где i < j, мы можем получить значение, используя две команды Прибавителя:

1. Прибавить 1: DP[i + 1][j] (переходим от числа i к числу i + 1).
2. Увеличить старшую цифру на 1: DP[i * 10][j] (переходим от числа i к числу i с добавленным нулем в конце).

Таким образом, для каждой ячейки DP[i][j], где i < j, мы суммируем значения DP[i + 1][j] и DP[i * 10][j] для получения общего количества программ, которые преобразуют число i в число j.

Теперь заполним таблицу DP по этим правилам:

cssCopy code
const int MAX_NUMBER = 36;
int DP[MAX_NUMBER + 1][MAX_NUMBER + 1] = {0};

// Заполнение базовых случаев
for (int i = 1; i <= MAX_NUMBER; i++) {
    DP[i][i] = 1;
}

// Заполнение более сложных случаев
for (int i = MAX_NUMBER; i >= 1; i--) {
    for (int j = i + 1; j <= MAX_NUMBER; j++) {
        DP[i][j] = DP[i + 1][j] + (i * 10 <= MAX_NUMBER ? DP[i * 10][j] : 0);
    }
}

Таким образом, значение DP[15][36] даст нам количество программ, которые преобразуют число 15 в число 36:

cssCopy code
int result = DP[15][36];

Выполнив этот код, мы получим значение result, которое покажет количество программ, преобразующих число 15 в число 36 с помощью команд Прибавителя.