Введение
Здравствуйте! Я — студент математического факультета, учусь на 3 курсе и так уж вышло, что я увлекся решением задач ЕГЭ части C как по математике, так и по информатике.
К сожалению, на ЕГЭ по информатике обращают меньше всего внимания. Вы спросите, почему я так решил? Да хотя бы, потому что на протяжении 7 лет задания по математике меняются из года в год, причем коренным образом, а по информатике как были, так и остались. Каждый год я видел одни и те же задания. И знаете что?! Это действительно надоело, потому что ЕГЭ по информатике превращается в своего рода – «набей руку на решение однотипных задач и получи свою пятерку».
В 2012 году на ЕГЭ по информатике, наконец, обратили внимание. И оно поменялось (причем все три части A, B, C).
Все кому интересно посмотреть на задачи, которые были на протяжении 7 лет и на то, как они были изменены в 2012 году, прошу подкат. Мы будем рассматривать C часть, так как, именно, она представляет больший интерес. Хотя А и B части по информатики тоже очень серьезно изменились, их мы рассмотрим в следующий раз, если это Вам будет интересно.
Задачи, которые были до 2012 года
С1
Задача С1 является классической задачей о попадании точки в некоторую область, которая задана графически. Помню, как с этими задачками нас запаривали на первом курсе…
Собственно условие задачи:
Требовалось написать программу, при выполнении которой с клавиатуры считываются координаты точки на плоскости (x, y – действительные числа) и определяется принадлежность этой точки заданной заштрихованной области (включая границы). Программист торопился и написал программу неправильно.
Программа на языке Pascal
var x, y: real;
begin
readln(x,y);
if y<=x then
if y<=-x then
if y>=x*x-2 then
write('принадлежит')
else
write('не принадлежит')
end.
|
Требуется выполнить последовательно следующее:
1) Приведите пример таких чисел x, y, при которых программа неправильно решает поставленную задачу.
2) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой правильный способ доработки исходной программы.)
Давайте выполним каждый из пунктов.
1) Для решения пункта 1 необходимо понять, что делает исходная программа. После небольших рассуждений можно сделать вывод, что она проверяет, попадает ли точка в область выделенную красным цветом. То есть любая точка, принадлежащая серой области, и не принадлежащая красной области является ответом на поставленный вопрос. Например, x=2, y=2 или x=0.5, y=0.5 или x=-0.5, y=0.5 (таких точек куча выбирайте любую).
2) Поскольку на ЕГЭ самым ходовым языком программирования является Pascal (Delphi), то напишем на нем правильную программу, которая определяет принадлежность введенной точки заданной области. Для этого разобьем область на два множества точек относительно оси ординат (то есть x<= 0, x>=0)
var x, y: real;
begin
readln(x,y);
if (y>=x*x-2) and (y<=x) and (x>=0) or (x<=0) and (y<=-x) and (y>=x*x-2) then
write('принадлежит')
else
write('не принадлежит');
end.
Первое условие в if — e означает принадлежность сиреневой области, а второе — голубой, и мы берем их объединение.
Ну вот и все с задачей С1 мы разобрались. Легко, не правда ли?!
C2
Задача С2 — достаточно простая задача на обработку данных в массиве, что-то типа: посчитать среднее арифметическое четных элементов массива.
Рассмотрим конкретный пример:
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать значения от 0 до 1000. Опишите на русском языке или на одном из языков программирования алгоритм, который позволяет подсчитать и вывести среднее арифметическое элементов массива, имеющих нечетное значение. Гарантируется, что в исходном массиве хотя бы один элемент имеет нечетное значение.
Решение:
Const N=30;
Var a: array [1..N] of integer;
i, x, y: integer;
s: real;
begin
for i:=1 to N do
readln(a[i]);
x:=0; y:=0;
for i:=1 to N do
if (a[i] mod 2=1) then
begin
x:=x+a[i];
y:=y+1;
end;
s:=x/y;
writeln(s);
end.
В этой задаче, думаю даже комментарии излишне, так как она является очень простой. Хотя были модификации этой задачи посложнее, например: … подсчитать и вывести среднее арифметическое элементов массива, сумма цифр, которых является нечетным числом. Задача простая, но скажите на порядок сложнее.
С3
Пожалуй, это самая пресловутая задача. Она надоела всем: от школьников до учителей. Мой преподаватель, который проверяет ЕГЭ, больше всего жалуется именно на эту задачу: «Ну, какой идиот придумал эту задачу? Надоело…».
Если судить объективно, то эта задача ничего общего с информатикой вообще не имеет. Почему она сидит в С части на протяжении 7 лет? Непонятно!
Собственно, задача представляет собой игру, в которой играют двое игроков, делая ходы. Рассмотрим одну из этих злополучных задач и метод ее решения. Кстати, именно эта задача принципиально поменялась в 2012 году.
Условие задачи звучит так:
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то кучке или добавляет 4 камня в какую-то кучку. Игрок, после хода, которого общее число камней в двух кучках становится больше 25, проигрывает. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Для решения задачи необходимо построить дерево игры. Рассмотрим все возможные варианты ходов обоих игроков, которые заведомо не являются проигрышными (игроки не могут ходить во вред себе).
Из дерева игры видно, что как бы не походил первый игрок суммарное количество камней в обеих кучках будет больше 25, а потому он проигрывает. Итак, при правильной игре выигрывает второй игрок.
Ну, вот и все. С С3 мы тоже разобрались! Как она Вам? По мне — так очень скучная. Если пару раз прорешать задачи такого типа, то они не представляют никакой трудности!
C4
Сказать честно задача С4 мне не нравится. Одно ее условие на полстраницы чего стоит. К сожалению, эта задача проверяет не алгоритмические знания ученика, а больше технические.
Условие задачи звучит так:
На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат: <Фамилия> <Имя> <оценки>, где <Фамилия> – строка, состоящая не более чем из 20 символов, <Имя> – строка, состоящая не более чем из 15 символов, <оценки> – через пробел три целых числа, соответствующие оценкам по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним пробелом. Пример входной строки:
Иванов Петр 4 5 4
Требуется написать программу, которая будет выводить на экран фамилии и имена трех лучших по среднему баллу учеников. Если среди остальных есть ученики, набравшие тот же средний балл, что и один из трех лучших, то следует вывести и их фамилии и имена. Требуемые имена и фамилии можно выводить в произвольном порядке.
Поскольку самому решать эту задачу, ну, очень не охота, то приведу пример из кодификатора ЕГЭ (образец для проверки).
var p:array[1..100] of record
name: string;
sum: integer;
end;
c:char;
i,j,N,s1,s2,s3,m:integer;
begin
readln(N);
for i:=1 to N do
begin
p[i].name:='';
repeat
read(c);
p[i].name:=p[i].name+c
until c=' '; {считана фамилия}
repeat
read(c);
p[i].name:=p[i].name+c
until c=' '; {считано имя}
p[i].sum:=0;
for j:=1 to 3 do
begin
read(m);
p[i].sum:=p[i].sum+m
end; {подсчитана сумма баллов}
readln;
end;
s1:=0; s2:=0; s3:=0;
for i:=1 to N do
begin
if p[i].sum>s1 then
begin
s3:=s2; s2:=s1;
s1:=p[i].sum
end else
if p[i].sum>s2 then
begin
s3:=s2; s2:=p[i].sum
end else
if p[i].sum>s3 then s3:=p[i].sum;
end;
for i:=1 to N do
if p[i].sum>=s3 then writeln(p[i].name);
end.
Мне кажется, что задача С4 должна иметь несколько другой характер, а, именно: проверять помимо технических знаний еще и алгоритмические знания ученика такие как сортировки, структуры данных. Вообще хочется чтобы эта задача была легкой в реализации но сложной в разгадке решения. Сейчас же, как раз наоборот решить легко но написать сложно.
Задачи в 2012 году
С1
Кажется, составители ЕГЭ решили, что задача о попадании точки в некоторую область является слишком сложной(как по мне — это вовсе не так). Задача С1 была буквально упрощена. Теперь вместо системы координат рассматривается числовая прямая, а вместо области — объединение отрезков. Необходимо по введенному число определить принадлежность отрезкам.
Не понятно для чего надо было упрощать, эту и без того, простую задачу!?
C2
Эта задача осталась без изменения. Необходимо произвести обработку элементов массива.
C3
А вот эта задача изменилась коренным образом.
Условие звучит так:
У исполнителя Утроитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 29? Ответ обоснуйте.
Первое что пришло в голову после прочтение – это написание рекурсивной функции вычисляющей количество нужных программ. Но прочитав условие задачи еще раз я понял, что такой ответ не прокатит. Им нужен обоснованный ответ, а не программа. Понятно, что в этой задачи речь идет о динамическом программировании.
Приведу решение из кодификатора:
Обозначим R(n) – количество программ, которые преобразуют число 1 в число n. Обозначим t(n) наибольшее кратное трем, не превосходящее n. Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить 28.
Верны следующие соотношения:
1. Если n не делится на 3, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) – прибавлением единиц.
2. Пусть n делится на 3.
Тогда R(n) = R(n/3)+R(n-1)= R(n/3)+R(n-3) (если n>3).
При n=3 R(n) = 2 (два способа: прибавлением двух единиц или
однократным умножением на 3).
Поэтому достаточно постепенно вычислить значения R(n) для всех
чисел, кратных трем и не превосходящих 29: сначала вычисляем R(1), затем R(3), R(6) и т.д.
Имеем:
R(2)=1
R(3) = 2 = R(4)=R(5)
R(6) = R(2)+R(3) =1+2 = 3 = R(7)=R(8)
R(9) = R(3)+R(6) =2+3 =5 = R(10)=R(11)
R(12) = R(4)+R(9) = 2+5 = 7 = R(13)=R(14)
R(15) = R(5)+R(12) =2+7 =9 = R(16)=R(17)
R(18) = R(6)+R(15) = 3+9 = 12 = R(19)=R(20)
R(21) = R(7)+R(18) = 3+12 = 15 = R(22)=R(23)
R(24) = R(8)+R(21) = 3+ 15 = 18 = R(25)=R(26)
R(27) = R(9)+R(24) = 5 + 18 = 23 = R(28)=R(29)
Ответ: 23
По мне эта задача куда интереснее, чем игра. Она требует от ученика, хотя бы, представления о понятии динамического программирования.
Что Вы думаете?
C4
Задача С4 в этом году тоже немного улучшилась. Теперь не надо считывать эти фамилии и имена как в прошлой задаче С4. Собственно условие звучит так:
На ускорителе для большого числа частиц производится замеры скорости каждой из них. Чтобы в документации качественно отличать одну серию эксперимента от другой, каждую серию решили характеризовать числом, равным максимальному произведению из всех произведений пар скоростей различных частиц.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет обрабатывать результаты эксперимента, находя искомую величину. В нашей модели скорость частицы – это величина, которая может принимать как положительные, так и отрицательные значения. Следует учитывать, что частиц, скорость которых измерена, может быть очень много, но не может быть меньше двух.
На вход программе в первой строчке подается количество частиц N. В каждой из следующих N строк записано одно целое число со знаком, по абсолютной величине не превышающее 10000.
Пример входных данных:
5
123
1000
-12
10
1000
Программа должна вывести одно целое число, равное максимальному произведению из всех произведений пар скоростей различных частиц.
Пример выходных данных для приведенного выше примера входных данных:
1000000
В данной задаче поставлено достаточно много условий. Во-первых, требуется написать как можно эффективнее программу по времени и по памяти. Во-вторых, говорится, что данных может быть очень много. Это тонкий намек на то, что если мы решим записать входные данные в массив, то мы уже не получим эффективное решение. Наивный способ решения данной задачи: записать все в массив и двойным циклом пробежаться по элементам массива, найдя искомое число. Очевидно, такой алгоритм требует O(n*n) времени и O(n) памяти. Это плохо.… За такое решение можно получить максимум 2 балла из 4.
Немного поразмыслив можно понять, что, так как исходное число состоит из произведения 2 чисел со знаком, то оно будет максимально, если это два самых больших или два самых маленьких из входных чисел. То есть необходимо найти два самых больших и два самых маленьких числа, затем сравнить их произведение и выдать ответ. Причем все это можно сделать за один проход даже не сохраняя данных в массив.
Думаю, эта задача куда симпатичнее задач С4 предыдущих годов.
Заключение
Ну, вот мы и познакомились с задачками ЕГЭ части C по информатике. Радует, что все задачи являются доступными для школьника, который готовился к экзамену. Также радует, что писать программу можно на любом языке программирования (встречались Python, PHP, Basic лишь бы проверяющий знал этот язык).
Какие задачи Вам понравились больше старые или новые?
Автор: timyrik20
