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




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

Дан массив, содержащий 2015 неотрицательных целых чисел. Ямой называется не крайний элемент массива, который меньше обоих своих соседей. Необходимо найти в массиве самую глубокую яму, то есть яму, значение которой минимально. Если в массиве нет ни одной ямы, ответ считается равным 0.

Например, в массиве из шести элементов, равных соответственно 4, 9, 2, 17, 3, 8, есть две ямы – 2 и 3, самая глубокая яма – 2.

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

 

Бейсик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:=-1;

for i:=2 to N-1 do begin

if ((k=-1) or (a[i] < k)) and (a[i] < a[i-1]) and (a[i] < a[i+1]) then

k:=a[i];

end;

if (k=-1) then writeln('0') else writeln(k);