Пошаговый разбор решения задания 22 демоверсии ЕГЭ 2017 на динамическое программирование.
  главная : карта раздела : автора  
 


Интерактивный тренажер задания 22 демонстрационной версии ЕГЭ 2017 на
"Динамическое программирование "

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


 

Дополнительные материалы к уроку

 

Интерактивные демонстрации по применению рекуррентных формул


Примеры решений с помощью использования рекуррентных формул

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

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

РЕШЕНИЕ через рекуррентные формулы:
Для записи рекуррентных формул перепишем заданные команды на обратные
для команды 1, обратной будет команда: вычти 1, а для второй - вычти 2 и для третей раздели на 2, откуда следует, что:
если число делится на 2, то F(n) = F(n/2)+F(n-2) + F(n-1)
если число не делится на 2, то F(n) = F(n-2) + F(n-1)

Далее заполняем таблицу с заголовками N и F(n) следующим образом:
Напротив N = 3 ставим значение F(n) = 1, поскольку помним правило: «число из самого себя можно получить с помощью только одной пустой программы».
Следующие значения рассчитываем по созданным формулам.
N_____F(n)
N = 3 F(n) = 1
N = 4 F(4) = F(2) + F(2) + F(3) = 1
N = 5 F(5) = F(3) + F(4) = 2
N = 6 F(6) = F(3) + F(4) + F(5) = 4
N = 7 F(7) = F(5) + F(6) = 6
N = 8 F(8) = F(4) + F(6) + F(7) = 11
N = 9 F(9) = F(7) + F(8) = 17
N = 10 F(10) = F(5) + F(8) + F(9) = 30

Первую точку нашли. таким образом, при N = 10 значение F(n) = 30

Для прохождения второй точки строим новую таблицу с начальным значением N=10 и F(n)=12,
а все предыдущие значения приравниваем к нулю и используя старые формулы продолжаем расчет значений для новой таблицы

N = 10 F(n) = 30
N = 11 F(11) = F(9) + F(10) = 30
N = 12 F(12) = F(6) + F(10) + F(11) = 60

Таким образом, правильный ответ: 60


Исполнитель Май15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май15 – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 29, и при этом траектория вычислений содержит число 14 и не содержит числа 25?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17. В этом задании траектория лежит через число 14 и не проходит число 25, следовательно, на первом этапе мы должны дойти до числа 14, пользуясь последовательно командами 1 и 2. А сделать это можно как минимум двумя способами, а именно: первый способ - рассуждения и, соответственно, второй - составлением рекуррентных формулРешение рассуждением (или решение в "лоб"):
  1. из числа 2 можно получить число 3, выполнив команду 1. 2+1 = 3, т.е. для получения из двойки тройку существует только одна программа - 1
  2. из числа 2 можно получить число 4 уже двумя способами 2+1+1 = 4 и 2*2 = 4, т.е. существует две программы: 11 и 2
  3. далее будем записывать кратко из 2->5 - 1) 2+1+1+1 2) 2*2+1 - существует только две программы: 111 и 21
  4. 2->6 - 1) 2+1+1+1+1; 2) 2*2+1+1; 3) (2+1)*2 - три программы: 1111; 211 и 12
  5. 2->7 - я придумал только три программы: 11111; 2111 и 121 если у вас получится больше, то пишите, обсудим. (назовем их основополагающими и для удобства раскрасим в разные цвета: 11111; 2111 и 121, а далее, чтобы не запутаться, будем их увеличивать последовательно на 1 с последующим сокращением длины кода...)
  6. 2->8 - 111111;21111;1211; но программу 111111можно записать и так 112; а программу 21111 так: 22 итого получаем 5 программ (далее, следуя этой логике, получаем следующие строки)
  7. 2->9 - 1111111;211111;12111;1121;221 итого 5 программ
  8. 2->10 - 11111111;2111111;121111;11211;2211 и 1112; 212 итого 7 программ
  9. 2->11 - 111111111; 21111111; 1211111; 112111; 22111 и 11121; 2121 итого 7 программ
  10. 2->12 - 1111111111; 211111111; 12111111; 1121111; 221111 и 111211; 21211 и 11112; 2112; 122 итого 10 программ
  11. 2->13 - 11111111111; 2111111111; 121111111; 11211111; 2211111 и 1112111; 212111 и 111121; 21121; 1221 итого 10 программ
  12. 2->14 - 111111111111; 21111111111; 1211111111; 112111111; 22111111 и 11121111; 2121111 и 1111211; 211211;12211 и 111112; 21112; 12112 = 13
