Задание 27(С4) с пробного ЕГЭ 2015 Вариант 3.

Задача: 

В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту передаются положительные вещественные числа - текущие показания прибора "Бета 14". Количество передаваемых чисел в серии известно и не превышает 10 000. Все числа не превосходят 1000.

Необходимо вычислить "бета-значение" серии показаний прибора - максимальную сумму двух показаний, между моментами передачи которых прошло не менее 5 минут. Временем, в течение которого происходит передача передача числа, можно пренебречь. В первой строке задается число N - общее количество показаний прибора. Гарантируется, что N>5. В каждой из следующих N строк задается одно положительное вещественное число - очередное показание прибора.

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

10

12

5

45

46

8

11

20

30

28

26

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

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

75

Решение:
Сначала определимся, как получился результат: 30+45=75.

Теперь разберем задачу, что нам известно и какие нам нужны переменные:

N - количество вещественных положительных чисел;

А - массив таких чисел;

Max_Summa - максимальная сумма, которую нужно найти.

Для ее нахождения нужно перебрать все пары чисел на расстоянии не менее 5.

Так для первого числа это будут 6-е, 7-е, 8-е, 9-е. 10-е. 

Для второго - 7-е, 8-е, 9-е. 10-е.

и т.д.

Из этих сумм находим наибольшее. Приведем пример такой программы на Паскале:

var N:integer;

A:array [1..10000]of real;

Max_Summa:real;

i,j:integer;

begin

    readln(N);

    for i:=1 to N do

      readln(A[i]);

    Max_Summa:=0;

    For i:=1 to N-1 do

    For j:=i+5 to N do

        if  A[i]+A[j]>Max_Summa then Max_Summa:=A[i]+A[j];

   writeln(Max_Summa);

end.

Эта программа весит 2 балла, так как использует двойной цикл и массив, зависящий от количества переменных.

Попробуем разобрать алгоритм. Нужно ли перебирать все пары? Применим метод рассуждения как при динамическом программировании (получение решения на основе уже полученного ранее на предыдущем шаге).

С первыми пяти элементами мы ничего не можем делать.

Возьмем 6-й элемент - какой элемент мы будем складывать с ним? Только первый. Считаем его максимальной суммой.

Возьмем 7-й элемент - можно сложить к нему только 1-й и 2-й. А какой наверняка даст нам максимальную сумму (не считая первый полученный максимум)? Наверное тот, который максимальный. Значит нужно определить среди 1-го и 2-го элемента максимальный (обозначим как maximum) и найти максимальную сумму из условия:

если  6-й элемент + maximum > max_summa, то max_summa:=6-й элемент + maximum.

Для следующих элементов рассуждаем аналогично. Получим следующую программу на Delphi (Lazarus, PascalABC):

var N:integer;

A:array of real;

Max_Summa, Maximum:real;

i, j:integer;

begin

    readln(N); setlength(A,N); //нумерация массива от 0 до N-1

    for i:=0 to N-1 do

      readln(A[i]);

    Max_Summa:=0;

   

    For i:=5 to N-1 do begin

     Maximum:=0;

     For j:=0 to i-5 do 

       if A[j]>Maximum then Maximum:=A[j];

     if  A[i]+Maximum>Max_Summa then Max_Summa:=A[i]+Maximum;

   end;

   writeln(Max_Summa);

end.

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

var N:integer;

A:array of real;

Max_Summa, Maximum:real;

i:integer;

begin

    readln(N); setlength(A,N); //нумерация массива от 0 до N-1

    for i:=0 to N-1 do

      readln(A[i]);

    Max_Summa:=0;

    Maximum:=0;

    For i:=5 to N-1 do begin

     if A[i-5]>Maximum then Maximum:=A[i-5];

     if  A[i]+Maximum>Max_Summa then Max_Summa:=A[i]+Maximum;

   end;

   writeln(Max_Summa);

end.

Эта программа на 3 балла. Так как в программе нет вложенных циклов, то она будет эффективна по времени.

Теперь избавимся от большого массива. Посмотрим, что используем мы только первые пять элементов и всегда только последний максимальный. Если массив будет из первых пяти, то для 11-го нужно сравнивать уже с шестым. Поэтому 6-й элемент нужно тоже сохранить для последующей обработки. А куда его деть? Посмотрите, что после обработки 6-го элемента первый элемент уже не нужен, так как он будет максимальный и в дальнейшем нахождении максимального он не нужен. Но остальные 4 элемента нам понадобятся. Можно сделать сдвиг массива влево и записать 6-й элемент как пятый. Этот массив можно представить как очередь (первый пришел - последний вышел). Приведем пример программы на С++:

#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue <float> A;
int N, i;
float Max_Summa=0, Maximum=0, a;
cin>>N;
for(i=0;i<5;i++){cin>>a; A.push(a);}
for(i=5; i<N; i++)
{
a=A.front(); A.pop();
if (a>Maximum) Maximum=a;
cin>>a; A.push(a);
if (a+Maximum>Max_Summa) Max_Summa=a+Maximum;
}
cout<<Max_Summa;
return 0;
}

И эта программа уже будет на 4 балла. Но можно использовать и другой вариант без очереди с массивом из пяти элементов и без сдвига элементов массива влево. 

Заметим, что 5-й элемент нам понадобится только когда будем проверять 10-й, 6-й - для 11-го, 7-й - для 12-го, 8-й - для 13-го, 9-й - для 14-го. А далее 10-й только для 15-го и т.д. Т.е. каждый новый i-ый элемент можно занести в массив под номером, полученному по модулю 5: 

A[i%5]=a;

а ранее сравнивать с тем же элементом A[i%5]:

5-й с нулевым,

6-й с первым,

7-й со вторым,

8-й с третьим,

9-й с четвертым,

10-й с нулевым, который теперь 5-й,

11-й с первым, который теперь 6-й,

12-й со вторым, который теперь 7-й,

13-й с третьим, который теперь 8-й,

14-й с четвертым, который теперь 9-й,

и т.д.

Обратим внимание, что хранить в массиве можно только максимальные элементы. Тогда программа на C++ запишется в виде:

#include <iostream>

using namespace std;
int main()
{
float A[5];
int N, i;
float a, Max_Summa=0, Maximum=0;
cin>>N;
for(i=0;i<5;i++){

   cin>>a; 

   if (a>Maximum) Maximum=a; 

   A[i]=Maximum;

}

for(i=5; i<N; i++)
{
    cin>>a;

    if (A[i%5]+a>Max_Summa) Max_Summa=A[i%5]+a;

    if (a>Maximum) Maximum=a;
    A[i%5]=Maximum; 

}
cout<<Max_Summa;
return 0;
}