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




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

Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

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

 

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

 

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

 

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

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

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

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

 

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

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

10

100

45

55

245

35

25

10

10

10

26

Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 2600.

Решение.

Задание Б (решение для задания А приведено ниже, см. программу 3). Для каждого элемента с номером k (нумерацию начинаем с 1), начиная с k = 9, рассмотрим все допустимые по условиям задачи пары, в которых данный элемент является вторым.

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

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

 

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

program N_27;

const d = 8;

var

N: integer;

a: array[0..d-1] of integer; {буфер}

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

x: integer;

mx: integer; {максимальное введенное число}

{(не считая 8 последних)}

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

i: integer;

begin

readln(N);

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

for i:=1 to d do

begin

readln(x);

a[i mod d] := x

end;

{ Ввод остальных элементов, поиск максимального

произведения}

mx := 0; m := 0;

for i := d + 1 to N do

begin

readln(x);

if a[i mod d] > mx then mx := a[i mod d];

if x * mx > m then m := x * mx;

a[i mod d] := x

end;

writeln(m)

end.

 

 

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

 

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

const d = 8;

var

N: integer;

a: array[1..10000] of integer; {хранение всех

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

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

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

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

i: integer;

begin

readln(N);{Ввод всех элементов последовательности}

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

mn := 0;

m := 0;

for i := d + 1 to N do

begin

if a[i-d] > mn then mn := a[i-d];

if a[i] * mn > m then m := a[i] * mn

end;

writeln(m)

end.

 

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

Const d = 8;

var

N: integer;

a: array[1..10000] of integer;

{хранение всех элементов}

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

i, j: integer;

begin

readln(N);

{Ввод значений элементов}

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

m := 0;

for i := 1 to N-d do begin

for j := i+d to N do begin

if a[i] * a[j] > m then m := a[i] * a[j];

end;

end;

writeln(m)

end.