Итак, мы нашли, что для получения из числа 2 числа 14 существует 13 различных программ. Допустим, мы дойдем так до числа 24, и следующая команда +1 даст число 25, но оно запрещено! Следовательно, нам нельзя делать команду +1. Остается команда *2, но 24*2 = 48 и мы не попадем на нужное число 29допустим, дойдем до 23, но +1 приводит к рассмотренному выше случаю, как и для 24, поскольку 23*2 = 46 - опять перебор. Если допустить число 15, то снова15*2 =30.получается, что для того, чтобы избежать попадания в число 25,после получения числа 14 необходимо поставить команду 2 и 1 т.е. 14*2=28+1 = 29. Нам остается в строке пункта 12 в конце каждой программы добавить код 21 и посмотреть, можно ли укоротить какую-либо из них: 11111111111121; 2111111111121; 121111111121; 11211111121; 2211111121;1112111121; 212111121; 111121121; 21121121;1221121;11111221; 2111221; 1211221 Попробуйте сократить длину любой из данных программ, мне этого сделать не удалось, следовательно, для получения числа 29 из числа 2, с учетом того, что траектория должна содержать число 12 и не содержать 25, есть всего 13 программ. Правильный ответ: 13

Интерактивный тренажер 22 ЕГЭ ДЕМО 2016
"Динамическое программирование "

Решение с помощью рекуррентных формул:

Для составления рекуррентных формул переменим заданные программы на обратные и запомним, что для получения числа самого из себя существует ровно одна программа, которая ничего не делает. итак,  условие:
1. Прибавить 1
, меняем на вычти 1 или кратко N-1 а условие:
2. Умножить на 2, меняем на раздели на 2 или кратко N/2 исходя из этого, составляем следующие рекуррентные формулы:
если заданное число N делится на 2, то F(n) = F(n/2)+F(n-1)
если заданное число N не делится на 2, то F(n) = (n-1)
Далее с помощью формул необходимо заполнить таблицу. Напротив числа 2 сразу же ставим 1, поскольку помним правило: «число из самого себя можно получить с помощью одной программы». После чего берем число 3. Оно на 2 не делится, поэтому пользуемся второй формулой F(n) = F(n-1) где вместо n, подставив число 3,  получаем  F(3) = F(3-1) = F(2) = 1. Напротив 3 ставим 1. И переходим к следующему числу 4, оно делится на два, поэтому берем первую формулу: F(n) = F(n/2) + F(n-1) = F(2)+F(3) = 1+1 = 2  и т.д. Заполняем табличку до первой точки  N = 14

N          F(n)
2             1
3             1
4             2
5             2
6             3
7             3
8             5
9             5
10           7
11           7
12           10
13           10
14           13

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

F(15) = F(n-1) = F(15-1) = F(14) = 13.
F(16) = F(n/2)+ F(n-1) =  F(8)+F(15) = 0+13 = 13. (F(8) = 0, так как числа 8 в данной таблице нет)
F(17) = F(16) =13.
F(18)=  F(9)+F(17) = 0+13 = 13.  (F(9) = 0, так как числа “9” в данной таблице нет и так далее до числа 25)

N          F(n)
14           13
15           13
16           13
17           13
18           13
19           13
20           13
21           13
22           13
23           13
24           13
25           0   - хотя F(25) = F(25-1) = F(24) = 13, мы поставили ноль программ, поскольку этого числа получить не нужно
26           0, так как F(26/2)+F(26-1) = F(13)+F(25) = 0 (числа  13 в этой таблице нет)+0 = 0
27           0,  так как F(27)=F(27-1) = F(26)=0
28           13, так как F(28) = F(28/2)+F(28-1)=F(14)+F(27) = 13+0
29           13, так как F(29) = F(29-1)= F(28) = 13 Правильный ответ: 13


Динамическое программирование ЕГЭ 2015

