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




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

По каналу связи передаётся последовательность положительных целых чисел Х1, Х2, ... все числа не превышают 1000, их количество заранее неизвестно. Каждое число передаётся в виде отдельной текстовой строки, содержащей десятичную запись числа. Признаком конца передаваемой последовательности является число 0.

 

Участок последовательности от элемента ХT до элемента XT+N называется подъёмом, если на этом участке каждое следующее число больше или равно предыдущему, причем участок нельзя расширить, т.е.

1) Т = 1 или ХT-1 > ХT

2) XT+N — последний элемент последовательности или XT+N > XT+N+1. Высотой подъёма называется разность XT+N − ХT. Подъём считается значительным, если высота подъёма больше величины минимального элемента этого подъема.

 

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

 

Программа должна вывести результаты в следующей форме:

 

Получено чисел: ...

Найдено значительных подъемов: ...

 

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

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

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

 

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

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

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

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

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

 

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

 

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

 

144

17

21

27

3

7

9

11

25

0

 

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

Получено чисел: 9

Найдено значительных подъемов: 1

Решение.

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

 

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

program с4_1;

var

n, up, х, start, last : integer;

begin

n: =0;

up:=0;

start:=1001;

last:=1001;

repeat

readln(x);

n: =n+1;

if x < last then begin

if last > 2*start then up:=up+1;

start:=x;

end;

last:=x;

until x = 0;

writeln('Получено чисел: ', n-1);

writeln('Найдено значительных подъемов: ', up);

end.

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

алг С4_1

нач

цел n, up, х, start, last

n: =0

up: =0

start:=1001

last:=1001

нц

ввод x

n: =n+1

если x < last to

если last > 2*start to up:=up+1 все

start:=x;

все

last:=x;

кц при x=0

вывод "Получено чисел: ", n-1, не

вывод "Найдено значительных подъемов: ", up, не кон

 

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

DIM n, up, х, start, last AS INTEGER

n=0

up=0

start=1001

last=1001

DO

INPUT x

n = n + 1

IF x < last THEN

IF last > 2 * start THEN up = up + 1

start = x;

END IF

last = x

LOOP UNTIL x = 0

PRINT "Получено чисел: "; n-1

PRINT "Найдено значительных подъемов: up