Подготовка к ЕГЭ по информатике (задание 27)

Методика подготовки обучающихся к решению задачи егэ по информатике и икт №27

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

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

им. К.А. Тренева» г. Симферополя

Т.Ю. Буркова

Основные характеристики задачи 27

Уровень сложности – высокий

Время выполнения - 55 минут.

Максимальный первичный балл – 4 балла.

Элементы содержания, проверяемые на ЕГЭ: Основные этапы разработки программ. Разбиение задачи на подзадачи. Умение создавать собственные программы (30–50 строк) для решения задач средней сложности

Проверяемые умения или способы действий: Создавать программы на языке программирования по их описанию

Кодификатор элементов содержания и требований к уровню подготовки выпускников образовательных организаций для проведения единого государственного экзамена по информатике и ИКТ

Возможные алгоритмические задачи для подраздела 1.1 перечня требований к уровню подготовки выпускников, достижение которых проверяется на едином государственном экзамене по информатике и ИКТ.

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

− Запись натурального числа в позиционной системе с основанием, меньшим или равным 10. Обработка и преобразование такой записи числа.

− Нахождение сумм, произведений элементов данной конечной числовой последовательности (или массива).

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

− Заполнение элементов одномерного и двумерного массивов по заданным правилам.

− Операции с элементами массива. Линейный поиск элемента. Вставка и удаление элементов в массиве. Перестановка элементов данного массива в обратном порядке. Суммирование элементов массива. Проверка соответствия элементов массива некоторому условию.

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

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

− Операции с элементами массива, отобранных по некоторому условию (например, нахождение минимального четного элемента в массиве, нахождение количества и суммы всех четных элементов в массиве).

− Сортировка массива. − Слияние двух упорядоченных массивов в один без использования сортировки.

− Обработка отдельных символов данной строки. Подсчет частоты появления символа в строке.

− Работа с подстроками данной строки с разбиением на слова по пробельным символам. Поиск подстроки внутри данной строки, замена найденной подстроки на другую строку.

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

Задача б

Задача а

• Максимальный балл
• – 4 балла
• Решение должно быть эффективным по времени и по памяти

• Максимальный балл – 2 балла
• Решение может быть неэффективным по времени и по памяти
• Может быть указано исходное количество обрабатываемых значений

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

эффективность по времени

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

Наиболее ценным ресурсом в этой задаче считается время. Эффективность по времени расценивается «дороже», чем эффективность по памяти. Как же написать эффективную по времени программу?

Обозначим время выполнения программы T. Допустим, нам нужно последовательно просмотреть в цикле N элементов массива. Тогда время выполнения программы будет прямо пропорционально количеству элементов (T~N).

Если же для каждого из N элементов нам нужно заново просмотреть весь массив (цикл в цикле), то время будет пропорционально квадрату количества элементов.

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

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

При оценивании указано, что рекурсивный алгоритм не считается эффективным по времени

Эффективность по памяти

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

Переборное решение (задача а)

i

i

1

1

1

1

2

2

2

2

3

v

3

3

3

v

4

4

4

4

5

5

5

5

v

v

v

v

v

6

6

6

v

6

7

7

7

v

v

v

v

v

7

v

(n)

v

v

(n)

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

j

j

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

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

Переборное решение (задача а)

i

i

j

1

1

2

2

3

3

v

v

4

4

5

5

v

v

v

v

6

6

v

v

7

v

7

v

v

(n)

v

v

v

v

v

v

v

v

v

v

j

1

1

2

2

3

3

4

4

5

5

v

v

6

6

7

7

v

v

v

(n)

v

v

v

v

v

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

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

i

1

j

2

i+ 1

.

.

.

.

N- 1

N

i

1

j

2

i+k

.

.

.

.

N-k

N

Переборное решение (задача а)

1

2

1

1

2

1

2

2

1

2

1

2

i 1

i 2

i 3

i 4

i 5

i 6

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

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

9

На что обратить внимание

• Параметры изменения счетчиков
• Инициализация счетчиков, переменных для поиска максимальных и минимальных значений
• Вывод результата
• Типы данных
• Оформление решения
• Пояснение

9