Примеры задач и их решений генерируемых интерактивным тренажером "Динамическое программирование"

Задание №1

У исполнителя Калькулятор две команды, которым присвоены номера:
          1. прибавь 2
          2. возведи в квадрат
Первая из них увеличивает число на экране на 2, а вторая возводит его в квадрат. Программа для Калькулятора – это последовательность команд.
Сколько есть программ, которые число 3 преобразуют в число 46? Ответ обоснуйте.
РЕШЕНИЕ через использование рекуррентных формул:
В строке N = 3 записываем значение К = 1, т.к. любое число можно получить с помощью одной пустой программы. Записываем рекуррентные формулы.       если можно извлечь корень квадратный из N, то K(N) = K(N-2) + K(корень квадратный из N)       иначе K(N) = K(N-2)с помощью рекуррентных формул заполняем таблицу для всех значений от 3 до 46:N = 3 : К = 1N = 4 : К =0N = 5 : К = 0 N = 6 : К = 1N = 6 : К = 0N = 7 : К = 0 N = 8 : К = 0 N = 9 : К = 1N =10 : К = 0N = 11 : К = 0 N = 12 : К = 1......N = 18 : К = 1.....N = 24 : К = 1.....N = 36 : К = 2 .....N = 46 : К = 0 где многоточие озночает, что для очередных значений N : K = 0 - длинновато, конечно, но что поделать...
Таким образом правильный ответ :0

Задание №2

У исполнителя Калькулятор три команды, которым присвоены номера:
          1. умножь на 2
          2. прибавь 2
Сколько есть программ, которые число 3 преобразуют в число 51? Ответ обоснуйте.

РЕШЕНИЕ с помощью рекуррентных формул:

В строке N = 3 записываем значение К = 1, т.к. любое число можно получить с помощью одной пустой программы. Записываем рекуррентные формулы.       если N делится на 2, то K(N) = K(N-2) + K(N/2)       если N не делится на 2, то K(N) = K(N-2)с помощью рекуррентных формул заполняем таблицу для всех значений от 3 до 51:N = 3 : К = 1N = 4 : К = 0N = 5 : К = 1N = 6 : К = 1N = 7 : К = 1N = 8 : К = 1N = 9 : К = 1N = 10 : К = 2N = 11 : К = 1N = 12 : К = 3N = 13 : К = 1 N = 14 : К = 4N = 15 : К = 1 N = 16 : К = 5N = 17 : К = 1N = 18 : К = 6 N = 19 : К = 1N = 20 : К = 7N = 21 : К = 1N = 22 : К = 8N = 23 : К = 1 24: 12 25: 1 26: 13 27: 1 28: 17 29: 1 30: 18 31: 1 32: 23 33: 1 34: 24 35: 1 36: 30 37: 1 38: 31 39: 1 40: 39 41: 1 42: 40 43: 1 44: 49 45: 1 46: 50 47: 1 48: 62 49: 1 50: 63 51: 1

Таким образом правильный ответ :1

Задание №3

У исполнителя КАЛЬКУЛЯТОР две команды, которым присвоены номера:
          1.      прибавь 1
          2.      увеличь две младшие цифры на 1
Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков и число единиц. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд.Сколько есть программ, которые число 13 преобразуют в число 50?

Решение:

