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


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

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

 

4

2

10

3

2

 

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

 

3 1

10 1

2 2

Решение.

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

 

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

Var n, i, j, t: integer;

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

Begin

For i := 1 to 10 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:=10 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 10 do

if Count[i] > 0 then

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

end.

DIM Count(10) AS INTEGER

DIM Names(10) AS INTEGER

FOR i = 1 TO 10

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 = 10 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 10

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

NEXT i

END

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 802.