Презентация на тему "МЕТОДИКА РЕШЕНИЯ ЗАДАЧ ЕГЭ ВЫСОКОГО УРОВНЯ 27 (С4)"

Методика решения задач ЕГЭ

Высокого уровня 27 (С4)

Учитель информатики

Шахова Е.А.

ГБОУ «Гимназия №1

им. А.С. Пушкина»

Севастополь, 2017

Спецификация задания №27

согласно КИМ в 2017 ( «ФИПИ»)

Характеристика

Значение

Что проверяется

Умение создавать собственные программы (30–50 строк) для решения задач средней сложности

Требования к проверяемым элементам содержания

Основные этапы разработки программ. Разбиение задачи на подзадачи.

Проверяемые требования к уровню подготовки

Создавать программы на языке программирования по их описанию

Уровень сложности

Высокий

Максимальный балл

4

Примерное время выполнения

55 мин

0 5,7% 16,2% " width="640"

Анализ результатов выполнения задачи в 2016 году

Полученные баллы

1

Процент участников

2

7%

3-4

3,7%

0

5,7%

16,2%

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

• Понятие сложности алгоритма;
• Объявление, ввод массива;
• Записи (структуры данных);
• Работа со строками и символьными переменными;
• Нахождение максимума и минимума в массиве, в последовательности;
• Нахождение суммы, произведения элементов массива, последовательности;
• Свойства кратности, делимости сумм и произведений чисел;
• Сдвиг элементов массива;
• Использование вложенных циклов для полного перебора.

Особенности решения

• Большое количество возможных вариаций задач и их формулировок;
• От учащегося требуются хорошие практически навыки программирования;
• Требуется знать свойства делимости;
• Большое количество приемов и способов решения, которые трудно формализовать;
• Организация оптимального решения требует творческого подхода и тщательного анализа задачи.

Возможные темы задач

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

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

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

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

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

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

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

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

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

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

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

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

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

=1000. Как правильно понимать условие? на первый вопрос – как именно вводятся данные – находим ответ в самом начале условия: вроде бы «дежурная» фраза «на вход программе подаются…» означает, что данные нужно читать не из файла, а со стандартного входного потока; это, в свою очередь, значит, что можно использовать привычные операторы read ( readln ), предполагая, что ктото вводит эти данные с клавиатуры вручную итак, сначала вводится количество записей в файле N , а затем N строк с информацией; заметим, что из всей этой информации нас интересует (в каждой строке) только номер школы, остальное можно просто отбрасывать номер школы стоит после второго пробела в строке « – не более чем двузначный номер » – крайне важная информация; собственно, только она и позволяет найти хорошее решение задачи; это значит, что школ не более 99! что означает выражение «как можно более эффективная программа»? прежде всего, данные читаются только один раз, за один проход, нельзя «вернуться» и прочитать чтото вновь в программе не выполняются никакие лишние действия используемые алгоритмы имеют минимальную сложность (см. выше) расходуется минимальный возможный объем памяти; например, чтобы найти количество отрицательных элементов массива, не нужно вводить второй массив; если нам достаточно держать в памяти одну введенную строку, не нужно одновременно хранить все прочитанные строки зачем нужно уточнение « N=1000 »? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные мы будем считать, что в исходных данных нет ошибок (так принято на олимпиадах и экзаменах), иначе обработка разнообразных ошибок будет составлять основную часть программы Или используется перенаправление входного потока из командной строки, но это уже абсолютно неважно… " width="640"

Возможная формулировка задания (тип I)

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

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

Иванов П.С. 57

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

Как правильно понимать условие?

на первый вопрос – как именно вводятся данные – находим ответ в самом начале условия: вроде бы «дежурная» фраза «на вход программе подаются…» означает, что данные нужно читать не из файла, а со стандартного входного потока; это, в свою очередь, значит, что можно использовать привычные операторы read ( readln ), предполагая, что ктото вводит эти данные с клавиатуры вручную

итак, сначала вводится количество записей в файле N , а затем N строк с информацией; заметим, что из всей этой информации нас интересует (в каждой строке) только номер школы, остальное можно просто отбрасывать

номер школы стоит после второго пробела в строке

« – не более чем двузначный номер » – крайне важная информация; собственно, только она и позволяет найти хорошее решение задачи; это значит, что школ не более 99!

что означает выражение «как можно более эффективная программа»?

прежде всего, данные читаются только один раз, за один проход, нельзя «вернуться» и прочитать чтото вновь