Очевидно, что при выполнении любой из предложенных команд начальное число только увеличивается и не может уменьшаться!При заданных командах очередное число N может быть получено четырьмя способами:  - для всех чисел, больших начального числа -  увеличением на 1  - увеличением обеих цифр на 1 в результате выполнения команды 2 (то есть, фактически командой «+11») – для всех чисел, больших или равных 13 + 11 = 24, которые НЕ оканчиваются на 0  - увеличением только старшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+10») – для всех чисел, больших 24 и имеющих 9 на конце  - увеличением только младшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+1») – для всех чисел от 91 до 99, но в нашем диапазоне (13..50) таких неттаким образом, приходим к выводу что в данном случае можно воспользоваться тремя рекуррентными формулами, которые принимают вид:   K(N) = K(N-1) - для чисел, меньших, чем 24, а также для всех чисел, оканчивающихся на 0   K(N) = K(N-1) + K(N -11) - для чисел, больших или равных 24, кроме тех что оканчиваются на 9    K(N) = K(N-1) + K(N -11) + K(N -10) - для чисел, оканчивающихся на 9 В строке N = 13 записываем значение К = 1, т.к. любое число можно получить из самого себя с помощью одной пустой программы, а значения остальных строк расчитываем с помощью рекуррентных формул:N = 13: K = 1N = 14: K = 1N = 15: K = 1N = 16: K = 1N = 17: K = 1N = 18: K = 1N = 19: K = 1N = 20: K = 1N = 21: K = 1N = 22: K = 1N = 23: K = 1N = 24: K = 2N = 25: K = 3N = 26: K = 4N = 27: K = 5N = 28: K = 6N = 29: K = 8N = 30: K = 8N = 31: K = 9N = 32: K = 10N = 33: K = 11N = 34: K = 12N = 35: K = 14N = 36: K = 17N = 37: K = 21N = 38: K = 26N = 39: K = 40N = 40: K = 40N = 41: K = 48N = 42: K = 57N = 43: K = 67N = 44: K = 78N = 45: K = 90N = 46: K = 104N = 47: K = 121N = 48: K = 142N = 49: K = 208N = 50: K = 208

Ответ: 208

Задание №4

У исполнителя Калькулятор три команды, которым присвоены номера:
          1. прибавь 1
          2. умножь на 2
          3. умножь на 5
Первая из них увеличивает число на экране на 1, вторая увеличивает его в 2 раза, а третья - в 5 раз. Программа для Калькулятора – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 35?

РЕШЕНИЕ через использование рекуррентных формул: 

   если N/2 и  N/5, то K(N) = K(N-1)+K(N/2)+K(N/5)    если N не делится на 2 и  N не делится на 5, то K(N) = K(N-1)    если N не делится на 2, но  N/5, то K(N) = K(N-1)+K(N/5)    если N/2, но не делится на 5, то K(N) = K(N-1)+K(N/2)вспомним, что любое число можно получить из самого себя с помощью одной пустой программы, поэтому в начальную строку таблимцы вписываем:N = 1: К = 1, а далее заполняем, пользуясь формулами записанными выше 2: 2 3: 2 4: 4 5: 5 6: 7 7: 7 8: 11 9: 11 10: 18 11: 18 12: 25 13: 25 14: 32 15: 34 16: 45 17: 45 18: 56 19: 56 20: 78 21: 78 22: 96 23: 96 24: 121 25: 126 26: 151 27: 151 28: 183 29: 183 30: 224 31: 224 32: 269 33: 269 34: 314 35: 321

Таким образом правильный ответ :321

Задание №5

У исполнителя КАЛЬКУЛЯТОР две команды, которым присвоены номера:
          1.      прибавь 1
          2.      увеличь вторую с конца цифру на 1
Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд.Сколько есть программ, которые число 19 преобразуют в число 35?Ответ обоснуйте

Решение:

Очевидно, что при выполнении любой из предложенных команд начальное число только увеличивается и не может уменьшаться!При заданных командах очередное число N может быть получено двумя способами:  - для всех чисел, больших начального числа -  увеличением на 1  - для всех чисел, больших или равных 29 увеличением числа десятков на 1 то есть, фактически командой «+10»таким образом, рекуррентные формулы принимают вид:   K(N) = K(N-1) - для чисел, меньших, чем 29    K(N) = K(N-1) + K(N -10) - для чисел, больших или равных 29 В строке N = 19 записываем значение К = 1, т.к. любое число можно получить из самого себя с помощью одной пустой программы, а значения остальных строк расчитываем с помощью рекуррентных формул:N = 19: K = 1N = 20: K = 1N = 21: K = 1N = 22: K = 1N = 23: K = 1N = 24: K = 1N = 25: K = 1N = 26: K = 1N = 27: K = 1N = 28: K = 1N = 29: K = 2N = 30: K = 3N = 31: K = 4N = 32: K = 5N = 33: K = 6N = 34: K = 7N = 35: K = 8 Ответ: 8

Таким образом правильный ответ: 8


Возникли вопросы, сомнения или появились замечания, пишите...

 
© Северобайкальск, Russia
Александр Козлов, 2017

  Рейтинг@Mail.ru