22. Перебор вариантов, динамическое программирование

Демонстрационный вариант Единый государственный экзамен ЕГЭ 2017 г. – задание №22. Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?

Исполнитель А16 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     1. Прибавить 1
     2. Прибавить 2
     3. Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2,третья умножает его на 2.
Программа для исполнителя А16 – это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

Решение:

1. Прибавить 1
2. Прибавить 2
3. Умножить на 2

Разобъём задачу на 2 этапа: получить из 3 – 10 и получить из 10 – 12

1) Из 3 – 10

4 из 3 можем получить только 1 способом: 3+1=4 (1 способ)

5 из 3 можем получить 2 способами: 4+1 (1) и 3+2 (1) (2 способа)

6 из 3 можем получить 4 способами: 5+1 (2); 4+2 (1) и  3*2 (1) (4 способа)

7 из 3 можем получить 6 способами: 6+1 (4); 5+2 (2) (6 способов)

8 из 3 можем получить 11 способами: 7+1 (6); 6+2 (4) и  4*2 (1) (11 способов)

9 из 3 можем получить 17 способами: 8+1 (11); 7+2 (6)  (17 способов)

10 из 3 можем получить 30 способами: 9+1 (17); 8+2 (11) и  5*2 (2) (30 способов)

2) Из 10 – 12

12 из 10 можно получить 2 способами:

  1. Сразу 12 из 10: 10+2
  2. Сначала получаем 11: 10+1, потом 12 из 11: 11+1

10 из 3 можем получить 30 способами, 12 из 10 можно получить 2 способами:

2*30=60

3 4 5 6 7 8 9 10 11 12
1 1
1 1 2
1 1 2 4
2 4 6
1 4 6 11
6 11 17
2 11 17 30
30 30
30 30 60

Ответ: 60

Демонстрационный вариант Единый государственный экзамен ЕГЭ 2016 г. – задание №22

Исполнитель Май15 преобразует число на экране.
У исполнителя есть две команды, которым присвое­ны номера:

1. Прибавить 1
2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение:

Разобъём задачу на 2 этапа: получить из 2 – 14 и получить из 14 – 29

1) Из 2 – 14

3 из 2 можем получить только 1 способом: 2+1=3 (1 способ)

4 из 2 можем получить 2 способами: 3+1 (1) и 2*2 (1) (2 способа)

5 из 2 можем получить 2 способами: 4+1 (2)  (2 способа)

6 из 2 можем получить 3 способами: 5+1 (2) и 3*2 (1) (3 способа)

7 из 2 можем получить 3 способами: 6+1 (3) (3 способа)

8 из 2 можем получить 5 способами: 7+1 (3) и  4*2 (2) (5 способов)

9 из 2 можем получить 5 способами: 8+1 (5)  (5 способов)

10 из 2 можем получить 7 способами: 9+1 (5) и  5*2 (2) (7 способов)

11 из 2 можем получить 5 способами: 10+1 (7)  (7 способов)

12 из 2 можем получить 10 способами: 11+1 (7) и  6*2 (3) (10 способов)

13 из 2 можем получить 10 способами: 12+1 (10)  (10 способов)

14 из 2 можем получить 13 способами: 12+1 (10) и  7*2 (3) (13 способов)

2) Из 14 – 29

Траектория вычислений не содержит числа 25, значит, 29 из 14 мы не можем получить, используя только команду №1 ( Прибавить 1).

Поэтому для получения 29 из 14, мы 14 умножаем на 2 и прибавляем 1:

14*2=28 (1 способ)

28+1=19(1 способ)

14 из 2 можем получить 13 способами, 29 из 14 можно получить 1 способом:

13*1=13

Ответ:13 

У исполнителя Калькулятор две команды, которым присвоены номера:

  1. прибавь 1
  2. умножь на 2

Сколько есть программ, которые число 1 преобразуют в число 16?  

Решение:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 36

Ответ: 36

У исполнителя Калькулятор две команды, которым присвоены номера:

  1. прибавь 1
  2. увеличь каждый разряд числа на 1

Например, число 23 с помощью команды 2 превратится в 34, а 29 в 39 (так как младший разряд нельзя увеличить). Если перед выполнением команды 2 какая-либо цифра равна 9, она не изменяется. Сколько есть программ, которые число 25 преобразуют в число 51?

Решение:

25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
 1 1 1 1 1 1 1 1 1 1 1 2 3 4 4+1+1=6 6

 

41 42 43 44 45 46 47 48 49 50 51
7 8 9 10 11 12 14 17 17+4+6=27 27 27+6=33

Ответ: 33

Исполнитель А12S преобразует целое число, записанное на экране. У исполнителя три команды, каждой команде присвоен номер:

  1. Прибавь 1
  2. Прибавь 2
  3. Прибавь предыдущее

Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя А12S – это последовательность команд.

Сколько существует программ, которые число 3 преобразуют в число 10?

Решение:

3 4 5 6 7 8 9 10
1 1 3 4 8 12 23 35
1+1+1 3+1 4+3+1 8+4 12+8+3 23+12

Ответ: 35

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

  1. Прибавить 1
  2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 34 и при этом траектория вычислений содержит число 12?

Решение:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 2 2 3 3 5 5 7 7 10 10 10 10 10 10 10 10 10

 

21 22 23 24 25 26 27 28 29 30 31 32 33 34
10 10 10 20 20 30 30 40 40 50 50 60 60 70

Ответ: 70

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

  1. Прибавить 1
  2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 40 и при этом траектория вычислений содержит число 20 и не содержит число 8?

Решение:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 2 2 3 3  2 2 5 5 8 8 8 8 8 8 10

 

 21 22 23 24 25 26 27 28 29 30 31 32 33  34  35  36 37 38 39 40
10 10  10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 20

Ответ: 20

Исполнитель Июнь16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

  1. Прибавить 1
  2. Прибавить 2
  3. Умножить на 2

Сколько существует программ, для которых при исходном числе 3 результатом является число 13 и при этом траектория вычислений содержит число 10?

Решение:

3 4 5 6 7 8 9 10 11 12 13
1 1 2 4 6 11 17 30 30 60 90
1+1 1+1+2 2+4 1+4+6 6+11 2+11+17 30+30 30+60

Ответ: 90