в программе не выполняются никакие лишние действия

используемые алгоритмы имеют минимальную сложность (см. выше)

расходуется минимальный возможный объем памяти; например, чтобы найти количество отрицательных элементов массива, не нужно вводить второй массив; если нам достаточно держать в памяти одну введенную строку, не нужно одновременно хранить все прочитанные строки

зачем нужно уточнение « N=1000 »? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные

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

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

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

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

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

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

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

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

Type Rec=record

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

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

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

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

end;

Возможная формулировка задания (тип II)

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

1.  R  – сумма двух различных переданных элементов последовательности.

2.  R  кратно 3.

3. Если в последовательности нет двух чисел, сумма которых кратна 3, контрольное значение считается равным -1.

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

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

Как правильно понимать условие?

«раз­лич­ные» озна­ча­ет, что нель­зя про­сто удва­и­вать пе­ре­дан­ные числа, суммы раз­лич­ных, но рав­ных по ве­ли­чи­не эле­мен­тов до­пус­ка­ют­ся

Организация полного перебора

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

Rmin:=R;

end;

if Rmin= 2001 then Rmin:=-1;

writeln(Rmin);

End.

Рассказать как выбирается начальное значение Rmin

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

Писать программу эффективную по памяти, но не эффективную по времени не проще, чем просто эффективную по памяти. Задачу на 2 балла легко научиться писать.

Оптимальное решение

ИДЕЯ: Хранить в памяти не все введенные ранее числа, а только те, которые «лучше» остальных.

Чтобы сумма была меньше, нужно брать меньшие числа, достаточно хранить только минимальные, удовлетворяющие условию.

!

?

Сколько таких чисел хранить и какие должны быть условия?

По условию сумма должна быть наименьшей и кратной трем. Хранить только наименьшее нет смысла, потому как с другим наименьшим оно может не дать нужного остатка при делении на 3.

Вывод: следует хранить все минимальные числа, имеющие разные остатки при делении на 3.

Алгоритм оптимального решения

• Считываем количество чисел n .
• Инициализируем переменные.
• Цикл из n итераций

3.1 Чтение очередного числа a .

3.2 Вычисление его остатка от деления на 3.

3.3 Выбираем число, остаток от деления на 3 от которого в сумме с остатком деления a на 3 кратен 3.

3.3 Если их сумма меньше контрольного значения, запоминаем ее как контрольное значение.

3.4 Если число a меньше минимального, имеющего тот же остаток от деления на 3, запоминаем его.

• Если контрольное число не изменилось, запоминаем в него 1.
• Вывод контрольного значения.

Программа для оптимального решения

Var R, Rmin: integer;

n, a, I,m1,m2:integer;

b : array[0..2] of integer;

Begin

Rmin:=2001;

for i:=0 to 2 do b[i]:=1001;

readln(n);

for i:=1 to n do

begin

readln(a);

m1:=(a mod 3); m2:=( 3 - m1)mod 3;

if b[m2]1001 then

begin R:=a+b[m3];

if R

end;

if a

end;

if Rmin=2001 then Rmin:=-1;

writeln(Rmin);

End.

Обратить внимание на порядок!!!!!! Сначала ищем минимальную сумму а потом смотрим заменить ли число с остатком.

Возможная формулировка задания (тип III)

Для заданной последовательности неотрицательных целых чисел необходимо найти минимальную сумму двух её элементов, номера которых различаются не менее чем на 4. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

  Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б.

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

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик)(4 балла).

Как правильно понимать условие?

Решение задачи А (не оптимальное)

Полный перебор похож на решение предыдущей задачи, только нужно брать не соседние пары, а через 4 элемента.

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- 4 do

for j:=i+ 4 to n do

begin

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

