Дан массив, содержащий 2015 неотрицательных целых чисел. Пиком называется не крайний элемент массива, который больше обоих своих соседей. Необходимо найти в массиве самый высокий пик, то есть пик, значение которого максимально. Если в массиве нет ни одного пика, ответ считается равным 0.
Например, в массиве из шести элементов, равных соответственно 4, 9, 2, 17, 3, 8, есть два пика – 9 и 17, максимальный пик равен 17.
Напишите на одном из языков программирования программу для решения этой задачи. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных.
| Бейсик | Python |
|---|---|
CONST N=2015 DIM A(N) AS INTEGER DIM I, J, K AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I … END
| #допускается также использо- #вание целочисленных #переменных j, k a = [] n = 2015 # менять значение n нельзя for i in range(0, n): a.append(int(input())) …
|
| Паскаль | Алгоритмический язык |
const N=2015; var a: array [1..N] of integer; i, j, k: integer; begin for i:=1 to N do readln(a[i]); … end.
| алг нач цел N=2015| Изменять значение этой переменной нельзя целтаб a[1:N] цел i, j, k нц для i от 1 до N ввод a[i] кц … кон |
| Си++ | |
#include <iostream> using namespace std; #define N 2015 int main(){ int a[N]; int i, j, k; for (i=0; i < N; i++) cin >> a[i]; … return 0; }
| |
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
Необходимо перебрать все элементы массива, кроме первого и последнего (они не могут быть пиками, так как имеют всего по одному соседу), выделить пики и выбрать из них максимальный.
При этом недостаточно просто выбрать максимальный элемент массива, так как он может не быть пиком (например, если несколько одинаковых элементов идут подряд). Решение, основанное на поиске максимума без проверки пиков, не считается верным и оценивается 0 баллов.
Пример правильной программы на Паскале:
k:=0;
for i:=2 to N-1 do begin
if (a[i]>a[i-1]) and (a[i]>a[i+1]) and (a[i]>k)
then k:=a[i];
end;
writeln(k)