среда, 29 апреля 2015 г.

Задание 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;
}

Комментариев нет:

Отправить комментарий