27-я егэшная (c4). проверьте, правильно ли написана программа и является ли она как можно более эффективной по времени и по памяти. для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8. значение каждого элемента последовательности не превышает 1000. количество элементов последовательности не превышает 10000. напишите программу для решения поставленной , которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности n, т.е. при увеличении n в k раз время работы программы должно увеличиваться не более чем в k раз. программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа n и не превышает 1 килобайта. входные данные представлены следующим образом. в первой строке задаётся число n — общее количество элементов последовательности. гарантируется, что n > 8. в каждой из следующих n строк задаётся одно неотрицательное целое число – очередной элемент последовательности. пример входных данных: 10 100 45 55 245 35 25 10 10 10 26 программа должна вывести одно число — описанное в условии произведение. пример выходных данных для выше примера входных данных: 2600. решение: var n,max,max2,i,a: integer; begin readln(n); max: =8; max2: =0; for i: =1 to n do begin readln(a); if a> max then if max-a> =8 then begin max2: =max; max: =a end else max: =a else if (max-a> =8)and(a> max2) then max2: =a; end; writeln(max*max2); end.
Подумаем, как можно было бы решать задачу.
- Наивный сохранить все числа в массив и пробежаться по нему в двойном цикле, в псевдокоде это выглядит примерно так:
max = 0
for i = 1 to n do
for j = 1 to n do
if |i - j| >= 8 and max < a[i] * a[j] then
max = a[i] * a[j]
Это нехорошо и по времени (время выполнения порядка n^2), и по памяти (количество памяти растет с ростом n пропорционально n).
- Немного ускоряем: у нас пары i, j и j, i ничем не отличаются, так что будем считать, что j < i. Учитывая условие, что |i - j| >= 8, получаем, что j <= i - 8. Переписываем:
max = 0
for i = 9 to n do
for j = 1 to i - 8 do
if max < a[i] * a[j] then
max = a[i] * a[j]
Это решение работает в 2 раза быстрее, но этого недостаточно. Памяти тоже слишком много.
- Продолжаем ускорять. Пусть i зафиксировано. Мы пытаемся сравнить a[i] * a[j] с max для всех j от 1 до i - 8. Очевидно, произведение будет максимально, если a[j] - максимум среди a[1], a[2], ..., a[i - 8]. Возможное решение: создадим массив из максимумов среди первых k чисел, и будем сравнивать уже с максимумом.
maximums[1..n]
maximums[1] = a[1]
for i = 2 to n do
maximums[i] = max(maximums[i - 1], a[i])
max = 0
for i = 9 to n do
if max < a[i] * maximums[i - 8] then
max = a[i] * maximums[i - 8]
Это решение уже работает быстро, но остались проблемы с большим расходом памяти.
- Последний рывок. Заметим, что для того, чтобы разобраться с числом под номером i, нам совсем не нужен массив a, а из массива maximums достаточно знать только maximums[i - 8], ..., maximums[i - 1] - 8 чисел. Так что большие массивы не нужны, их можно убрать. Тогда программа будет эффективна и по времени, и по памяти.
У меня максимумы хранятся в массиве maxs[0..7], все номера берутся по модулю 8. В вашей программе это может быть реализовано иначе.
Pascal:
var
i, n, t, max: integer;
maxs: array[0..7] of integer;
begin
read(n);
read(t);
max := 0;
maxs[1] := t;
for i := 2 to n do
begin
read(t);
if (i > 8) and (max < t * maxs[i mod 8]) then
max := t * maxs[i mod 8];
if t > maxs[(i + 7) mod 8] then
maxs[i mod 8] := t
else
maxs[i mod 8] := maxs[(i + 7) mod 8];
end;
write(max);
end.