На спутнике «Фотон» установлен прибор, предназначенный для измерения энергии космических лучей. Каждую минуту прибор передаёт по каналу связи неотрицательное вещественное число – количество... | Яндекс.Репетитор

Задание#T25512

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

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

условных единиц. Общее количество показаний прибора в серии не превышает

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

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

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

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

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А.

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

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

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

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

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

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б.

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

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

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

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

В каждой из следующих строк задаётся одно неотрицательное вещественное число – очередное показание прибора.

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

Программа должна вывести одно число – описанное в условии произведение.

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

Показать разбор

Содержание верного ответа

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

Задание Б (решение для задания А приведено ниже, см. программу ). Для каждого показания с номером начиная с

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

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

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

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

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

алг
нач
  цел s = 6 | требуемое расстояние между показаниями
  цел N
  ввод N
  вещ а              | очередное показание прибора
  вещтаб мини[0:s-1] | текущие минимумы последних s элементов
  цел i
  | вводим первые s показаний, фиксируем минимумы
  ввод мини[1]
  нц для i от 2 до s
    ввод а
    мини[mod(i, s)] := min(а, мини[i-1])
  кц
  вещ м    | минимальное значение произведения
  м := 1000.0 * 1000 + 1
  нц для i от s+1 до N
    ввод а
    м := min(м, а * мини[mod(i, s)])
    мини[mod(i, s)] := min(а, мини[mod(i-1, s)])
  кц
  вывод м
кон

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

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

const s = 6; {требуемое расстояние между показаниями}
var
  N: integer;
  a: array[1..s] of real; {хранение s показаний прибора}
  a_: real; {ввод очередного показания}
  mn: real; {минимальное введенное число не считая s последних}
  m: real; {минимальное значение произведения}
  i, j: integer;
begin
  readln(N);
  {Ввод первых s чисел}
  for i:=1 to s do
    readln(a[i]);
  {Ввод остальных значений, поиск минимального произведения}
  mn := 1001;
  m := 1000 * 1000+1;
  for i := s + 1 to N do begin
    if a[1] < mn then mn := a[1];
    readln(a_);
    if a_ * mn < m then m := a_ * mn;
    {сдвигаем элементы вспомогательного массива влево}
    for j := 1 to s - 1 do
      a[j] := a[j + 1];
    a[s] := a_
  end;
  writeln(m)
end.

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

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

const s = 6; {требуемое расстояние между показаниями}
var
  N: integer;
  a: array[1..10000] of real; {хранение всех показаний прибора}
  mn: real; {минимальное введенное число}
            {не считая s последних}
  m: real; {минимальное значение произведения}
  i: integer;
begin
  readln(N);
  {Ввод всех показаний прибора}
  for i:=1 to N do
    readln(a[i]);
  mn := 1001;
  m := 1000 * 1000 + 1;
  for i := s + 1 to N do
  begin
    if a[i-s] < mn then mn := a[i-s];
    if a[i] * mn < m then m := a[i] * mn
  end;
  writeln(m)
end.

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

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

const s = 6; {требуемое расстояние между показаниями}
var
  N: integer;
  a: array[1..10000] of real; {хранение всех показаний прибора}
  m: real; {минимальное значение произведения}
  i, j: integer;
begin
  readln(N);
  {Ввод значений прибора}
  for i:=1 to N do
    readln(a[i]);
  m := 1000 * 1000 + 1;
  for i := 1 to N-s do begin
    for j := i+s to N do begin
      if a[i] * a[j] < m then m := a[i] * a[j];
    end;
  end;
  writeln(m)
end.

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

Предварительные замечания.

В задаче есть два задания (А и Б). Соответственно, ученик может представить две программы. В каждой из программ должно быть указано, решением какого из заданий она является. Если в работе представлена одна программа, то в ней также должно быть указано, решением какого из заданий она является.
Если ученик не указал, к какому заданию относится программа, или можно предположить, что ученик ошибся в идентификации программ, необходимо следовать приведенным ниже инструкциям.

Случай 2.1. Ученик представил только одну программу.

Следует рассматривать программу как решение задания Б и оценивать ее по соответствующим критериям.

Случай 2.2 Ученик представил две программы, но указание задания есть только для одной из программ.

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

Случай 2.3 Ученик представил две программы; ни для одной из них задание не указано или в обоих решениях указано одно и то же задание.

Следует первую (по порядку в представленных учеником материалах) программу рассматривать, как ответ на задание А, а вторую – как ответ на задание Б.

Случай 2.4 Ученик представил более двух программ.

Следует рассматривать только две последние программы и соотносить их с заданиями по правилам 2.1–2.3.

Случай 2.5. Решение, представленное в качестве решения задания А, по критериям для задания Б может быть оценено в или балла. При этом решение, представленное в качестве решения задания Б, получило меньшую оценку.

Следует считать, что ученик перепутал имена заданий и оценивать решение, представленное как решение задания А, по критериям задания Б.

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

Пояснения для проверяющих.

Задание Б является усложнением задания А. Если в качестве решения задания Б представлено решение задания А, то согласно приведенным ниже критериям, его оценка будет такой же, как если бы это решение было представлено в качестве решения задания А.
Два задания и, соответственно, возможность для экзаменуемого представить две программы дают ученику возможность (при его желании) сначала написать менее сложное и менее эффективное решение (задание А), которое дает ему право получить два балла, а затем приступить к поиску более эффективного решения.
Приведенные в пп. 2.1–2.5 правила имеют целью избежать снижения оценки из-за того, что ученик перепутал обозначения заданий. В целом, эти правила эквивалентны такой процедуре проверки:

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

Критерии оценки

Критерии оценивания задания А

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

1 баллНе выполнены условия, позволяющие поставить балла.
Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности.

0 балловНе выполнены критерии, позволяющие поставить или балла

Критерии оценивания задания Б

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

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

– неточное определение границ массива, выход за границу массива (например, описан массив с границами от до а реально используется от до или наоборот);
– вычисленный индекс элемента массива на отличается от верного;
используется операция < вместо <=, or вместо and и т.п.

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

1 баллНе выполнены условия, позволяющие поставить

или балла.
Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. Заметим, что неверным является решение, основанное на следующих рассуждениях. Найдем минимальных элементов, используя вспомогательный массив из значений, запоминая еще и индексы найденных элементов. Тогда среди них обязательно найдутся два, находящиеся на расстоянии не меньше Среди таких пар и выберем ответ. Это неверно, так как ответ может выражаться через одно из этих минимальных значений и находящееся именно от него на расстоянии не меньше число, не попавшее в минимальных. Например, В данном случае описанный алгоритм выдаст

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

0 балловНе выполнены критерии, позволяющие поставить

или балла.

Это задание в разделах:

ЕГЭ-2015 - Архив

Задание#T25512

Это задание в разделах:

Рекомендованные задания