РЕШУ ЕГЭ — информатика

Задания

В еженедельном выпуске популярной газеты было объявлено голосование по выбору актёра, который, по мнению читателей, должен сняться в продолжении фильма «Белое солнце пустыни». На выбор был предложен список из шести актеров. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет обрабатывать результаты sms-голосования по данному вопросу. Результаты голосования получены в виде списка актёров (каждый элемент списка соответствует одному sms-сообщению). Следует учитывать, что количество голосов в списке может быть очень велико. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших sms-сообщений N. В каждой из последующих N строк записаны фамилия и имя актера (сначала фамилия, а потом через пробел имя). Длина строки не превосходит 50 символов. Пример входных данных:

Меньшиков Олег

Миронов Евгений

Меньшиков Олег

Машков Владимир

Меньшиков Олег

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

Меньшиков Олег 3

Миронов Евгений 1

Машков Владимир 1

Решение. Программа читает все входные данные один раз, не запоминая их в массиве, размер которого равен N, а составляя только список встретившихся актёров и количества голосов, отданных за каждого из них. Во время чтения данных об очередном актёре просматривается список ранее сохранённых актеров. Если он уже есть в списке, то количество голосов, отданных за него, увеличивается на 1, иначе актёр добавляется в массив упомянутых в голосовании актёров (при корректных данных размер массива не может быть больше 6). После окончания ввода производится сортировка массивов актёров и количества голосов, отданных за них, в порядке убывания количества голосов; затем выводится список актёров с указанием частоты встречаемости. Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведены примеры решения задания на языках Паскаль и Бейсик. Допускаются решения, записанные на других языках программирования. При оценивании решений на других языках программирования необходимо учитывать особенности этих языков программирования. Так, на языке C++ при считывании строковой переменной будут считаны не фамилия и имя, а только фамилия, поэтому следует использовать функцию getline(cin,s); аналогичная проблема возникает и в языке Си.

Пример правильной и эффективной программы на языке Паскаль:	Пример правильной и эффективной программы на языке Бейсик:
Var n, Num, i, j, t: integer; Count: array[1..6] of integer; s: string; Names: array[1..6] of string; Begin Num:=0; {Число различных актеров в списке голосов} ReadLn(N); {Считываем количество голосов} for i:=1 to N do begin ReadLn(S); {считали очередного актера} {Осуществляем его поиск в списке уже встретившихся} j:=1; while (j<=Num) and (s<>Names[j]) do j:=j+1; {Если он найден} if j<=Num then {Увеличиваем счетчик числа голосов, отданных за этого актера} Count[j]:=Count[j]+1 else begin {Иначе добавляем актера в конец списка} Names[j]:=s; Count[j]:=1; Num:=Num+1; end end; {Сортируем массивы Names и Count в порядке убывания значений массива Count} for i:=Num downto 2 do for j:=2 to i do if Count[j-1] < Count[j] then begin t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t; s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s; end; for i:=1 to Num do WriteLn(Names[i], ' ', Count[i]); end.	DIM N, Num, i, j, t AS INTEGER DIM Count(6) AS INTEGER DIM Names$(6) Num = 0 'Число различных актеров в списке голосов INPUT N 'Считываем количество голосов FOR i = 1 TO N LINE INPUT s$ 'считали актера 'Осуществляем поиск названия в списке уже встретившихся j = 1 WHILE (j <= Num) AND (s$ <> Names$(j)) j = j + 1 WEND 'Если актер найден IF j <= Num THEN 'Увеличиваем счетчик числа голосов, отданных за 'этого актера Count(j) = Count(j) + 1 ELSE ' Иначе добавляем актера в конец списка Names$(j) = s$ Count(j) = 1 Num = Num + 1 END IF NEXT i 'Сортируем массивы Names и Count в порядке убывания значений 'массива Count FOR i = Num TO 2 STEP -1 FOR j = 2 TO i IF Count(j - 1) < Count(j) THEN t = Count(j): Count(j) = Count(j - 1): Count(j - 1) = t s$ = Names$(j): Names$(j) = Names$(j - 1): Names$(j - 1) = s$ END IF NEXT j NEXT i FOR i = 1 TO Num PRINT Names$(i), Count(i) NEXT i END

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

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

Var n, Num, i, j, t: integer;

Count: array[1..6] of integer;

s: string;

Names: array[1..6] of string;

Begin

Num:=0; {Число различных актеров в списке голосов}

