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




Школа экспертов
Вернуться на основную страницу «Школы экспертов»

Ниже представлены ученические решения экзаменационных заданий. Оцените каждое из них в соответствии с критериями проверки заданий ЕГЭ. После нажатия кнопки «Проверить» вы узнаете правильный балл за каждое из решений. В конце будут подведены итоги.

Задание 3793
Задание 12443


Задание № 3793

На вход программе (как вариант, из входного файла text.dat) подаётся текст на английском языке. Ввод этих символов заканчивается точкой (другие символы, отличные от «.» во входных данных отсутствуют; в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка). Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять и выводить на экран, какая английская буква встречается во входной последовательности чаще всего и сколько именно раз. Строчные и прописные буквы при этом не различаются. Если таких букв несколько, то программа должна выводить на экран ту из них, которая стоит по алфавиту раньше.

Например, пусть файл содержит следующую информацию:

It is not a simple task. Yes!

Тогда чаще всего встречаются буквы I, S, T. (слово Yes в подсчете не участвует, так как расположено после точки). Следовательно, в данном случае, программа должна вывести

I 3.


Пояснение

Программа читает текст до точки один раз, подсчитывая в массиве, хранящем 26 целых чисел, количество вхождений каждой из букв. Сам текст при этом не запоминается. Затем в этом массиве шлется первое вхождение максимального элемента. Баллы начисляются только за программу, которая решает задачу хотя бы для частного случая (например, для строк, состоящих не более чем из 255 символов).

 

БейсикПаскаль

DIM i, imах, с, a(26) AS INTEGER

OPEN "TEXT.DAT" FOR INPUT AS #1

