Задания
Версия для печати и копирования в MS Word
Задания Д27 C4 № 6436

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

 

Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

 

Задание А. Имеется набор данных, состоящий из 15 чисел.

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

Максимальная оценка за правильную программу – 2 балла.

 

Задание Б. Имеется набор данных, состоящий из целых чисел. Набор может быть очень большим.

Напишите программу для решения этой задачи.

Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).

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

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

Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

 

Следует учитывать, что количество голосов в списке может быть очень велико. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших sms-сообщений N. В каждой из последующих N строк записан номер пары от 1 до 16.Пример входных данных:

 

4

2

16

3

2

 

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

 

2 2

3 1

16 1

Спрятать решение

Решение.

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

 

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

Var n, i, j, t: integer;

Count, Names: array[1..16] of integer;

Begin

For i := 1 to 16 do

begin

Count[i] := 0;

Names[i] := i;

end;

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

for i:=1 to N do

begin

ReadLn(t); {считали очередную пару}

Count[t] := Count[t] + 1;{подсчитываем её}

end;

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

for i:=16 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;

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

end;

for i:=1 to 16 do

if Count[i] > 0 then

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

end.

DIM N, i, j, t AS INTEGER

DIM Count(16) AS INTEGER

DIM Names(16) AS INTEGER

FOR i = 1 TO 16

Count(i) = 0

Names(i) = i

NEXT i

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

FOR i = 1 TO N

INPUT t 'считали пару

'Подсчитываем её

Count(t) = Count(t) + 1

NEXT i

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

'значений массива Count

FOR i = 16 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

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

END IF

NEXT j

NEXT i

FOR i = 1 TO 16

IF Count(i) > 0 THEN PRINT Names(i), Count(i)

NEXT i

END

 

 

Приведём решение Даниила Доценко, Pascal ABC.

 

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

k,i,n,j:integer;

begin

  readln(n);

  for i:=1 to n do begin

    readln(k);

    a[k]:=a[k]+1;

  end;

  k:=0;

  for i:=1 to 16 do

    if a[i]>k then k:=a[i];

    for j:=k downto 1 do

      for i:=1 to 16 do

        if j=a[i] then writeln(i,' ',a[i]);

end.

 

Пример решения задачи А на языке Паскаль.

var

a: array[1..16] of integer; {исходные данные}

val: integer; {пара}

lenght: integer; {количество голосов за пару}

i, j, k: integer;

begin

for i := 1 to 15 do read(a[i]);

for i:=1 to 15-1 do

for j:=1 to 15-i do

if a[j] < a[j+1] then begin

k := a[j];

a[j] := a[j+1];

a[j+1] := k;

end;

lenght := 1;

for i := 1 to 15 do

if a[i]=a[i+1] then

lenght := lenght + 1

else begin

writeln(a[i], ' ', lenght);

lenght := 1;

end;

end.

Спрятать критерии
Критерии проверки:

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

Аналоги к заданию № 6436: 6856 Все

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Вариант 602.
Спрятать решение · ·
Денис Шегай 12.02.2019 23:24

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

 

var

a, b: array [1..16] of integer;

x, n, i, max, max2: integer;

 

begin

read(n);

for i := 1 to n do

begin

read(x);

a[x] += 1;

if a[x] > max then

max := a[x];

end;

while max > 0 do

begin

for i := 1 to 16 do

begin

if a[i] = max then

writeln(i, ' ', a[i]);

if (a[i] > max2) and (a[i] < max) then

max2 := a[i];

end;

max := max2;

max2 := 0;

end;

end.