Методический анализ результатов ЕГЭ по информатике (стр. 4 )

Задание 23 (высокого уровня сложности). Задание высокого уровня сложности, проверяющее умение строить и преобразовывать логические выражения. С заданием справилось 20,5%, что на 13,39% выше, чем в прошлом году.

Пример. Сколько различных решений имеет система логических уравнений

(x1 ∧ y1) ≡ (¬x2 ∨ ¬y2)

(x2 ∧ y2) ≡ (¬x3 ∨ ¬y3)

...

(x5 ∧ y5) ≡ (¬x6 ∨ ¬y6),

где x1, …, x6, y1, …, y6, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение (метод битовых цепочек):

перепишем уравнения в более понятном виде:

.

Заметим, что по закону Де Моргана и выполним замену переменных

.

Получаем систему

,

которая может быть записана в виде

и сворачивается в одно уравнение

.

Это уравнение накладывает такое ограничение на битовую цепочку : соседние биты различны, что дает всего дав решения: и . Теперь нужно перейти к исходным переменным, и . Если , то имеем всего один вариант исходных переменных: , то есть единица в решении Z не увеличивает количество решений в исходных переменных. Если , то имеем три варианта исходных переменных: , то есть каждый ноль в решении Z утраивает количество решений в исходных переменных. Поскольку в каждом решении 3 нуля, каждое из двух решений Z даёт 33 = 27 решений в исходных переменных; таким образом, всего решений 2  27 = 54. Ответ: 54.

Решение (оптимизированный метод отображений):

Из анализа системы логических уравнений мы видим, что присутствует 6 переменных Х и 6 переменных У. Так как любая из этих переменных может принимать только два значения (0 и 1), то заменим эти переменные на 12 однотипных переменных, например Z. Теперь перепишем систему с новыми однотипными переменными. ВНИМАНИЕ, сложность задачи будет заключаться во внимательной записи при замене переменных. (z1 ∧ z2) ≡ (¬z3 ∨ ¬z4) (z3 ∧ z4) ≡ (¬z5 ∨ ¬z6) ... (z9 ∧ z10) ≡ (¬z11 ∨ ¬z12) построим таблицу, в которой переберем все варианты z1, z2, z3, z4, поскольку в первом логическом уравнении четыре переменных, то таблица будет иметь 16 строк (16=24); уберем из таблицы (желтая заливка) такие значения z4, при которых первое уравнение не имеет решения.

Z1	Z2	Z3	Z4
0	0	0	0
1
1	0
1
1	0	0
1
1	0
1
1	0	0	0
1
1	0
1
1	0	0
1
1	0
1

Анализируя таблицу, строим правило отображения пар переменных (например, паре Z1Z2=00 соответствует пара Z3Z4 = 11).

Заполняем таблицу, вычисляя количество пар переменных, при котором система имеет решение.

Z1Z2	Z3Z4	Z5Z6	Z7Z8	Z9Z10	Z11Z12
00	1	1	3	3	9	9
01	1	1	3	3	9	9
10	1	1	3	3	9	9
11	1	3	3	9	9	27

Складываем все результаты: 9 + 9 + 9 + 27 = 54. Ответ: 54.

Для успешного выполнения этого задания участник должен провести фактически мини-исследование системы логических выражений. Это оказалось под силу только 20% учащихся.

Задание 24 (повышенный уровень). Справилось 59,4% выпускников, что на 12,48% больше чем в 2017 году. Выпускники 2018 года: не указали, что выдает программа при конкретной входной последовательности и последовательность, при которой программа работает правильно; не увидели первую ошибку или исправили ее неправильно, не исправили вторую ошибку; не поняли условие задачи.

Пример. На вход программы поступает последовательность из четырёх неотрицательных целых чисел (некоторые числа могут быть одинаковыми). Нужно написать программу, которая выводит на экран количество делящихся нацело на 4 чисел в исходной последовательности и максимальное делящееся нацело на 4 число. Если делящихся нацело на 4 чисел нет, требуется на экран вывести «NO». Известно, что вводимые числа не превышают 1000. Программист написал программу неправильно.

Pascal	Python
const n = 4; var i, x: integer; var maximum, count: integer; begin count := 0; maximum := 1000; for i := 1 to n do begin read(x); if x mod 4 = 0 then begin count := count + 1; if x < maximum then maximum := x end end; if count > 0 then begin writeln(count); writeln(maximum) end else writeln('NO') end.	n = 4 count = 0 maximum = 1000 for i in range (1, n+1): x = int(input()) if x % 4 == 0: count += 1 if x < maximum: maximum = x if count > 0: print (count) print (maximum) else: print ("NO")

Последовательно выполните следующее.

1. Напишите, что выведет эта программа при вводе последовательности: 2 8 4 3.

2. Приведите пример такой последовательности, содержащей хотя бы одно делящееся нацело на 4 число, что при её вводе приведённая программа, несмотря на ошибки, выведет правильный ответ.

3. Найдите допущенные программистом ошибки и исправьте их.

Известно, что в тексте программы можно исправить ровно две строки так, чтобы она стала работать правильно.

Решение:

Сначала выполним первое задание. Ручная прокрутка программы для входной последовательности 2 8 4 3 даёт count=2 и maximum=4. Пишем ответ:

1) При вводе чисел 2 8 4 3 программа выведет числа 2 и 4.

Это значит, что количество чисел, делящихся на 4, программа подсчитала правильно (два числа – 8 и 4), а максимальное определила неправильно (4 вместо 8).

При изучении программы вызывает вопросы поиск максимального значения:

maximum := 1000;

for i := 1 to n do begin

...

if x < maximum then

maximum := x

end

end;

Программа фактически ищет не максимальное, а минимальное число, делящееся на 4. Этот вывод совпадает с результатом, которые мы получили в п. 1. Отсюда сразу следует ответ на второй вопрос – программа выведет правильный ответ, если число, делящееся на 4 – всего одно, или есть несколько таких равных чисел.

2) Программа выведет правильный ответ (числа 1 и 4) при вводе чисел 2 1 4 3.

Поняв причину проблемы, легко исправить программу. Начальное значение переменной maximum должно быть равно 0 (или меньше), так чтобы оно было не больше любого подходящего числа (неотрицательного, делящегося на 4). Кроме того, нужно изменить знак в условии, вместо знака «меньше» использовать «больше»:

3) в программе нужно исправить две ошибки

Неверное начальное значение переменной maximum:

Было: maximum:= 1000;

Исправление: maximum:= 0;

Неверное условие при поиске максимума:

Было: if x < maximum then.

Исправление: if x > maximum then.

Задание 25 (высокий уровень). Задание высокого уровня сложности на обработку массива. Справилось 40,9% выпускников, что на 0,33% ниже по сравнению с 2017 годом. Типичные ошибки выпускников: отсутствует в явном виде инициализация счетчиков или сумматора найденных элементов массива, отсутствие фрагмента программы или ее запись с синтаксическими ошибками; не понимание условия задачи; отсутствие описания вводимых элементов в программу.

Пример. Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит самую большую сумму двух соседних элементов и заменяет на эту сумму все элементы, кратные 3. Гарантируется, что в массиве есть хотя бы один элемент, кратный 3. В качестве результата необходимо вывести измененный массив в обратном порядке, каждый элемент массива выводится с новой строчки. Например, для массива из восьми элементов
1 2 6 3 2 7 3 4 программа должна вывести (по одному числу в строке) числа: 4 10 7 2 10 10 2 1.