if ( R

Rmin:=R;

end;

writeln(Rmin);

End.

( R

Оптимальное решение

2

10

4

6

7

9

8

7

3

8

1

Если нельзя хранить все введенные ранее числа, то сколько чисел хранить в памяти и какие?

?

Во-первых, необходимо хранить числа - «кандидаты» в лучшие для составления с новым полученным числом контрольного значения. Эти числа были получены как минимум за 4 (согласно условию задачи) числа до текущего.

Во-вторых, необходимо хранить предпоследние 3 числа, которые пока не могут быть использованы для формирования контрольного значения, но могут пригодиться для последующих чисел.

2

4

3

8

1

Внимание: если условие для контрольного значения сложное, «кандидатов» может быть несколько, как в предыдущей задаче.

Алгоритм решения задачи Б

• Считываем количество чисел n .
• Инициализация переменных, считываем первое число, сохраняем как лучшее.
• Считываем 3 числа, запоминаем в массив.
• Цикл из n-4 итераций

• 4.1 Чтение очередного числа a. 4.2 Складываем с лучшим. Если их сумма меньше контрольного значения, запоминаем ее как контрольное значение. 4.3 Сравниваем первый элемент массива и лучшее, запоминаем из них лучшее. 4.4 Сдвигаем влево на 1 элементы массива. 4.4 Запоминаем a в последний элемент массива.
• 4.1 Чтение очередного числа a.
• 4.2 Складываем с лучшим. Если их сумма меньше контрольного значения, запоминаем ее как контрольное значение.
• 4.3 Сравниваем первый элемент массива и лучшее, запоминаем из них лучшее.
• 4.4 Сдвигаем влево на 1 элементы массива.
• 4.4 Запоминаем a в последний элемент массива.
• Вывод контрольного значения.

Программа для решения задачи Б

Const delta=4; {минимальный интервал}

Var R : integer; {минимальная сумма}

n, a, m:integer; {количество чисел, очередное значение, лучшее}

b : array[1..delta-1] of integer; {массив промежуточных значений}

Begin

R:=2001;

readln(n);

readln(m);

for i:=1 to delta-1 do readln(b[i]);

for i:= delta+1 to n do

begin

readln(a);

if m+a

if b[1]

for j:=1 to delta-2 do b[i]:=b[i+1];

b[delta-1]:=a;

end;

writeln(R);

End.

Обратить внимание на порядок!!!!!! Сначала ищем минимальную сумму а потом смотрим заменить ли число с остатком.

Модификация задачи (тип III)

Для заданной последовательности положительных целых чисел необходимо найти минимальное, кратное трем произведение двух её элементов, номера которых различаются не менее чем на 5. Если таких чисел нет, вывести 0.

Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

Решение задачи А (не оптимальное)

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- 4 do

for j:=i+ 4 to n do

begin

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

if (R

Rmin:=R;

end;

if Rmin=1000001 then Rmin:=0;

writeln(Rmin);

End.

Longint;

1000001 ;

5

5

( R

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

and( R mod 5 =0) then

Программа для решения задачи Б

Const delta=5; {минимальный интервал}

Var R : longint ;{минимальное произведение}

n, a:integer;{количество чисел, очередное значение}

m, m5:integer;{наименьшее, наименьшее из кратных 5}

b : array[1..delta-1] of integer; {массив промежуточных значений}

Begin

R:=1000001; readln(n); readln(m);

if (m mod 5)=0 then m5:=m else m5:=0;

for i:=1 to delta-1 do readln(b[i]);

for i:= delta+1 to n do

begin

readln(a);

if ((m50) and ((m5*a)

if ((a mod 5)=0) and (a*m

if b[1]

if (b[1]mod 5=0)and (b[1]

for j:=1 to delta-2 do b[i]:=b[i+1]; {сдвиг в массиве}

b[delta-1]:=a;

end;

if Rmin=1000001 then Rmin:=0;

writeln(R);

End.

Обратить внимание на порядок!!!!!! Сначала ищем минимальную сумму а потом смотрим заменить ли число с остатком.

Возможная формулировка задания (тип IV)

На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это целое неотрицательное число. Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. Скорость, по крайней мере, одной частицы нечётна.

При обработке результатов в каждой серии эксперимента отбирается множество скоростей. Это непустое подмножество скоростей частиц (в него могу войти как скорость одной частицы, так и скорости всех частиц серии), такое, что сумма всех значений скоростей у него нечётна и максимальна среди всех возможных непустых подмножеств с нечётной суммой. Если таких подмножеств несколько, то из них выбирается то подмножество, которое содержит наименьшее количество элементов.

.

Как правильно понимать условие?

Идея оптимального решения

Поскольку задачу нужно решать в один проход (если делать оптимальное решение), то сумму надо считать одновременно с чтением данных.

Проблема 1 : сумма должна быть максимальной по значению, но минимальной по количеству.

Вывод : нужно брать все положительные элементы и не брать нулевые.

Проблема 2 : не все числа должны входить в эту сумму, чтобы она была нечетной.

Вывод : надо запоминать «кандидатов» на удаление из последовательности, если сумма вдруг получится четной. Это должно быть нечетное число с одной стороны и минимальное из нечетных, чтобы сумма уменьшилась на минимальное возможное значение.

Программа оптимального решения

Var s: longint ; {сумма}

n, a:integer; {количество чисел, очередное значение}

m :integer; {наименьшее нечетное}

Begin

S:=0;

readln(n);

m:=0;

for i:= 1 to n do

begin

readln(a);

S:=s+a;

if ( (a mod 2)=1) and ((m=0)or (a

end;

if (s mod 2)=0 then s:=s-m;

writeln(R);

End.

Возможная формулировка задания (тип V)

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

Задача А. Количество пар известно заранее и равно 6. Числа не превышают 30 000. (2 балла)

Задача Б. Количество пар N не известно заранее и может принимать значения 2

Как правильно понимать условие?

Решение задачи А

Var a:array[1..6,1..2]of integer;

i,j1,j2,j3,j4,j5,j6 : integer;

s,smin:integer;

Begin

for i:=1 to 6 do

for j1:=1 to 2 do read(a[I,j1]);

smin:=1000*6+1;

for j1:=1 to 2 do

for j2:=1 to 2 do

for j3:=1 to 2 do

for j4:=1 to 2 do

for j5:=1 to 2 do

for j6:=1 to 2 do begin

s:=a[1,j1]+ a[2,j2] +a[3,j3]+ a[4,j4]+ a[5,j5] +a[6,j6];

if (s0) then smin:=s

end;

if smin= 1000*6+1 then smin:=1;

writeln(smin);

End.

Идея решения задачи Б

Поскольку задачу нужно решать в один проход (если делать оптимальное решение), то сумму надо считать одновременно с чтением данных.

Проблема 1 : сумма должна быть минимальной по значению.

Вывод : нужно брать из каждой пары только минимальное число.

Проблема 2 : Сумма может получиться кратной 6.

Вывод : надо запоминать «кандидатов» на замену одного числа из пары на другое, если сумма вдруг получится кратной 6. Число должно иметь, во первых, минимальную разницу с заменяемым, а во-вторых, должно иметь другой остаток при делении на 6, чтобы и сумма поменяла свой остаток от деления. Сумма при этом увеличится именно на разницу между числами, поэтому проще запоминать именно ее.

Решение задачи Б

Var n:integer; {количество чисел}

a, b : integer; {очередная пара чисел}

dmin, d : integer; {минимальная разница между числами в паре}

s:integer; i:integer;

Begin

readln(n);

s:=0; d:=1001;

for i:=1 to n do begin

readln(a,b);

if a

d:=abs(a-b);

if (d0) then dmin:=d;

end;

if s mod 6 =0 then

if dmin=1001 then s:=0

else s:=s+dmin;

writeln(s);

end.

Задачи

Датчик передаёт каждую секунду по каналу связи неотрицательное целое число, не превосходящее 1000 — текущий результат измерений. Временем, в течение которого происходит передача, можно пренебречь.

Необходимо найти в заданной серии показаний датчика минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 8 секунд. Если получить такое произведение не удаётся, ответ считается равным -1. Общее количество показаний датчика в серии не превышает 10 000.

1) в4 2) в9 3) в12

Задачи

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

Задача А. Количество пар известно заранее и равно 6. Числа не превышают 30 000.

Задача Б. Количество пар N не известно заранее и может принимать значения 2

4) в13 5) в16

Список использованных источников

• В.Р. Лещинер, М.А. Ройтберг. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ для учителей, подготовленные на основе анализа типичных ошибок Участников ЕГЭ 2016 года по ИНФОРМАТИКЕ и ИКТ. – http://www.fipi.ru/ege-i-gve-11/analiticheskie-i-metodicheskie-materialy.
• КИМ ЕГЭ «Информатика и ИКТ» http://www.ege.edu.ru/ru/classes-11/preparation/demovers/
• Материалы сайта Полякова К.Ю по подготовке к ЕГЭ http://kpolyakov.spb.ru/school/ege.htm.
• Информатика и ИКТ. Подготовка к ЕГЭ 2016. 20 тренировочных вариантов по демоверсии на 2016 год: учебно методическое пособие / Под ред. Л. Н. Евич, С.Ю. Кулабухова. – Ростов наДону: Легион, 2015.
• Каталог заданий сайта «Решу ЕГЭ». –

https://inf-ege.sdamgia.ru/test?a=catlistwstat