Лекция №5. Выполнение типовых заданий части 3.

Лекция №5. Выполнение типовых заданий части 3.

Для записи ответов к заданиям этой части (С1–С4) используется бланк ответов № 2. Запишисывается сначала номер задания (С1 и т.д.), а затем полное решение. Ответы записываются четко и разборчиво.

Перед тем, как приступить к решению задания С1 из ЕГЭ по информатике, отметим, что необходимым условием успешного его решения является умение составлять программы как минимум на одном языке программирования (Паскаль, Бейсик, Си). Рассмотрим первое задание из группы повышенной сложности.

Задача С1: Требовалось написать программу, которая вводит с клавиатуры координаты точки на плоскости (x,y – действительные числа) и определяет принадлежность точки заштрихованной области, включая ее границы. Программист торопился и написал программу неправильно.

Последовательно выполните следующее:
1) Приведите пример таких чисел x, y, при которых программа неверно решает поставленную задачу.
2) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы).
 

Решение: Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла)
Элементы ответа:
1) Пример: x= –1, y= –3 (Любая пара (x,y), для которой выполняется: x2+y2<4 или x< –2 или (y<0 и y<= –x))
2) Возможная доработка (Паскаль):
if (x*x+y*y>=4) and (x>= –2) and (y<= –x) and (y>=0) then
write('принадлежит')
else
write('не принадлежит')
(могут быть и другие способы доработки).

Для решения задания С2 вам вновь придется вспомнить навыки программирования. Отметим, что достаточно привести фрагмент ответа на одном из языков.

Задача С2: Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 100 – баллы учащихся выпускного класса за итоговый тест по информатике. Для получения положительной оценки за тест требовалось набрать не менее 20 баллов. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит минимальный балл среди учащихся, получивших за тест положительную оценку. Известно, что в классе хотя бы один учащийся получил за тест положительную оценку.

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
 

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

Решение: 

Задание С3. Рассмотрим очередную задачу группы С из ЕГЭ по информатике 2010 года. Ее особенностью является то, что решается она методом перебора.

Задача С3: Два игрока играют в следующую игру. На координатной плоскости стоит фишка. В начале игры фишка находится в точке с координатами (–2,–1). Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3,y), (x,y+4), (x+2,y+2). Игра заканчивается, как только расстояние от фишки до начала координат превысит число 9. Выигрывает игрок, который сделал последний ход. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Решение: Содержание верного ответа и указания к оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) Выигрывает первый игрок, своим первым ходом он должен поставить фишку в точке с координатами (1,-1). Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке координаты фишки на каждом этапе игры.

 Таблица содержит все возможные варианты ходов второго игрока. Из неё видно, что при любом ответе второго игрока у первого имеется ход, приводящий к победе.

Для успешного выполнения задания С4 от учеников вновь потребуется проявить навыки программирования. Рекомендуем подтянуть знания в данном разделе информатики.

Задача С4: На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95 и 98. В городе N был проведен мониторинг цены бензина на различных АЗС.

Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять для каждого вида бензина, сколько АЗС продают его дешевле всего. На вход программе в первой строке подается число данных о стоимости бензина. В каждой из последующих N строк находится информация в следующем формате:

<Компания> <Улица> <Марка> <Цена>

где <Компания> – строка, состоящая не более, чем из 20 символов без пробелов, <Улица> – строка, состоящая не более, чем из 20 символов без пробелов, <Марка> – одно из чисел – 92, 95 или 98, <Цена> – целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. <Компания> и <Улица>, <Улица> и <Марка>, а также <Марка> и <цена> разделены ровно одним пробелом. Пример входной строки:

Синойл Цветочная 95 2250

Программа должна выводить через пробел 3 числа – количество АЗС, продающих дешевле всего 92-й, 95-й и 98-й бензин соответственно. Если бензин какой-то марки нигде не продавался, то следует вывести 0.

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

12 1 0

Решение: Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) Программа читает все входные данные один раз, не запоминая их в массиве, размер которого соответствует числу АЗС или диапазону цен. Во время чтения данных определяются минимальная цена каждой марки бензина и количество АЗС, продающих его по этой цене. Для этого используются 6 переменных или соответствующие массивы (например, для удобства из 8 элементов каждый, см. программу на языке Бейсик).

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

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

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

var

min, ans: array[92..98] of integer;

c: char;

i, k, N, b: integer;

begin

for i:=92 to 98 do

begin

min[i]:=3001;{допустимо и другое число, >3000}

ans[i]:=0;

end;

readln(N);

for i:=1 to N do

begin

repeat

read(c);

until c=' '; {считана компания}

repeat

read(c);

until c=' '; {считана улица}

readln(k,b);

if min[k] > b then

begin

min[k]:=b;

ans[k]:=1

end else

if min[k] = b then ans[k]:=ans[k]+1;

end;

{если бензина какой-то марки не было,

ans[i] осталось равным 0}

writeln(ans[92],' ', ans[95],' ', ans[98])

end.

Пример правильной и эффективной программы на языке Бейсик:

DIM min(8) AS INTEGER, ans(8) AS INTEGER

DIM s AS STRING

FOR i = 2 TO 8

min(i) = 3001

ans(i) = 0

NEXT i

INPUT n

FOR j = 1 TO n

LINE INPUT s

c$ = MID$(s, 1, 1)

i = 1

WHILE NOT (c$ = " ")

i = i + 1

c$ = MID$(s, i, 1)

WEND

i = i + 1

c$ = MID$(s, i, 1)

WHILE NOT (c$ = " ")

i = i + 1

c$ = MID$(s, i, 1)

WEND

i = i + 2

REM Выделим из марки бензина только последнюю цифру

30

k = ASC(MID$(s, i, 1)) - ASC("0")

i = i + 2

b = VAL(MID$(s, i))

IF min(k) > b THEN

min(k) = b

ans(k) = 1

ELSE IF min(k) = b THEN ans(k) = ans(k) + 1

END IF

NEXT j

PRINT ans(2),ans(5),ans(8)

END