Написать программу по алгоритму Нахождение суммы чисел последовательности, удовлетворяющих заданному условию: Дана последовательность целых чисел. Количество чисел в последовательности неизвестно, признак окончания последовательности – число 0. Найти сумму элементов последовательности, которые при делении на 7 дают остаток 3

Ответы

ДжулиТян 24.08.2020 07:39

Будем рассматривать каждое введённое число как правый элемент возможной пары (первые 8 чисел не могут быть такими элементами). Для получения максимальной суммы нужно сложить это число с максимальным из всех элементов, расположенных от начала последовательности до элемента, расположенного на 8 позиций раньше текущего. Будем хранить этот максимум и корректировать его при вводе каждого нового элемента. Для этого понадобится хранить последние 8 элементов. Остальные элементы последовательности можно не хранить, это обеспечивает эффективность по памяти. Для хранения 8 элементов можно использовать циклический массив, как показано в следующем решении.

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

const s=8; {требуемое расстояние между элементами}

var

N: integer; {количество чисел}

x: integer; {очередное число}

a: array[0..s-1] of integer;

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

sm: integer; {максимальная сумма пары}

i: integer; {счётчик для ввода}

ia: integer; {текущий индекс в массиве a}

begin

readln(N);

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

for i:=0 to s − 1 do readln(a[i]);

{ввод и обработка остальных значений}

m:=0; sm:=0; ia:=0;

for i:=s to N − 1 do begin

readln(x);

if a[ia] > m then m := a[ia];

if m+x > sm then sm := m+x;

a[ia] := x;

ia := (ia+1) mod s

end;

writeln(sm)

end.

Вместо циклического массива можно использовать сдвиги. В этом случае для вычисления максимума всегда используется первый элемент массива, а новое число записывается в последний. Хотя этот алгоритм работает медленнее, чем алгоритм с циклическим массивом (для каждого элемента требуется 7 дополнительных присваиваний при сдвигах), основное требование эффективности здесь выполнено: при увеличении размера массива в k раз количество действий растёт не более чем в k раз. Ниже приводится пример такой программы.

Решение 2. Правильная и эффективная программы на языке Паскаль (использован сдвиг массива)

const s=8; {требуемое расстояние между элементами}

var

N: integer; {количество чисел}

x: integer; {очередное число}

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

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

sm: integer; {максимальная сумма пары}

i: integer; {счётчик для ввода}

ia: integer; {счётчик для сдвига}

begin

readln(N);

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

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

{ввод и обработка остальных значений}

m:=0; sm:=0;

for i:=s+1 to N do begin

readln(x);

if a[1] > m then m := a[1];

if m+x > sm then sm := m+x;

for ia:=1 to s − 1 do a[ia]:=a[ia+1];

a[s] := x

end;

writeln(sm)

end.

Возможно также «лобовое» решение: запишем в се и сходные числа в массив, переберём все возможные пары и выберем из них требуемую. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Такая программа оценивается не выше двух .

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

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

const s=8; {требуемое расстояние между элементами}

var

N: integer; {количество чисел}

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

sm: integer; {максимальная сумма пары}

i,j: integer;

begin

readln(N);

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

sm :=0;