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




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

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

 

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

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

 

Если чисел, соответствующих приведённым условиям, нет, считается, что R = –1. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

 

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

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

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

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

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

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

 

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

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

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

Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.

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

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество элементов последовательности.

 

 

 

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

 

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

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

 

Если удовлетворяющее условию контрольное значение определить невозможно (то есть R = –1), то выводится только фраза «Контроль не пройден».

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

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

 

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

 

6

100

8

33

45

19

90

145

 

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

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

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

Решение.

Сумма двух чисел нечетна, если одно из них — чётное, а другое — нечетное. Программа, вычисляющая контрольное значение, читает все входные данные один раз, не запоминая их в массиве. Для прочитанного фрагмента входной последовательности программа хранит значения двух величин: М0 – самое большое чётное число; M1 – самое большое нечётное число. После того как все данные прочитаны, искомое контрольное значение вычисляется как сумма M0 + M1. Ниже приведены реализующие этот алгоритм программы на языке Паскаль, а также на алгоритмическом языке. Допускаются решения, записанные на других языках программирования.

 

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

var R,M0,M1,res,i,N,dat: longint;

begin

M0 := 0;

M1 := 0;

readln(N);

for i := 1 to N do

begin

readln(dat);

if (dat mod 2 = 0) and (dat > M0) then

M0 := dat;

if (dat mod 2 <> 0) and (dat > M1) then

M1 := dat;

end;

if (M0>0) and (M1>0) then

res := M0+M1

else res := -1;

readln(R);

if res > 0 then

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

if (R > 0) and (R = res)

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

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

end.

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

 

ввод x

если mod(x,2) = 0 и x > m0

то m0 := x

все

если mod(x,2) <> 0 и x > m1

то m1 := x

все

кц

если m0 > 0 и m1 > 0 то

res := m0+m1

иначе

res := -1

все

ввод R

если res>0

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

все

если R>0 и R=res

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

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

все

кон

 

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

var

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

N: integer; {количество показаний прибора в серии}

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

max: integer; {максимальная сумма}

i, j: integer;

begin

readln(N);

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

max := -1;

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

readln(R);

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

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

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

end.


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