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


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

По каналу связи передается последовательность положительных целых чисел , … все числа не превышают 1000, их количество заранее неизвестно. Каждое число передается в виде отдельной текстовой строки, содержащей десятичную запись числа. Признаком конца передаваемой последовательности является число 0. Участок последовательности от элемента до элемента называется подъемом, если на этом участке каждое следующее число больше предыдущего. Высотой подъема называется разность . Напишите эффективную программу, которая вычисляет наибольшую высоту среди всех подъемов последовательности. Если в последовательности нет ни одного подъема, программа выдает 0. Программа должна напечатать отчет по следующей форме:

Получено ... чисел Наибольшая высота подъема: …

 

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

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

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

 

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

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

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

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

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

 

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

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

144

17

27

3

7

9

11

10

0

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

Получено 8 чисел

Наибольшая высота подъема: 10

 

Решение.

Программа читает все входные данные один раз, не запоминая все входные данные в массиве. Во время чтения программа помнит число LMax — высоту самого высокого из уже закончившихся подъемов, а также необходимые сведения о текущем подъеме, например, число L — высоту текущего подъема (то есть разность между последним и первым числом участка) и последнее прочитанное число T (это число — наибольшее из чисел текущего подъема). Прочитав очередное число R, программа сравнивает его с числом T. Если R > T, то значение L увеличивается на R-T. В противном случае фиксируется конец подъема и начало нового участка. То есть, во-первых, значение L сравнивается с LMax и, при необходимости, LMax полагается равным L. Во-вторых, полагаем L = 0.

 

Пример правильной и эффективной

программы на языке Паскаль:

Пример правильной и эффективной

программы на языке Бейсик:

program c4_1;

 

var

R, T, N, L, LMax : Integer;

begin

N:=0;

L:=0;

LMax:=0;

T:=1001;

repeat

ReadLn(R);

if R<>0 then N:=N+1;

if R>T then L:=L+R-T

else begin

if L>LMax then LMax:=L;

L:=0;

end;

T:=R;

until R=0;

WriteLn('Получено ', N, ' чисел');

WriteLn('Наибольшая высота подъема ', LMax);

end.

DIM R, T, N, L, LMax AS INTEGER

N = 0

L = 0

LMax = 0

T = 1001;

DO

INPUT R

IF R <> 0 THEN N = N + 1

IF R > T THEN

L = L + R-T

ELSE

IF L > LMax THEN LMax = L

L = 0

END IF

T = R

LOOP UNTIL R = 0

PRINT "Получено "; N; " чисел"

PRINT "Наибольшая высота подъема "; Lmax

Пример правильной и эффективной

программы на языке Алгоритмическом языке:

алг C4_1

нач

цел R, T, N, L, LMax

N:=0

L:=0

LMax:=0

T:=1001;

нц

ввод R

если R<>0 то N:=N+1 все

если R>T то

L:=L+R-T

иначе

если L>LMax то LMax:=L все

L:=0

все T:=R

кц при R=0

вывод "Получено ", N, " чисел", нс

вывод "Наибольшая высота подъема ", LMax, нс

кон