ReadLn(N); {Считываем количество голосов}

for i:=1 to N do

begin

ReadLn(S); {считали очередного актера}

{Осуществляем его поиск в списке уже встретившихся}

j:=1;

while (j<=Num) and (s<>Names[j]) do j:=j+1;

{Если он найден}

if j<=Num then {Увеличиваем счетчик числа голосов, отданных за этого актера}

Count[j]:=Count[j]+1

else begin {Иначе добавляем актера в конец списка}

Names[j]:=s;

Count[j]:=1;

Num:=Num+1;

end

end;

{Сортируем массивы Names и Count в порядке убывания значений массива Count}

for i:=Num downto 2 do

for j:=2 to i do if Count[j-1] < Count[j] then

begin

t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t;

s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s;

end;

for i:=1 to Num do

WriteLn(Names[i], ' ', Count[i]);

end.

DIM N, Num, i, j, t AS INTEGER

DIM Count(6) AS INTEGER

DIM Names$(6)

Num = 0 'Число различных актеров в списке голосов

INPUT N 'Считываем количество голосов

FOR i = 1 TO N

LINE INPUT s$ 'считали актера

'Осуществляем поиск названия в списке уже встретившихся

j = 1

WHILE (j <= Num) AND (s$ <> Names$(j))

j = j + 1

WEND

'Если актер найден

IF j <= Num THEN 'Увеличиваем счетчик числа голосов, отданных за

'этого актера

Count(j) = Count(j) + 1

ELSE ' Иначе добавляем актера в конец списка

Names$(j) = s$

Count(j) = 1

Num = Num + 1

END IF

NEXT i

'Сортируем массивы Names и Count в порядке убывания значений

'массива Count

FOR i = Num TO 2 STEP -1

FOR j = 2 TO i

IF Count(j - 1) < Count(j) THEN

t = Count(j): Count(j) = Count(j - 1): Count(j - 1) = t

s$ = Names$(j): Names$(j) = Names$(j - 1): Names$(j - 1) = s$

END IF

NEXT j

NEXT i

FOR i = 1 TO Num

PRINT Names$(i), Count(i)

NEXT i

END

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Программа работает для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве, размер которого соответствует числу N (количеству запросов), а подсчитывая в массиве размером 12, сколько раз встретилась та или иная задача. Допускается наличие в тексте программы трёх синтаксических ошибок: пропущен или неверно указан знак пунктуации; неверно написано или пропущено зарезервированное слово языка программирования; не описана или неверно описана переменная; применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку)	4
Программа работает верно, но входные данные сохраняются в массиве, размер которого соответствует числу N. Этот массив, возможно, потом сортируется. Или для увеличения числа встречаемости очередной пары используется цикл от 1 до 16, или оператор case, или 16 операторов if. Допускается наличие до пяти синтаксических ошибок, описанных выше. Возможно, в принципиально верно организованном вводе данных есть одна ошибка. 3 балла также выставляется, если в эффективной программе, удовлетворяющей критериям выставления 4 баллов, есть одна ошибка, в результате которой программа работает неверно на некоторых наборах нетипичных входных данных (например, все подали голоса за одну и ту же пару). Также 3 балла выставляется, если программа выводит на экран все пары с верным количеством поданных за них голосов, но среди них есть и те, за кого не было подано ни одного голоса	3
Программа работает в целом верно, эффективно или нет, но в реализации алгоритма содержится до двух ошибок (неверная инициализация счетчиков, хотя в предложенных выше решениях обнулять их не требуется; возможно, программа работает неверно, если в списке упомянуто меньше 6 актёров, выход за границу массива, допущена ошибка в принципиально верно организованной сортировке, используется знак “<” вместо “<=”, “or” вместо “and” и т.п.). Возможно, некорректно организовано считывание входных данных. Допускается наличие до семи синтаксических ошибок, описанных выше	2
Программа, возможно, работает неверно при некоторых входных данных, но по приведённому тексту решения ясно, что экзаменуемый понимает, из каких этапов должно состоять решение задачи. При использовании сортировки она может быть реализована принципиально неверно (например, вместо двух циклов используется один). Всего допускается до четырёх различных ошибок в реализации алгоритма, в том числе описанных в критериях присвоения 2 баллов. Допускается наличие любого количества синтаксических ошибок, описанных выше	1
Задание не выполнено или выполнено неверно	0
Максимальный балл	4

Ключ