СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 27 № 8003

По каналу связи передаются положительные целые числа, не превышающие 1000, — результаты измерений, полученных в ходе эксперимента (количество измерений N известно заранее, гарантируется, что N > 2). После окончания эксперимента передаётся контрольное значение — наименьшее число R, удовлетворяющее следующим условиям:

1) R — сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются);

2) R — чётное число.

В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

Напишите программу (укажите используемую версию языка программирования, например Free Pascal 2.6.4), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:

Вычисленное контрольное значение:

Контроль пройден (или Контроль не пройден)

Постарайтесь, чтобы программа была эффективной. Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Перед текстом программы кратко опишите используемый Вами алгоритм решения.

На вход программе в первой строке подаётся количество чисел N (N > 2). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение. Пример входных данных:

6

100

8

35

145

59

84

92

Пример выходных данных для приведённого выше примера входных данных: Вычисленное контрольное значение: 92.

Решение.

Сумма двух чисел чётна, если они имеют одинаковую чётность (оба чётные или оба нечётные).

Программа, вычисляющая контрольное значение, читает все входные данные один раз, не запоминая их в массиве. Для прочитанного фрагмента входной последовательности программа хранит значения двух самых маленьких чётных и двух самых маленьких нечётных чисел:

М01 — самое маленькое чётное число;

М02 — второе по величине маленькое чётное число;

M11 — самое маленькое нечётное число.

М12 — второе по величине маленькое нечётное число;

После того как все данные прочитаны, искомое контрольное значение вычисляется как меньшая из сумм M01 + M02 и M11 + M12. Поскольку N > 2, обязательно найдётся хотя бы одна пара чисел одинаковой чётности и контрольное значение всегда будет вычислено, но надо отдельно обработать случаи, когда среди данных нет пары чётных или пары нечётных элементов. Эту проверку следует делать очень аккуратно. Например, следующий очень похожий на правильный фрагмент на самом деле ошибочен:

if (M12 > 1000) or (M01+M02 < M11+M12) then res:=M01+M02

else res := M11+M12

Этот фрагмент даст неверный результат, например, при M01=10, M02=1001, M11=901, M12=915.

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

 

Пример правильной и эффективной программы на языке Паскаль

var M01,M02,M11,M12,res,i,N,x, R: longint;

begin

M01 := 1001; M02:= 1001;

M11 := 1001; M12:= 1001;

readln(N);

for i := 1 to N do

begin

readln(x);

if x mod 2 = 0 then begin

if x < M01 then begin

M02:=M01; M01:=x

end

else if x < M02 then M02:=x;

end

else begin

if x < M11 then begin

M12:=M11; M11:=x

end

else if x < M12 then M12:=x;

end

end;

if M02 > 1000 then res:=M11+M12

else if M12 > 1000 then res:=M01+M02

else if M01+M02 < M11+M12 then res := M01+M02

else res := M11+M12

writeln('Вычисленное контрольное значение: ',res);

readln(R);

if R = res

then writeln('Контроль пройден')

else writeln('Контроль не пройден');

end.

 

Пример правильной и эффективной программы на алгоритмическом языке

алг

нач

цел N | количество чисел на входе

цел x | исходные данные

цел m01=1001

цел m02=1001

цел m11=1001

цел m12=1001

цел R | введенное контрольное значение

цел res | вычисленное контрольное значение

ввод N

нц N раз

ввод x

если mod(x,2) = 0 то

выбор

при x < m01:

m02:=m01; m01:=x

при xm02:=x

все

иначе

выбор

при x < m11:

m12:=m11; m11:=x

при x < m12:

m12:=x

все

кц

выбор

при m02 > 1000: res:=m11+m12

при m12 > 1000: res:=m01+m02

при m01+m02 < m11+m12: res:=m01+m02

иначе res:=m11+m12

все

вывод нс, 'Вычисленное контрольное значение: ',res

ввод R

если R=res

то вывод нс, "Контроль пройден"

иначе вывод нс, "Контроль не пройден"

все

кон


Аналоги к заданию № 7684: 7711 7938 8003 Все