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


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

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

 

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

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

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

 

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

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

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

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

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

 

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

 

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

11

12

45.3

5.5

4

25

23

21

20

10

12

26

 

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

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

48

Решение.

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

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

 

 

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

алг

нач

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

цел N

ввод N

вещ а | очередное показание прибора

вещтаб мини[0:s - 1] | текущие минимумы

| последних 6 элементов

цел i

ввод мини[1]

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

ввод а

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

кц

вещ м | минимальное значение произведения

м := 1.0 * 1000 * 1000 + 1

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

ввод а

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

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

кц

вывод м

кон

 

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

алг

нач

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

цел N

ввод N

вещтаб а[0:s - 1] | k-е введенное число

| записываем в ячейку а[mod(k, 6)]

вещ а_ | очередное показание прибора

цел i

| Пролог. Ввод первых шести чисел

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

ввод а_

а[mod(i, s)] := а_

кц

| Ввод остальных значений,

| поиск минимального произведения

вещ мини = 1001 | минимальное введенное число

| (не считая 6 последних)

вещ м | минимальное значение произведения

м := 1.0 * 1000 * 1000 + 1

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

ввод а_

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

м := min(м, а_ * мини)

а[mod(i, s)] := а_

кц

вывод м

кон

 

Далее приведены аналогичные программы на языках Python и Паскаль. В решении на языке Python используется «зацикленный» список prev_min из s = 6 элементов, в котором хранятся последовательные минимумы считанных чисел. Если программа получает на вход последовательность чисел a[0], a[1], … , a[N-1], то сначала заполняются элементы списка prev_min: a[2]), … , prev_min[s - 1] = min(a[0], a[1], … , a[s - 1]). При этом допустимых пар элементов (расстояние между которыми не меньше s) нет, поэтому значение переменной result, в которой хранится ответ, не обновляется. Далее считывается значение элемента последовательности a[s], рассматривается его произведение на prev_min[0] = a[0], при необходимости (если полученное произведение меньше значения result) обновляется значение result. После этого в элемент списка prev_min[0] записывается минимум из считанного числа a[s] и prev_min[s - 1], тем самым prev_min[0] становится равным min(a[0], a[1], … , a[s]). Далее, на каждом шаге в переменную next_num считывается очередной элемент последовательности a[i], он перемножается с prev_min[i % s], в котором в тот момент хранится min(a[0], a[1], … , a[i - s]), при необходимости обновляется переменная result, и далее в результате выполнения присваивания prev_min[i % s] = min(prev_min[(i - 1) % s], next_num) значение prev_min[i % s] становится равно min(a[0], a[1], … , a[i]). Это значение prev_min[i % s] будет затем использовано через s шагов выполнения внешнего цикла, т.е. когда будет считан элемент a[i + s]. При этом все элементы считанной последовательности не сохраняются в списке.

 

 

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

s = 6

result = 1000 * 1000

N = int(input())

prev_min = [0] * s

prev_min[0] = float(input())

for i in range(1, s):

prev_min[i] = min(float(input()), prev_min[i - 1])

for i in range(s, N):

next_num = float(input())

result = min(result, next_num * prev_min[i % s])

prev_min[i % s] = min(prev_min[(i - 1) % s], next_num)

print(result)

 

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

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

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

program c4;

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

var

N: integer;

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

{k-е введенное число записываем в ячейку a[k mod 6]}

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

mn: real; {минимальное введенное число}

{не считая 6 последних}

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

i: integer;

begin

readln(N);

{ Пролог. Ввод первых шести чисел}

for i:=1 to s do

begin

readln(a_);

a[i mod s] := a_

end;

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

mn := 1001; m := 1000 * 1000+1;

for i := s + 1 to N do

begin

readln(a_);

if a[i mod s] < mn then mn := a[i mod s];

if a_ * mn < m then m := a_ * mn;

a[i mod s] := a_

end;

writeln(m)

end.

 

Пример 4. Решение задачи А на языке Паскаль.

var

a: array[1..10000] of real; {исходные данные}

N: integer; {количество показаний прибора в серии}

min: real; {минимальное произведение}

i, j: integer;

begin

readln(N);

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

min := 1000*1000+1;

for i := 1 to N-6 do

for j := i+6 to N do

if (a[i]*a[j] < min) then min := a[i]*a[j];

writeln(min);

end.


Аналоги к заданию № 7472: 8115 Все

Источник: Де­мон­стра­ци­он­ная версия ЕГЭ—2015 по информатике.