S$ = INPUT$(1,#1)

DO WHILE NOT (S$ = ".")

c = ASC(S$)

IF(c>=ASC("A")AND c<=ASC("Z")) THEN

с = с - ASC("A") + 1

ENDIF

IF(c>=ASC("a")AND c<=ASC("z")) THEN

с = с - ASC("a") + 1

ENDIF

IF(c >=1 AND c<=26) THEN a(c)=a(c)+l

S$ = INPUT$(1,#1)

LOOP

imax = 1

FOR i = 2 TO 26

IF a(i) > a(imax) THEN imax = i

NEXT i

PRINT CHR$(imax + 64), a(imax)

END

var a:array['A'..'Z'] of integer;

с, cmax: char;

begin

assign(input'text. dat');

reset(input);

for c:='A'to'Z' do a[c]:=0;

repeat

read(input, c);

c:=upcase(c);

if c in['A'...'Z']then

a[c]:=a[c]+l

until c='.';

cmax := 'A';

for c:='B'to'Z'do

if a[c] > a[cmax] then

cmax := c;

writeln(cmax,' ',a[cmax])

end.



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

Допускается наличие одной синтаксической ошибки.

4
Программа составлена верно, но содержит нерациональности: входные данные запоминаются в массиве символов или строке или входной поток просматривается несколько раз, программа может содержать вложенные циклы. Допускается наличие не более трех синтаксических ошибок.3
Программа составлена в целом верно с вложенными циклами или без, или обрабатывает каждую букву явным образом (26 или 52 оператора IF или оператор CASE, содержащий 26 или 52 вариантов), но, возможно, выводит значение не первой по алфавиту из искомых букв. Возможно в реализации алгоритма содержатся 1–2 ошибки (используется знак «<»

вместо «>», «or» вместо «and» и т. п.). Возможно, некорректно организована работа со входным файлом. Допускается наличие не более пяти синтаксических ошибок.

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

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

1
Задание не выполнено или выполнено неверно0
Максимальный балл4


Пример 1.

Оцените это решение в баллах:

Пример 2.

Оцените это решение в баллах:

Пример 3.

Оцените это решение в баллах:

Пример 4.

Оцените это решение в баллах:



Задание № 12443

В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число — текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 10 000. Все числа не превышают 1000. Временем, в течение которого происходит передача, можно пренебречь.

Необходимо вычислить «бета-значение» серии показаний прибора — минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 7 минут. Если получить такое произведение не удаётся, ответ считается равным –1.

Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору.

Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.

Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.

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

Максимальная оценка за выполнение задания А — 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

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

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм. Обязательно укажите, что программа является решением задания Б.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 7. В каждой из следующих N строк задаётся одно положительное целое число — очередное показание прибора.

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

12

12

45

5

3

14

17

23

21

20

19

18

17

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

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


Пояснение

Задание Б (решение для задания А приведено ниже, см. программу 4). Чтобы произведение было чётным, хотя бы один сомножитель должен быть чётным, поэтому при поиске подходящих произведений чётные показания прибора можно рассматривать в паре с любыми другими, а нечётные — только с чётными.

Для каждого показания с номером k, начиная с k = 8, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k — 7. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное — только чётным.

Для получения эффективного по времени решения нужно по мере ввода данных помнить абсолютное минимальное и минимальное чётное показание на каждый момент времени, каждое вновь полученное показание умножать на соответствующий ему минимум, имевшийся на 7 элементов ранее, и выбрать минимальное из всех таких произведений.

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

Ниже приводится пример такой программы, написанной на алгоритмическом языке.

 

Программа 1. Пример правильной программы на алгоритмическом языке.

Программа эффективна по времени и по памяти

алг

нач

    цел s = 7 | требуемое расстояние между показаниями

    цел amax = 1001 | больше максимально возможного показания

    цел N

    ввод N

    цел a | очередное показание прибора

    целтаб мини[0:s-1] | текущие минимумы последних s элементов

    целтаб миничет[0:s-1] | чётные минимумы последних s элементов

    цел i | вводим первые s показаний, фиксируем минимумы

    цел ма; ма := amax | минимальное показание

    цел мчет; мчет := amax | минимальное чётное показание

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

        ввод а

        ма := imin(ма, a)

        если mod(a,2) = 0 то мчет := imin(мчет,a) все

        мини[mod(i, s)] := ма

        миничет[mod(i, s)] := мчет

    кц

    цел мп = amax*amax | минимальное значение произведения

    цел п

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

        ввод а

            если mod(a,2)=0

            то п := a * мини[mod(i, s)]

            иначе если мчет < amax

            то п := a * миничет[mod(i, s)]

            иначе п := amax*amax;

            все

        все

        мп := imin(мп, п)

        ма := imin(ма, a)

        если mod(a,2) = 0 то мчет := imin(мчет,a) все

        мини[mod(i, s)] := ма

        миничет[mod(i, s)] := мчет

    кц

    если мп = amax*amax то мп:=-1 все

    вывод мп

кон

 

Возможны и другие реализации. Например, вместо циклического заполнения массива можно каждый раз сдвигать его элементы. В приведённом ниже примере хранятся и сдвигаются не минимумы, а исходные значения.

Это требует чуть меньше памяти (достаточно одного массива вместо двух), но по времени решение со сдвигами менее эффективно, чем с циклическим заполнением. Однако время работы остаётся пропорциональным N, поэтому максимальная оценка за такое решение тоже составляет 4 балла.

 

Программа 2. Пример правильной программы на языке Паскаль.

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

const s = 7; {требуемое расстояние между показаниями}

        amax = 1001; {больше максимально возможного показания}

var

        N: integer;

        a: array[1..s] of integer; {хранение s показаний прибора}

        a_: integer; {ввод очередного показания}

        ma: integer; {минимальное число без s последних}

        me: integer; {минимальное чётное число без s последних}

        mp: integer; {минимальное значение произведения}

        p: longint;

        i, j: integer;

begin

        readln(N);

        {Ввод первых s чисел}

        for i:=1 to s do readln(a[i]);

        {Ввод остальных значений, поиск минимального произведения}

        ma := amax; me := amax;

        mp :=amax*amax;

        for i := s + 1 to N do begin

            readln(a_);

            if a[1] < ma then ma := a[1];

            if (a[1] mod 2 = 0) and (a[1] < me) then me := a[1];

            if a_ mod 2 = 0 then p := a_ * ma

            else if me < amax then p := a_ * me

            else p := amax* amax;

            if (p < mp) then mp := p;

            {сдвигаем элементы вспомогательного массива влево}

            for j := 1 to s - 1 do

                a[j] := a[j + 1];

        a[s] := a_

    end;

    if mp = amax*amax then mp:=-1;

    writeln(mp)

end.

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

не выше 3 баллов.

 

Программа 3. Пример правильной программы на языке Паскаль.

Программа эффективна по времени, но неэффективна по памяти

const s = 7; {требуемое расстояние между показаниями}

        amax = 1001; {больше максимально возможного показания}

var

    N, p, i: integer;

    a: array[1..10000] of integer; {все показания прибора}

    ma: integer; {минимальное число без s последних}

    me: integer; {минимальное чётное число без s последних}

    mp: longint; {минимальное значение произведения}

begin

    readln(N);

    {Ввод всех показаний прибора}

    for i:=1 to N do readln(a[i]);

    ma := amax;

    me := amax;

    mp := amax*amax;

    for i := s + 1 to N do

    begin

        if a[i-s] < ma then ma := a[i-s];

        if (a[i-s] mod 2 = 0) and (a[i-s] < me) then

            me := a[i-s];

        if a[i] mod 2 = 0 then p := a[i] * ma

        else if me < amax then p := a[i] * me

        else p := amax * amax;

        if (p < mp) then mp := p

    end;

    if mp = amax*amax then mp := -1;

    writeln(mp)

end.

Возможно также переборное решение, в котором находятся произведения всех возможных пар и из них выбирается минимальное. Ниже (см. программу 4) приведён пример подобного решения. Это (и аналогичные ему) решение неэффективно ни по времени, ни по памяти. Оно является решением задания А, но не является решением задания Б. Оценка за такое решение — 2 балла.

 

Программа 4. Пример правильной программы на языке Паскаль.

Программа неэффективна ни по времени, ни по памяти

const s = 7; {требуемое расстояние между показаниями}

var

    N: integer;

    a: array[1..10000] of integer; {все показания прибора}

    mp: integer; {минимальное значение произведения}

    i, j: integer;

begin

    readln(N);

    {Ввод значений прибора}

    for i:=1 to N do

        readln(a[i]);

    mp := 1000 * 1000 + 1;

    for i := 1 to N-s do begin

        for j := i+s to N do begin

            if (a[i]*a[j] mod 2 = 0) and (a[i]*a[j] < mp)

                then mp := a[i]*a[j]

        end;

    end;

    if mp = 1000 * 1000 + 1 then mp := -1;

    writeln(mp)

end.



Критерии оце­ни­ва­ния вы­пол­не­ния заданияБаллы
Программа пра­виль­но ра­бо­та­ет для любых со­от­вет­ству­ю­щих усло­вию вход­ных данных. При этом не ис­поль­зу­ют­ся мас­си­вы и дру­гие струк­ту­ры данных, раз­мер ко­то­рых за­ви­сит от ко­ли­че­ства вход­ных элементов, а время ра­бо­ты про­пор­ци­о­наль­но этому количеству. Воз­мож­но ис­поль­зо­ва­ние мас­си­вов и ди­на­ми­че­ских струк­тур дан­ных (например, кон­тей­не­ры STL в про­грам­ме на языке C++) при условии, что в них в каж­дый мо­мент вре­ме­ни хра­нит­ся не более 15 эле­мен­тов (минимально не­об­хо­ди­мое ко­ли­че­ство — шесть; до­пус­ка­ет­ся ре­ше­ние с запасом).

Программа может со­дер­жать не более трёх син­так­си­че­ских оши­бок сле­ду­ю­щих видов:

− про­пу­щен или не­вер­но ука­зан знак пунк­ту­а­ции (запятая, точка с запятой, скоб­ки и т.д.);

− не­вер­но на­пи­са­но или про­пу­ще­но слу­жеб­ное слово языка программирования;

− не опи­са­на или не­вер­но опи­са­на переменная;

− при­ме­ня­ет­ся операция, не до­пу­сти­мая для со­от­вет­ству­ю­ще­го типа данных.

К син­так­си­че­ским ошиб­кам при­рав­ни­ва­ет­ся ис­поль­зо­ва­ние не­вер­но­го типа дан­ных (например, ис­поль­зо­ва­ние це­ло­го типа вме­сто ве­ще­ствен­но­го для пред­став­ле­ния дан­ных при вводе и обработке).

Если одна и та же ошиб­ка встре­ча­ет­ся не­сколь­ко раз, она счи­та­ет­ся за одну ошибку.

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

Программа может со­дер­жать не более пяти син­так­си­че­ских и при­рав­нен­ных к ним ошибок, опи­сан­ных в кри­те­ри­ях на 4 балла. Кроме того, до­пус­ка­ет­ся на­ли­чие не более одной «содержательной» ошиб­ки из числа следующих:

− не­вер­ная ини­ци­а­ли­за­ция при по­ис­ке ми­ни­маль­но­го значения;

− не­вер­ная об­ра­бот­ка на­чаль­ных эле­мен­тов данных, ко­то­рая может, например, при­ве­сти к по­лу­че­нию оши­боч­но­го от­ве­та при 6 < N < 12;

− не­точ­ное опре­де­ле­ние гра­ниц массива, выход за гра­ни­цу мас­си­ва (например, опи­сан мас­сив с гра­ни­ца­ми от 1 до 6, а ре­аль­но ис­поль­зу­ет­ся от 0 до 5 или наоборот);

− вы­чис­лен­ный ин­декс эле­мен­та мас­си­ва на 1 от­ли­ча­ет­ся от верного;

− ис­поль­зу­ет­ся знак “<” вме­сто “<=”, “or” вме­сто “and” и т. п.

3
Не вы­пол­не­ны условия, поз­во­ля­ю­щие по­ста­вить 3 или 4 балла. Про­грам­ма ра­бо­та­ет в целом верно, эф­фек­тив­но или нет. Например, до­пус­ка­ет­ся решение, в ко­то­ром все эле­мен­ты хра­нят­ся в мас­си­ве и про­из­во­дит­ся пе­ре­бор всех пар, рас­сто­я­ние между ко­то­ры­ми не мень­ше 6. До­пус­ка­ет­ся до семи син­так­си­че­ских и при­рав­нен­ных к ним оши­бок (см. кри­те­рии на 4 балла). До­пус­ка­ет­ся до двух «содержательных» ошибок, опи­сан­ных в кри­те­ри­ях на 3 балла.2
Не вы­пол­не­ны условия, поз­во­ля­ю­щие по­ста­вить 2, 3 или 4 балла. Из опи­са­ния ал­го­рит­ма или общей струк­ту­ры про­грам­мы видно, что эк­за­ме­ну­е­мый в целом пра­виль­но пред­став­ля­ет путь ре­ше­ния за­да­чи не­за­ви­си­мо от эффективности. При этом про­грам­ма может от­сут­ство­вать или быть пред­став­лен­ной от­дель­ны­ми фрагментами, без огра­ни­че­ний на ко­ли­че­ство ошибок.1
Не вы­пол­не­ны критерии, поз­во­ля­ю­щие по­ста­вить 1, 2, 3 или 4 балла0
Максимальный балл4


Пример 1.

Оцените это решение в баллах:

Пример 2.

Оцените это решение в баллах:



Наверх
Вернуться на основную страницу «Школы экспертов»