• Компьютер наземной станции слежения получает от объектов – самолетов, находящихся в зоне ее работы, идентификационные сигналы, представляющие собой последовательность из N целых положительных чисел. Каждый объект направляет на наземную станцию уникальное число, т.е. все числа в получаемой станцией последовательности различны. Обработка сигнала представляет собой рассмотрение всех пар различных элементов последовательности, при этом элементы пары не обязаны быть переданы непосредственно друг за другом, порядок элементов в паре не важен. Считается, что возникла критическая ситуация, если произведение элементов некоторой пары кратно 58. Необходимо определить общее количество возникших критических ситуаций.
• Описание входных и выходных данных.
• В первой строке входных данных задается количество чисел N (1
• В качестве результата программа должна напечатать одно число: общее количество возникших критических ситуаций.

В задании 27 встречаются несколько типов задач. Рассмотрим их подробнее. В качестве источника задач будем использовать сборник «ЕГЭ 2016 Информатика и ИКТ 20 вариантов» С.С. Крылова и Т.Е.Чуркиной.

9

Когда произведение двух чисел делится на 58?

Когда оба сомножителя делятся на 58.

Только один сомножитель делится на 58.

Одно число делится на 2, другое на 29.

n58*(n58-1)/2

n58*(N-n58)

n2*n29

9

Комбинаторная формула

i

i

1

1

1

1

2

2

2

2

v

3

3

3

3

v

4

4

4

4

5

5

v

5

v

v

5

v

v

6

v

6

6

6

v

v

7(n)

7

7

7(n)

v

v

v

(n)

(n)

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

v

j

j

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

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

n(n-1)/2

(n-k+1)(n-k)/2

n58 = 0

n29 = 0

n2 = 0

N = int(input())

for i in range(N):

temp= int(input())

if temp%58 == 0:

n58++

elif temp%29 ==0:

n29++

elif temp%2 == 0:

n2++

crypt = (n58*(n58-1))/2 + n58*(N-n58) +n29*n2

print(crypt)

var a: array [1..5] of integer;

kp, k13, kn13, i, n, b: integer;

begin

kp:=0;

k13:=0;

kn13:=0;

for i:=1 to 5 do readln( a[i]);

for i:=6 to n do

begin

if a[i mod 5] mod 13=0

then k13:= k13 + 1

else kn13 :=kn13 + 1;

readln (b);

if b mod 13 0

then kp:= kp + k13

else kp := kp + k13 + kn13;

a[i mod 5] :=b;

end;

writeln (kp);

end.

• Датчик передает каждую секунду по каналу связи неотрицательное целое число, не превосходящее 1000, - текущий результат измерений. Временем, в течение которого происходит передача, можно пренебречь.
• Необходимо найти в заданной серии показаний датчика минимальное четное произведение двух показаний, между моментами передачи которых прошло не менее 15 секунд. Если получить такое произведение не удается, ответ считается равным -1. Общее количество показаний датчика в серии не превышает 10 000.
• А. Напишите программу, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.
• Б. Напишите программу, которая будет эффективной по времени и по памяти.

N; for (int i=0; i cin a; mas.push(a); } min = -1; min_out15_even = 0; min_out15 = 0; for (i=0; i a = mas.pop(); if ((a%2==0)&&(min_out15_even==0 || a if (min_out15==0 || a cin a; mas.push(a); if (a%2==0) temp=min_out15*a; else temp=min_out15_even*a; if (min==-1 || mintemp) min = temp; } cout } " width="640"

#include

#include

using namespace std;

int main(){

queue mas;

int N, a;

long int min, min_out15_even, minn_out15, temp;

cin N;

for (int i=0; i

cin a;

mas.push(a);

}

min = -1;

min_out15_even = 0;

min_out15 = 0;

for (i=0; i

a = mas.pop();

if ((a%2==0)&&(min_out15_even==0 || a

if (min_out15==0 || a

cin a;

mas.push(a);

if (a%2==0) temp=min_out15*a;

else temp=min_out15_even*a;

if (min==-1 || mintemp) min = temp;

}

cout

}

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

N; for (int i=0;i cin max_t min_t; if (min_t max_t){ temp = max_t; max_t = min_t; main_t = temp; } max += max_t; temp = max_t – min_t; if (temp%5 != 0){ if (min_d == 0 || min_d temp) min_d = temp; } } If (max %5 != 0) cout else if (min_d 0){ max -= min_d; cout } else cout } " width="640"

#include

using namespace std;

int main(){

int max, max_t, min_t, min_d, temp;

int N;

max = 0;

min_d = 0;

cin N;

for (int i=0;i

cin max_t min_t;

if (min_t max_t){

temp = max_t;

max_t = min_t;

main_t = temp;

}

max += max_t;

temp = max_t – min_t;

if (temp%5 != 0){

if (min_d == 0 || min_d temp) min_d = temp;

}

}

If (max %5 != 0) cout

else if (min_d 0){

max -= min_d;

cout

} else cout

}