По каналу связи передаются положительные целые числа, не превышающие 1000, – результаты измерений, полученных в ходе эксперимента (количество измерений известно заранее). После окончания эксперимента передаётся контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:
1) R — сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются);
2) R — нечётное число.
Если чисел, соответствующих приведённым условиям, нет, считается, что R = –1. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.
Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.
Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А.
Максимальная оценка за выполнение задания А – 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Обязательно укажите, что программа является решением задания Б.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.
Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество элементов последовательности.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Free Pascal 2.6.4), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: …
Контроль пройден (или Контроль не пройден)
Если удовлетворяющее условию контрольное значение определить невозможно (то есть R = –1), то выводится только фраза «Контроль не пройден».
Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Пример входных данных:
6
100
8
33
45
19
90
145
Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 145
Контроль пройден
Сумма двух чисел нечетна, если одно из них — чётное, а другое — нечетное. Программа, вычисляющая контрольное значение, читает все входные данные один раз, не запоминая их в массиве. Для прочитанного фрагмента входной последовательности программа хранит значения двух величин: М0 – самое большое чётное число; M1 – самое большое нечётное число. После того как все данные прочитаны, искомое контрольное значение вычисляется как сумма M0 + M1. Ниже приведены реализующие этот алгоритм программы на языке Паскаль, а также на алгоритмическом языке. Допускаются решения, записанные на других языках программирования.
Пример правильной и эффективной программы на языке Паскаль.
var R,M0,M1,res,i,N,dat: longint;
begin
M0 := 0;
M1 := 0;
readln(N);
for i := 1 to N do
begin
readln(dat);
if (dat mod 2 = 0) and (dat > M0) then
M0 := dat;
if (dat mod 2 <> 0) and (dat > M1) then
M1 := dat;
end;
if (M0>0) and (M1>0) then
res := M0+M1
else res := -1;
readln(R);
if res > 0 then
writeln('Вычисленное контрольное значение: ',res);
if (R > 0) and (R = res)
then writeln('Контроль пройден')
else writeln('Контроль не пройден');
end.
Пример правильной и эффективной программы на Алгоритмическом языке.
ввод x
если mod(x,2) = 0 и x > m0
то m0 := x
все
если mod(x,2) <> 0 и x > m1
то m1 := x
все
кц
если m0 > 0 и m1 > 0 то
res := m0+m1
иначе
res := -1
все
ввод R
если res>0
то вывод нс, 'Вычисленное контрольное значение: ',res
все
если R>0 и R=res
то вывод нс, "Контроль пройден"
иначе вывод нс, "Контроль не пройден"
все
кон
Пример решения задачи А на языке Паскаль.
vara: array[1..10000] of integer; {исходные данные}
N: integer; {количество показаний прибора в серии}
R: integer; {принимаемое контрольное значение}
max: integer; {максимальная сумма}
i, j: integer;
begin
readln(N);
for i := 1 to N do read(a[i]);
max := -1;
for i := 1 to N-1 do
for j := i+1 to N do
if (a[i]+a[j] > max) and ((a[i]+a[j]) mod 2 <> 0) then max := a[i]+a[j];
readln(R);
writeln('Вычисленное контрольное значение: ', max);
if R <> max then writeln('Контроль не пройден')
else writeln('Контроль пройден');
end.