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




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

В командных олимпиадах по программированию для решения предлагается не больше 12 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наименее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием сети Интернет. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания. Пример входных данных:

 

6

А+B

Крестики-Нолики

А+В

Простой делитель

А+В

Простой делитель

 

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

 

Крестики-Нолики 1

Простой делитель 2

А+В 3

Решение.

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

 

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

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

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

s: string;

Names: array[1..12] 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;

if Num >= 3 then Num := 3;

for i:=1 to Num do

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

end.

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

DIM Count(12) AS INTEGER

DIM Names$(12)

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

IF Num >= 3 THEN Num = 3

FOR i = 1 TO Num

PRINT Names$(i), Count(i)

NEXT i

END

 

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