Разбор 22 задания ЕГЭ 2016 по информатике из демоверсии
Разбор 22 задания ЕГЭ 2016 года по информатике из демоверсии. Это задание на умение анализировать результат исполнения алгоритма (уметь cтроить информационные модели объектов, систем и процессов в виде алгоритмов). Это задание повышенного уровня сложности. Примерное время выполнения задания 7 минут.
Задание 22:
Исполнитель Май 15 преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя Май 15 – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Разбор 22 задания ЕГЭ 2016:
Решим нашу задачу в два этапа:
1 этап. Найдем количество программ Получить из 2 — 14
2 этап. Найдем количество программ Получить из 14 — 29, не проходя число 25
Найдем минимальное число, из которого существует два способа получения числа 14:
14/2 = 7 (это число 7)
Все числа, большие 7 имеют только один способ получения числа 14 (с помощью команды +1)
Рассмотрим числа, меньшие 7:
6: *2=12 (1 способ) или +1=7 (2 способа) Итого: 3
5: *2=10 (1 способ) или +1=6 (3 способа) Итого: 4
4: *2=8 (1 способ) или +1=5 (4 способа) Итого: 5
3: *2=6 (3 способа) или +1=4 (5 способов) Итого: 8
2: *2=4 (5 способов) или +1=3 (8 способов) Итого: 13
Итого, у числа 2 есть 13 способов получения числа 14.
Для того, чтобы перескочить число 25, нужно использовать команду *2.
Минимальное число, к которому можно применить эту команду равно 14 (14*2=28).
Есть только один спобоб получения числа 29 из 28: 28 + 1
Вывод: Количество решений равно: 13*1 = 13
Е23.22 при исходном числе 2 результатом является число 29
Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
Исполнитель Май15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май15 – это последовательность команд.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Решение задания 23 в электронных таблицах с помощью функции ИНДЕКС
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
Решение (электронные таблицы Excel, LibreOffice Calc с помощью функции ИНДЕКС):
- Основная идея решения заключается в том, что количество программ для данного числа равно сумме аналогичных значений чисел, в которые можно попасть из данного с помощью команд
- будем использовать возможность функции ИНДЕКС возвращать значение из ячейки, адрес которой можно вычислить. Для этого функции надо знать диапазон, в котором брать значения и номер строки и столбца внутри диапазона
- поскольку траектория содержит число 14, разобьем решение на два этапа
- найдем количество программ, для которых при исходном числе 2 результатом будет 14. В столбец А внесем числа от 2 до 14 так, чтобы каждое число совпадало с номером строки
- в столбец B внесем формулу для подсчета количества программ. В ячейке B2 это будет формула =ИНДЕКС(B$1:B$100;A2+1)+ИНДЕКС(B$1:B$100;A2*2)
- в функции ИНДЕКС(B$1:B$100;A2+1) B$1:B$100 это диапазон, внутри которого мы будем брать значения. Начинаться он должен с первой строки для того, чтобы нумерация строк внутри диапазона совпала с нумерацией чисел при вычислениях. А заканчиваться в такой ячейке, номер которой позволит взять любое число. В данном случае для расчета количества программ для числа 13 надо взять значения чисел 14 и 26. Значит, диапазон должен включать хотя бы 26 строк. Число 100 взято с запасом. Абсолютная адресация позволит эту формулу скопировать в другие ячейки стоблца B. A2 + 1 это вычисление из какой строки надо взять данные. По условию задачи у нас две команды: +1 и *2, соответственно, для подсчета количества программ в ячейке B2, которая соответствует числу 2, мы возьмем числа из строк 2 + 1 = 3 и 2 * 2 = 4
- данную формулу мы копируем на ячейки диапазона B3:B13, а в ячейку B14 внесем 1
- вторая часть решения – количество программ из 14 в 29. Построим данную часть правее, в столбцах С и D. Для корректной работы функции ИНДЕКС с формулами важно числа писать в совпадающие по номеру строки, а диапазон в формуле начинать с первой строки. Внесем формулу =ИНДЕКС(D$1:D100;C14+1)+ИНДЕКС(D$1:D100;C14*2) в ячейку D14, скопируем ее до ячейки D28, а в ячейку D29 внесем 1. Для того, чтобы учесть, что в 25 нельзя, просто удалим значение в столбце D напротив 25
- в ячейке B2 получилось количество программ, которыми можно попасть из 2 в 14, а в ячейке D14 количество программ из 14 в 29 минуя 25. Для получения итогового ответа перемножим эти числа: 13*1=13
- Ответ: 13
комментария 2
Подскажите, как быть с заданиями, содержащими вычитание:
Исполнитель А22 преобразует целое число, записанное на экране.
У исполнителя три команды, каждой команде присвоен номер:
3. Прибавь предыдущее
Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 3, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя А22 – это последовательность команд.
Понятная информатика,

