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


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

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

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

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

    все

кон


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