По каналу связи передаются положительные целые числа, не превышающие 1000 – результаты измерений, полученных в ходе эксперимента (количество измерений N известно заранее, гарантируется, что N > 2). После окончания эксперимента передаётся контрольное значение – наибольшее число R, удовлетворяющее следующим условиям.
1. R – сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются).
2. R кратно 3.
3. Если в последовательности нет двух чисел, сумма которых кратна 3, контрольное значение считается равным 1.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Free Pascal 2.6.4), которая будет проверять правильность контрольного значения.
Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: …
Контроль пройден (или Контроль не пройден)
Перед текстом программы кратко опишите используемый вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N (N > 2). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Пример входных данных:
6
100
8
33
145
19
84
153
Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 153
Контроль пройден
Сумма двух чисел может быть кратна 3 в двух случаях: либо оба слагаемых кратны 3, либо остаток от деления на 3 одного из них равен 1, а другого – 2.
Программа, вычисляющая контрольное значение, читает все входные данные один раз, не запоминая их в массиве. Для прочитанного фрагмента входной последовательности программа хранит значения самых больших чисел, дающих при делении на 3 остатки 1 и 2, и два самых больших числа, кратных 3.
М1 – самое большое число, дающее при делении на 3 остаток 1;
М2 – самое большое число, дающее при делении на 3 остаток 2;
M3A – самое большое число, кратное 3;
M3B – второе по величине число, кратное 3.
После того, как все данные прочитаны, искомое контрольное значение вычисляется, как большая из сумм M1 + M2 и M3A + M3B, но прежде чем вычислять каждую из этих сумм, нужно убедиться, что входящие в неё слагаемые определены, то есть в последовательности были числа с соответствующими остатками.
Ниже приведены правильно реализующие описанный алгоритм программы на языке Паскаль, а также на алгоритмическом языке. Допускаются решения, записанные на других языках программирования.
Пример правильной и эффективной программы на языке Паскаль
var M1,M2,M3A,M3B,R,r1,r2,res,i,N,x: longint;
begin
M1 := 0; M2:=0;
M3A := 0; M3B:=0;
readln(N);
for i := 1 to N do begin
readln(x);
case x mod 3 of
0:
if x>M3A then begin
M3B:=M3A; M3A:=x
end
else if x>M3B then M3B:=x;
1:
if x>M1 then M1:=x;
2:
if x>M2 then M2:=x;
end;
end;
if (M1>0) and (M2>0) then r1:=M1+M2
else r1:=1;
if (M3A>0) and (M3B>0) then r2:=M3A+M3B
else r2:=1;
if r1>r2 then res:=r1
else res:=r2;
writeln('Вычисленное контрольное значение: ',res);
readln(R);
if R = res
then writeln('Контроль пройден')
else writeln('Контроль не пройден');
end.
Пример правильной и эффективной программы на Алгоритмическом языке
алг
нач
цел N | количество чисел на входе
цел x | исходные данные
цел m1=0
цел m2=0
цел m3a=0
цел m3b=0
цел R | введенное контрольное значение
цел r1,r2
цел res | вычисленное контрольное значение
ввод N
нц N раз
ввод x
выбор
при mod(x,3)=0:
выбор
при x>m3a:
m3b:=m3a; m3a:=x
при x>m3b:
m3b:=x
все
при mod(x,3)=1: m1:=imax(m1,x)
при mod(x,3)=2: m2:=imax(m2,x)
все
кц
если m1>0 и m2>0
то r1:=m1+m2
иначе r1:=1
все
если m3a>0 и m3b>0
то r2:=m3a+m3b
иначе r2:=1
все
res:=max(r1,r2)
вывод нс, 'Вычисленное контрольное значение: ',res
ввод R
если R=res
то вывод нс, "Контроль пройден"
иначе вывод нс, "Контроль не пройден"
все
кон