Динамическое программирование – это способ или техника решения сложных задач путем приведения их к более простым подзадачам того же типа.
Динамическое программирование позволяет решать задачи, которые требуют полного перебора вариантов. Задание может звучать так:
«подсчитайте количество способов…»;
«как оптимально распределить…»;
«найдите оптимальный маршрут…».
Динамическое программирование позволяет увеличить скорость выполнения программы за счет эффективного использования памяти; полный перебор всех вариантов не требуется, поскольку запоминаются и используются решения всех подзадач с меньшими значениями параметров.
Пример 1.
У исполнителя Калькулятор две команды, которым присвоены номера:
Сколько есть программ, которые число 1 преобразуют в число 55?
Обозначим через N текущее (получаемое) число, а через K(N) – количество различных программ для получения этого числа.
Число N может быть получено одной из двух операций:
— увеличением на 1 числа N-1 (предыдущего числа);
— умножением на 4 числа N/4 (только для N, которые делятся на 4).
Тогда получаем следующие рекуррентные формулы:
K(N)= K(N-1) — для чисел, не кратных 4;
K(N) =K(N-1) +K(N/4) — для чисел, кратных 4.
Заполним таблицу получения чисел от 1 до 55, указывая в ней только кратные 4 числа, так как числа, лежащие в промежутке между ними всегда равны предыдущему значению для кратного числа:
Здесь при N = 4 получаем K4=К3+К4/4= К3+К1=1+1=2;
N = 8 получаем K8=К7+К4/2= К4+К2 =2+1=3, и так далее.
А если посмотреть внимательно, то можно и сделать еще быстрее: так как числа кратны 4, то каждое увеличение выполняется по 4 раза (13 1, по 2, по 3…)
Пример 2.
Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Число N могло быть получено одной из двух операций:
— увеличением на 1 числа N-1;
— умножением на 2 числа N/2 (только для N, которые делятся на 2);
K(N) = K(N-1) — для нечётных чисел
K(N) = K(N-1) + К(N/2) — для чётных чисел
Поскольку траектория должна проходить через число 10, сначала выясняем, сколькими способами можно получить 10 из 1, а затем будем считать, сколько есть способов получить 21 из 10
Заполняем таблицу от 1 до 10 по полученным формулам:

Второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 21 из 10, только левую часть таблицы (от 1 до 10) мы уже не рассматриваем:

На втором этапе можно использовать и такую идею: если мы знаем количество команд, с помощью которых из начального числа 1 можно получить 10 и определим количество команд, с помощью которых из 10 можно получить конечное значение 21, останется только перемножить эти два числа – это и будет ответ
Составляем таблицу для получения 21 из 10, используя те же рекуррентные формулы:

Результат : 14 * 2 = 28
Пример 3.
Исполнитель М17 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
3. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая – увеличивает его на 2, а третья – умножает его на 3. Программа для исполнителя М17 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и при этом траектория вычислений содержит числа 8 и 10?
Запишем рекуррентную формулу для вычисления K(N) – количества возможных программ для получения числа N из некоторого начального числа:
K(N) = K(N-1) +К(N-2), если N не делится на 3
K(N) = K(N-1) +К(N-2) +К(N/3), если N делится на 3
Все допустимые программы можно разбить на 3 части:
– переход от 2 до 8
– переход от 8 до 10
– переход от 10 до 12

Обозначим через К(a->b) количество возможных программ получения числа b из числа a
Очевидно, что К(a->b) = К(a->c) * К(c->b) для любого c, такого что a < c < b
Вычисляем эти значения отдельно стандартным способом по рекуррентным формулам п. 1:

и перемножаем: 15 × 2 × 2 = 60
Пример 4.
Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
В этом задании две особые точки – числа 14 (через которое должна проходить траектория) и 25 (а сюда она попасть НЕ должна)
Сначала, так же, как и в задачах, рассмотренных выше, составляем рекуррентную формулу, по которой будем вычислять количество K(N) обозначить количество разных программ для получения числа N из начального числа:
Число N могло быть получено одной из двух операций:
— увеличением на 1 числа N-1;
— умножением на 2 числа N/2 (только для N, которые делятся на 2);
K(N) = K(N-1) — для нечётных чисел
K(N) = K(N-1) + К(N/2) — для чётных чисел
Для начального числа 2 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; K(1) = 1.