По каналу связи передаётся последовательность положительных целых чисел Х1, Х2, ... все числа не превышают 1000, их количество заранее неизвестно. Каждое число передаётся в виде отдельной текстовой строки, содержащей десятичную запись числа. Признаком конца передаваемой последовательности является число 0.
Участок последовательности от элемента ХT до элемента XT+N называется подъёмом, если на этом участке каждое следующее число больше или равно предыдущему, причем участок нельзя расширить, т. е.
1) Т = 1 или ХT-1 > ХT
2) XT+N — последний элемент последовательности или XT+N > XT+N+1. Высотой подъёма называется разность
Напишите программу, которая вычисляет количество значительных подъемов в заданной последовательности.
Программа должна вывести результаты в следующей форме:
Получено чисел: ...
Найдено значительных подъемов: ...
Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 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
Приводим решение Игоря Кудашева на Python 3. Программа эффективна только по времени.
a = []
count = 0
up = 0
m = 0
while True:
x = int(input())
if x == 0: break
else: a.append(x)
for i in range(len(a) - 1):
if a[i] <= a[i + 1] and up == 0:
up = 1
m = a[i]
if a[i] > a[i + 1]:
up = 0
if a[i] - m > m:
count += 1
print('Получено чисел:', len(a))
print('Найдено значительных подъемов:', count)