Главная > Инструкция


31

24

27

30

18

15

18

28

28

23

12

Указания по оцениванию

Два балла ставятся в одном из двух случаев:

1. Правильное указание количества возможных программ,
основанное на верных рассуждениях, но доказательство


Баллы

© 2012 Федеральная служба по надзору в сфере образования и науки Российской Федерации

© 2012 Федеральная служба по надзору в сфере образования и науки Российской Федерации

C4

(2012-31/36)

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.

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

Представленное решение обладает одним из свойств 1. Указано, что нужно рассматривать значения n, меньшие, чем 29, и приведены правильные рекуррентные соотношения (см. выше), возможно, неполные. 2. Правильно выписаны и обоснованы значения R(n) для небольших n. 3. Правильно написан ответ, но нет его обоснования.

1

Не выполнено ни одно из перечисленных выше условий

0

Максимальный балл

3

В командных олимпиадах по программированию для решения предлагается

не больше 11 задач. Команда может решать предложенные задачи в любом

порядке. Подготовленные решения команда посылает в единую

проверяющую систему соревнований. Вам предлагается написать

эффективную, в том числе по используемой памяти, программу, которая

будет статистически обрабатывать пришедшие запросы, чтобы определить

наиболее популярные задачи. Следует учитывать, что количество запросов в

списке может быть очень велико, так как многие соревнования проходят с

использованием Интернет.

Перед текстом программы кратко опишите используемый вами алгоритм

решения задачи.

На вход программе в первой строке подаётся количество пришедших

запросов N. В каждой из последующих N строк записано название задачи

в виде текстовой строки. Длина строки не превосходит 100 символов,

название может содержать буквы, цифры, пробелы и знаки препинания.

Пример входных данных:

6

А+B

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

Прямоугольник

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

А+В

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

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс. (2012 - 32 / 36)

Программа должна вывести список из трёх наиболее популярных задач

с указанием количества запросов по ним. Если в запросах упоминаются

менее трех задач, то выведите информацию об имеющихся задачах. Если

несколько задач имеют ту же частоту встречаемости, что и третья по частоте

встречаемости задача, их тоже нужно вывести.

Пример выходных данных для приведённого выше примера входных данных:

А+В 2

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

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

Прямоугольник 1

Содержание верного ответа и указания по оцениванию

(допускаются иные формулировки ответа, не искажающие его смысла)

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

© 2012 Федеральная служба по надзору в сфере образования и науки Российской Федерации

© 2012 Федеральная служба по надзору в сфере образования и науки Российской Федерации

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс. (2012 - 33 / 36)

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс. (2012 - 34 / 36)

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

j:=1

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

нц пока (j<= Num) и (s<> Names [j])

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

j:=j+1

s: string;

кц

Names: array[1..11] of string;

I Обрабатываем очередную задачу

Begin

если j <=Num | Если задача найдена в списке

Num:=0; {Число различных задач в списке запросов}

то | Увеличиваем счетчик числа запросов

ReadLn(N); {Считываем количество запросов}

Count[j]:=Count[j]+1

for i:=1 to N do

иначе | Добавляем задачу в конец списка

begin

Names[j]:=s;

ReadLn(S); {считали очередную задачу}

Count[j]:=1;

{Осуществляем ее поиск в списке уже встретившихся}

Num:=Num+1

j:=1;

все

while (j<=Num) and (s<>Names[j]) do j:=j+1;

кц

{Если она найдена}

I 2. Совместно сортируем массивы Names и Count

if j<=Num then {Увеличиваем счетчик числа запросов}

| в порядке убывания значений массива Count

Count[j]:=Count[j]+1

нц для i от Num до 2 шаг -1

else begin {Иначе добавляем задачу в конец списка}

нц для j от 2 до i

Names[j]:=s;

если Count[j-1]

Count[j]:=1;

t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t;

Num:=Num+1

s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s;

end

все

end;

кц

{Сортируем массивы Names и Count в порядке убывания значений

кц

массива Count}

| 3. Вывод задач-";призеров";

for i:=Num downto 2 do

1 3.1. Определение порога для количества запросов по задаче

for j:=2 to i do if Count[j-1]

| Порог равен Count[j]

begin

если Num >= 3

t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t;

s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s;

иначе j := Num; все

end; if Num >= 3 then j := 3 else j := Num;

I 3.2. Цикл вывода i : = 1;

i : = 1; while (i <= Num) and (Count[i] >= Count[j]) do

нц пока (i <= Num) и (Count[i] >= Count[j])

begin

вывод нс, Names[i], ' ', Count[i], нс

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

i := i + 1;

кц

end

кон

end.

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

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

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

литтаб Names[1:11] | названия задач

DIM Count(11) AS INTEGER

целтаб Count[1:11] | счетчики числа запросов по каждой задаче

