Добро пожаловать! Если вы хотите успешно сдать ЕГЭ – то вы попали куда надо. Для полноценной подготовки к экзамену egedb.ru предлагает вам: прохождение тестов ЕГЭ по многим предметам с последующим анализом результатов, прорешивание задач определенного типа или на определенные темы, познакомится с процедурой проведения ЕГЭ и многое другое!
Хотите узнать больше о бланках, предоставляемых на экзамене и потренироваться в их заполнении? Всё просто! Наш сайт предлагает потренироваться на электронных копиях блаков – такие тренировки безусловно принесут свои плоды и помогут не допустить ошибок при заполнении.
Вам нужна статистика вашей подготовки на сайте? Войдите в личный кабинет при помощи своей учетной записи в социальной сети «В Контакте» и получите такую возможность. Или может быть вы хотите помочь развитию сайта? При повышенной активности на сайте вы можете быть повышены до уровня модератора и добавлять свои задания на сайт!


Главная

Тесты

Русский язык
Математика
Информатика
Физика
Биология
География
Обществознание
История

Задачи

Русский язык
Математика
Информатика
Физика
Биология
География
Обществознание
История

Как решить

Полезности

Статьи

Новости

Гостевая

Ссылки

Поиск

Вход

Задание C4 по предмету Информатика (№43)

Информатика 2012 год

Обработка символьных строк

C4

В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая
будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.
Пример входных данных:
6
А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель
Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.
Пример выходных данных для приведённого выше примера входных данных:
А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1
За правильный ответ 4 балл(ов)
Правильный ответ:
Программа читает все входные данные один раз, не запоминая их в массиве, размер которого равен N, а составляя только список встретившихся задач и количества запросов по каждой из них. Во время чтения данных об очередной задаче просматривается список ранее сохраненных задач; если она уже есть в списке, то количество запросов по ней увеличивается на 1, иначе задача добавляется в массив упомянутых в запросах задач (при корректных данных он не может быть больше 11). После окончания ввода производится сортировка массивов задач и количества запросов, отданных за них, в порядке убывания количества запросов, затем выводится список из трёх первых задач с указанием частоты встречаемости (или весь список, если его длина меньше трёх). Вместо сортировки можно применить и алгоритм поиска трёх максимальных элементов в массиве. Затем выводятся задачи, частота встречаемости которых не ниже, чем у третьей задачи. Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведены примеры решения задания на
Алгоритмическом языке, а также на языках Паскаль и Бейсик. Допускаются решения, записанные на других языках программирования. При оценивании решений на других языках программирования необходимо учитывать
особенности этих языков программирования. Так, на языке C++ при считывании строковой переменной будет считано не все название задачи, а только его первое слово, поэтому следует использовать функцию getline(cin,s), аналогичная проблема возникает и в языке Си.
Паскаль:
Var N, Num, i, j, t: integer; Count: array[1..11] of integer; s: string; Names: array[1..11] of string; Begin Num:=0; {Число различных задач в списке запросов} ReadLn(N); {Считываем количество запросов} for i:=1 to N do begin ReadLn(s); {считали очередную задачу} {Осуществляем ее поиск в списке уже встретившихся} j:=1; while (j<=Num) and (s<&rt;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 &rt;= 3 then j := 3 else j := Num; i := 1; while (i <= Num) and (Count[i] &rt;= Count[j]) do begin WriteLn(Names[i], ' ', Count[i]); i := i + 1; end end.

Бейсик:
DIM N, Num, i, j, t AS INTEGER DIM Count(11) AS INTEGER DIM s AS STRING DIM Names(11) AS STRING REM Число различных задач в списке запросов Num = 0 REM Считываем количество запросов INPUT N FOR i = 1 TO N REM Считываем очередную задачу INPUT s REM Осуществляем ее поиск в списке уже встретившихся j = 1 WHILE j <= Num AND s <&rt; Names(j) j = j + 1 WEND IF j <= Num THEN REM Если она найдена, увеличиваем счетчик числа запросов Count(j) = Count(j)+1 ELSE REM Иначе добавляем задачу в конец списка Names(j) = s: Count(j) = 1 Num = Num + 1 ENDIF NEXT i REM Сортируем массивы Names и Count REM в порядке убывания значений массива 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 REM определение порога для количества появлений REM задач из списка вывода; порог равен Count(j) IF Num &rt;= 3 THEN j = 3 ELSE j = Num END IF i = 1 REM Вывод наиболее популярных задач WHILE i <= Num AND Count(i) >= Count(j) PRINT Names(i), Count(i) i = i + 1 WEND

Алгоритмический язык:
литтаб Names[1:11] | названия задач целтаб Count[1:11] | счетчики числа запросов по каждой задаче цел i, j, t лит s | 1. Чтение списка запросов | 1.1. Инициализация количества запросов и счетчика задач Num:=0 |Число различных задач в списке запросов ввод N |Считываем количество запросов | 1.2. Цикл чтения нц для i от 1 до N ввод s |Считали очередную задачу |Осуществляем ее поиск в списке уже встретившихся j:=1 нц пока(j<=Num) и (s<&rt;Names[j]) j:=j+1 кц | Обрабатываем очередную задачу если j<=Num | Если задача найдена в списке то | Увеличиваем счетчик числа запросов Count[j]:=Count[j]+1 иначе | Добавляем задачу в конец списка Names[j]:=s Count[j]:=1 Num:=Num+1 все кц | 2. Совместно сортируем массивы Names и Count | в порядке убывания значений массива Count нц для i от Num до 2 шаг -1 нц для j от 2 до i если Count[j-1]<Count[j] то t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s все кц кц | 3. Вывод задач-"призеров" | 3.1. Определение порога для количества запросов по задаче | Порог равен Count[j] если Num &rt;= 3 то j := 3 иначе j := Num все | 3.2. Цикл вывода i := 1; нц пока (i <= Num) и (Count[i] &rt;= Count[j]) вывод нс, Names[i], ' ', Count[i] i := i+ 1 кц кон
Показать ответ

Ещё задания

Комментарии

Назад