Статья "МЕТОДИКА РЕШЕНИЯ ЗАДАЧ ЕГЭ ВЫСОКОГО УРОВНЯ 27 (С4)

10

Автор: учитель информатики Шахова Е.А., г. Севастополь, ГБОУ «Гимназия №1 им. А.С. Пушкина».

Задача №27 в ЕГЭ является задачей высокого уровня, призванная , прежде всего, проверить умения учащихся на практике составлять и реализовывать эффективные и правильные алгоритмы, составлять программы на языках высокого уровня.

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

Заметим, что эта задача имеет самый высокий балл, и на ее выполнение разработчики задания выделают практически четверть общего времени, отводимого на экзамен.

Проанализируем результаты решения этой задачи в 2015-2016 учебном году. Процент выполнения этой задачи представлен в следующей таблице:

Можно заметить очень невысокий процент успешного выполнения данного задания, что можно связать с непривычным типом задания, к которому многие учащиеся были не готовы. Это говорит о низком уровне алгоритмической культуры и отсутствии навыков программирования.

Итак, как же научиться решать эти задания?

Перечислим необходимые для этого знания и умения, базовые алгоритмические задачи и методы:

• понятие сложности алгоритма;

• объявление, ввод массива;

• записи (структуры данных);

• работа со строками и символьными переменными;

• нахождение максимума и минимума в массиве, в последовательности;

• нахождение суммы, произведения элементов массива, последовательности;

• свойства кратности, делимости сумм и произведений чисел;

• сдвиг элементов массива;

• использование вложенных циклов для полного перебора.

В качестве особенностей решения задачи можно выделить следующие:

• большое количество возможных вариаций задач и их формулировок;

• от учащегося требуются хорошие практически навыки программирования;

• требуется знать свойства делимости;

• большое количество приемов и способов решения, которые трудно формализовать;

• организация оптимального решения требует творческого подхода и тщательного анализа задачи.

Перед тем как говорить о решении задач, вспомним необходимые понятия.

Сложность алгоритмов

Сложность алгоритма – это количественная характеристика ресурсов, необходимых алгоритму для работы (успешного решения задачи).

Основные ресурсы:

• время (временнáя сложность) и

• объем памяти (ёмкостная сложность).

Наиболее важной характеристикой является время.

Сложность задачи может быть разной для разных входных данных (экземпляров задачи).

Различают сложность в худшем случае и сложность в среднем.

В теории сложности чаще оперируют понятием сложности в худшем случае.

Обычно оценивают порядок роста сложности при n®¥: T = O(f(n)).

• Фактическая сложность (время работы в секундах) зависит не только от алгоритма, но и от скорости работы компьютера.

• Именно порядок роста сложности ограничивает размер решаемых задач.

Например, если сравнивать порядок зависимости времени решения задачи, можно привести данные, представленные в таблице:

Выделим основные типы и темы заданий:

1. Обработка данных, вводимых в виде символьных строк или последовательности чисел.

2. Проверка контрольного значения среди последовательности чисел.

3. Поиск пар с определенными свойствами среди множества экспериментальных значений с заданными интервалом между индексами.

4. Выбор подмножества элементов с определенным набором свойств.

5. Выбор одного значения из пары с нахождением суммы или произведения с определёнными свойствами.

Рассмотрим каждый тип задачи отдельно.

На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат:

где – строка, состоящая не более чем из 20 символов, – строка, состоящая из 4-х символов (буква, точка, буква, точка), – не более чем двузначный номер. и , а также и разделены одним пробелом. Пример входной строки:

Иванов П.С. 57

Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, BorlandPascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ может быть несколько). При этом необходимо вывести информацию только по школам, пославшим хотя бы одного участника. Следует учитывать, что N=1000.

Данные задачи включались в экзамен несколько лет назад, сейчас не встречаются, но для полной картины следует рассмотреть и такие задачи тоже.

Необходимые знания и умения:

1. Решение задачи разбиения строки на подстроки по пробелам.

Функции и процедуры (Pascal) : pos, copy, delete, length, insert.

1. Преобразование строки в число, в цифры.

Функции и процедуры (Pascal) : val, StrToInt (Delphi).

1. Работа с символами. Функции (Pascal): ord, chr.

2. Работа с записями (структурами).

Type Rec=record

{поля записи}

F:string[20]; {фамилия}

IO: string[4]; {инициалы}

num: integer;{номер школы}

end;

Подробно останавливаться не будем из-за неактуальности.

По каналу связи передаются положительные целые числа, не превышающие 1000, – результаты измерений, полученных в ходе эксперимента (количество измерений известно заранее). После окончания эксперимента передаётся контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:

1) R — сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются);

2) R — нечётное число.

Если чисел, соответствующих приведённым условиям, нет, считается, что R = –1. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, FreePascal 2.6.4), которая будет проверять правильность контрольного значения.

Перед текстом программы кратко опишите используемый Вами алгоритм решения.

На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:

6

100

8

33

45

19

90

145

Пример выходных данных:

145

Рассмотрим неоптимальное решение полным перебором, которое оценивается в 2 балла.

При неоптимальном решении все данные сначала сохраняются в массиве, а затем в двойном цикле рассматриваются все возможные пары чисел.

Текст программы (авторский).

Var a:array [1..10000] of integer;

n, i, j: integer;

Rmin, R : integer;

Begin

readln(n);

for i:=1 to n do

readln(a[i]);

Rmin:=2001;

for i:=1 to n-1 do

for j:=i+1 to n do

begin

R:=a[i]+a[j];

{проверка условия контрольного значения}

if (R then Rmin:=R;