В телевизионном танцевальном марафоне с определением победителя с
Условие
В телевизионном танцевальном марафоне с определением победителя с помощью телезрителей после каждого тура объявляется 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 -
Осталось ещё 3 шага
< Count(j) THEN t = Count(j): Count(j) =…
= t t = Names(j): Names(j) = Names(j - 1)…
= t END IF NEXT j NEXT i FOR i = 1 TO 16 IF…
Бесплатно · займёт минуту