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




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

По каналу связи передаются положительные целые числа, не превышающие 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

27

 

Пример выходных данных для приведённого выше примера входных данных:

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

Контроль пройден

Решение.

Сумма двух чисел может быть кратна 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 := 1001; M2:=1001;

    M3A := 1001; M3B:=1001;

    readln(N);

    for i := 1 to N do begin

        readln(x);

        case x mod 3 of

            0:

                if x                    M3B:=M3A; M3A:=x

                end

                else if x            1:

                if x            2:

                if x                end;

            end;

    if (M1<1001) and (M2<1001) then r1:=M1+M2

    else r1:=2000;

    if (M3A<1001) and (M3B<1001) then r2:=M3A+M3B

    else r2:=2000;

    if r1    else res:=r2;

    if res=2000 then res:=1;

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

    readln(R);

    if R = res

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

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

end.

 

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

алг

нач

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

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

    цел m1=1001

    цел m2=1001

    цел m3a=1001

    цел m3b=1001

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

    цел r1,r2

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

    ввод N

    нц N раз

        ввод x

        выбор

            при mod(x,3)=0:

        выбор

            при x                m3b:=m3a; m3a:=x

            при x                m3b:=x

        все

    при mod(x,3)=1: m1:=imin(m1,x)

    при mod(x,3)=2: m2:=imin(m2,x)

    все

кц

если m1<1001 и m2<1001

    то r1:=m1+m2

иначе r1:=2000

все

если m3a<1001 и m3b<1001

    то r2:=m3a+m3b

иначе r2:=2000

все

res:=min(r1,r2)

если res=2000 то res:=1 все

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

ввод R

если R=res

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

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

все

кон


Аналоги к заданию № 5503: 5791 5823 5855 5887 5951 5983 6017 9211 9319 11128 Все