СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 27 № 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.

 

 

Приведём решение Сергея Мартынова, Python 3.

a=[0 for x in range(0,16)]

n=int(input())

for i in range(0,n):

k=int(input())-1

a[k]+=1

for c in range(0,16):

m = max(a)

mi = a.index(m)

if m > 0:

print(mi+1, m)

a[mi] = -1

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

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.


Аналоги к заданию № 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.