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


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

По ка­на­лу связи пе­ре­даётся по­сле­до­ва­тель­ность по­ло­жи­тель­ных целых чисел, все числа не пре­вы­ша­ют 1000. Ко­ли­че­ство чисел из­вест­но, но может быть очень ве­ли­ко. Затем пе­ре­даётся кон­троль­ное зна­че­ние по­сле­до­ва­тель­но­сти — наи­боль­шее число R, удо­вле­тво­ря­ю­щее сле­ду­ю­щим усло­ви­ям:

 

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

 

2) R де­лит­ся на 14.

 

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

 

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

 

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

 

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

 

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

 

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

 

Вам пред­ла­га­ют­ся два за­да­ния, свя­зан­ные с этой за­да­чей: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния А и Б или одно из них по сво­е­му вы­бо­ру.

Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б. Если ре­ше­ние од­но­го из за­да­ний не пред­став­ле­но, то счи­та­ет­ся, что оцен­ка за это за­да­ние со­став­ля­ет 0 бал­лов.

За­да­ние Б яв­ля­ет­ся услож­нен­ным ва­ри­ан­том за­да­ния А, оно со­дер­жит до­пол­ни­тель­ные тре­бо­ва­ния к про­грам­ме. Перед про­грам­мой ука­жи­те вер­сию языка про­грам­ми­ро­ва­ния.

 

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

Обя­за­тель­но ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем за­да­ния А.

Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А – 2 балла.

Б. На­пи­ши­те про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, ко­то­рая будет эф­фек­тив­на как по вре­ме­ни, так и по па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

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

 

 

При­мер вход­ных дан­ных:

 

б

 

77

14

7

9

 

499

100

7700

 

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

 

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

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

Решение.

Произведение двух чисел делится на 14, если:

- один из сомножителей делится на 14 (второй может быть любым) либо

- ни один из сомножителей не делится на 14. причём один из сомножителей делится на 2, а другой - на 7.

Поэтому программа, вычисляющая кодовое число, может работать так.

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

М2 - самое большое чётное число, не кратное 7;

М7 - самое большое число, кратное 7. но не кратное 2;

М14 - самое большое число, кратное 14;

МАХ - самое большое число среди всех элементов последовательности, отличное от M14 (если число М14 встретилось более одного раза и оно же является максимальным, то МАХ = M14).

После того как все данные прочитаны, искомое кодовое слово вычисляется как максимум из произведений M14*МАХ и М2*М7.

Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.

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

 

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

var М2, М7, М14, R, MAX, dat, res, i, N: longint;

begin

M2 := 0; M7 := 0; M14 := 0; MAX := 0;

readln(N);

for i := 1 to N do begin

readln(dat);

if ((dat mod 2) = 0) and ((dat mod 7) >0) and (dat > M2) then M2 := dat;

if ((dat mod 7) = 0) and ((dat mod 2) > 0) and (dat > M7) then M7 := dat;

if (dat mod 14 = 0) and (dat > M14) then begin

if M14 > MAX then begin

MAX := M14;

M14 := dat;

end;

end

else

if dat > MAX then MAX := dat;

end;

readln(R);

if (M2*M7 < M14 *MAX) then

res := M14*MAX

else

res := M2*M7;

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

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

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

end.

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

М14 = 0

М2 = 0

М7 = 0

МАХ = 0

INPUT N

FOR I = 1 ТО N

INPUT DAT

IF DAT MOD 2=0 AND DAT > M2 THEN

M2 = DAT

ELSE

IF DAT MOD 7=0 AND DAT > M7 THEN

M7 = DAT

END IF

END IF

IF DAT MOD 14 = 0 AND DAT > M14 THEN

IF M14 > MAX

THEN

MAX = M14

END IF

M14 = DAT

ELSE

IF DAT > MAX THEN

MAX = DAT

END IF

END IF

NEXT I

INPUT R

IF M7 * M2 < M14 * MAX THEN

RES = M14 * MAX

ELSE

RES = M7 * M2

END IF

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

IF RES = R THEN

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

ELSE

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

END IF

END

 

Пример решения задачи А на языке Паскаль.

var

a: array[1..10000] of integer; {исходные данные}

N: integer; {количество элементов последовательности}

R: integer; {принимаемое контрольное значение}

max: integer; {вычисляемое контрольное значение}

i, j: integer;

begin

readln(N);

max := 0;

for i := 1 to N do read(a[i]);

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 14 = 0) then max := a[i] * a[j];

readln(R);

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

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

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

end.


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

Источник: ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Урал. Ва­ри­ант 1.