DIM s AS STRING

цел i, j, t

DIM Names(11) AS STRING

лит s

REM Число различных задач в списке запросов

| 1. Чтение списка запросов

Num = 0

| 1.1. Инициализация количества запросов и счетчика задач

REM Считываем количество запросов

Num:=0 |Число различных задач в списке запросов

INPUT (n)

ввод N |Считываем количество запросов

FOR i = 1 TO n

| 1.2. Цикл чтения

REM Считываем очередную задачу

нц для i от 1 до N

INPUT (s)

ввод s |Считали очередную задачу

REM Осуществляем ее поиск в списке уже встретившихся

|Осуществляем ее поиск в списке уже встретившихся

j = 1

© 2012 Федеральная служба по надзору в сфере образования и науки Российской Федерации

© 2012 Федеральная служба по надзору в сфере образования и науки Российской Федерации

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.

(2012-35/36)

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.

(2012-36/36)

Баллы

WHILE j <= Num AND s <> 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 >= 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

Указания по оцениванию

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

© 2012 Федеральная служба по надзору в сфере образования и науки Российской Федерации

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

Программа работает верно, но входные данные запоминаются в массиве, размер которого соответствует числу N. Этот массив, возможно, потом сортируется. Допускается наличие от одной до трех синтаксических ошибок. Возможно, в принципиально верно организованном вводе данных есть одна ошибка (например, использование read вместо readln в Паскале или неверное считывание строки в C++). Три балла также выставляется, если в эффективной программе, удовлетворяющей критериям выстав­ления 4 баллов, есть одна ошибка, в результате которой программа работает неверно на некоторых наборах нетипичных входных данных (например, все запросы относятся к одной и той же задаче)

3

Программа работает в целом верно, эффективно или нет, но в реализации алгоритма содержится до двух ошибок (неверная инициализация счётчиков — хотя в предложенных выше решениях обнулять их не требуется; возможно, программа неверно работает, если в списке упомянуто меньше 11 задач, выход за границу массива, допущена ошибка в принципиально верно организованной сортировке или алгоритме поиска минимальных элементов, используется знак ";<"; вместо ";<=";, ";or"; вместо ";and"; и т. п.). Возможно, некорректно организовано считывание входных данных. Допускается наличие от одной до пяти синтаксических ошибок, описанных выше.

2

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

1

Задание не выполнено или выполнено неверно.

0

Максимальный балл

4

© 2012 Федеральная служба по надзору в сфере образования и науки Российской Федерации



Скачать документ

Похожие документы:

  1. Егэ 2012 по информатике демонстрационный вариант кодификатор и спецификация спецификация контрольных измерительных материалов единого государственного экзамена 2012 года по информатике и икт 1 назначение ким егэ

    Документ
    ... ЕГЭ 2012поинформатике: демонстрационныйвариант, кодификатор и спецификация СПЕЦИФИКАЦИЯ контрольныхизмерительныхматериаловединогогосударственногоэкзамена2012годапоинформатике и ИКТ 1. Назначение КИМ ЕГЭ Контрольныеизмерительныематериалы ...
  2. Контрольные измерительные материалы единого государственного экзамена (егэ) 2012 года

    Документ
    ... контрольныхизмерительныхматериалов для проведения в 2012годуединогогосударственногоэкзаменапо 14 общеобразовательным предметам; - демонстрационныевариантыконтрольныхизмерительныхматериаловединогогосударственногоэкзамена2012годапо ...
  3. Методическое письмо о преподавании учебного предмета «информатика и икт» в 2012-2013 учебном году в общеобразовательных учреждениях

    Инструктивно-методическое письмо
    ... и ИКТ; спецификация контрольныхизмерительныхматериаловединогогосударственногоэкзамена2012годапоИнформатике и ИКТ; демонстрационныйвариантконтрольныхизмерительныхматериаловединогогосударственногоэкзамена2012годапоИнформатике и ИКТ ...
  4. Методическое письмо о преподавании учебного предмета «информатика и икт» в 2012-2013 учебном году в общеобразовательных учреждениях

    Инструктивно-методическое письмо
    ... и ИКТ; спецификация контрольныхизмерительныхматериаловединогогосударственногоэкзамена2012годапоИнформатике и ИКТ; демонстрационныйвариантконтрольныхизмерительныхматериаловединогогосударственногоэкзамена2012годапоИнформатике и ИКТ ...
  5. Егэ – изменения в контрольно-измерительных материалах

    Документ
    ... контрольныхизмерительныхматериалов для проведения в 2012годуединогогосударственногоэкзаменапо 14 общеобразовательным предметам; - демонстрационныевариантыконтрольныхизмерительныхматериаловединогогосударственногоэкзамена2012годапо ...

Другие похожие документы..