Задача к ЕГЭ по информатике на тему «максимум/минимум» №3

Дан целочисленный массив из $N = 31$ элементов. Элементы массива различны и могут принимать значения от -10000 до 10000. Опишите на одном из языков программирования алгоритм, который находит и выводит второй минимальный элемент массива, если в массиве больше положительных чисел, и второй максимальный, если больше неположительных. Под вторым максимальным элементом подразумевается элемент, следующий за максимальным в порядке убывания, под вторым минимумом — следующий за минимальным в порядке возрастания.

Например, для исходного массива из 6 элементов

-4

-7

программа должна вывести

-4

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

|--------------------------------|------------------------------------|-------------------------| |Б-ейсик-------------------------|P-ython-----------------------------|Ал-горитм-ическ-ий-язы-к-| |CON ST N ASIN T EGER = 31 |# доп ускается такж е |алг | |DIM A(0T ON − 1 )ASLON G |# испо льзовать тр и |нач | | | | | |DIM IASLON G |# цело числен ные пер еменн ые i,t,k | целN = 31 | | TASLON G |a = [] | цел-табa[0 : N − 1 ] | | KASLON G |n = 31 | целi,t,k | |F ORI = 0T ON − 1 |foriinrange (0,n ) : | нц д ляiот0доN − 1 | | IN PU T A (I ) | a.append (int(input ())) | вв одa[i] | | | | | |N EXT I |... | кц | |... | |... | -EN--D-----------------------------------------------------------------кон----------------------|

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Free Pascal 2.6). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах.

Для начала посчитаем, каких элементов больше (положительных или неположительных). Для этого в переменной $t$ (которую изначально приравняем к нулю) будем хранить количество положительных элементов (неположительных тогда будет $N − t$ ). Если положительных элементов окажется больше, будем искать второй минимум, иначе — второй максимум.

Узнав, каких элементов больше, снова обнулим $t$ . Если положительных элементов оказалось меньше, то в $t$ будем хранить первый максимум, а в $k$ — второй. Если первый элемент больше второго, то предположим, что первый элемент массива соответствует первому максимуму, а второй — второму, то есть $t = a[0],k = a[1]$ . Если второй элемент больше первого, то предположим, что $t = a[1],k = a[0]$ . Тогда будем перебирать элементы, начиная с третьего, в цикле $for$ от 2 до $N$ (от 2, так как индексация с нуля). Если элемент оказался больше, чем $t$ , то этот элемент станет первым максимумом, а предыдущий первый максимум теперь второй, то есть $k = t,t = a[i]$ . В переменную $k$ , в которой хранится значение второго максимума, мы записали предыдущее значение первого максимума, а новым первым максимумом стал текущий элемент. Если элемент оказался больше, чем второй максимум, но меньше, чем первый, то только меняем значение второго максимума: $k = a[i]$ .

Если положительных элементов оказалось больше, то в $t$ будем хранить первый минимум, а в $k$ — второй. Если первый элемент меньше второго, то предположим, что первый элемент массива соответствует первому минимуму, а второй — второму, то есть $t = a[0],k = a[1 ]$ . Если второй элемент меньше первого, то предположим, что $t = a[1],k = a[0 ]$ . Тогда будем перебирать элементы, начиная с третьего, в цикле $f or$ от 2 до $N$ (от 2, так как индексация с нуля). Если элемент оказался меньше, чем $t$ , то элемент станет первым минимумом, а предыдущий первый минимум теперь второй, то есть $k = t,t = a[i]$ . В переменную $k$ , в которой хранится значение второго минимума, мы записали предыдущее значение первого минимума, а новым первым минимумом стал текущий элемент. Если элемент оказался меньше, чем второй минимум, но больше, чем первый, то меняем значение только второго минимума: $k = a[i]$ .

После того, как мы перебрали все элементы, в $k$ оказалось значение второго максимума или второго минимума. Выведем его.

Пример программы на $C + +$ (с комментариями):

$k = 0,t = 0;$

$for(i = 0;i < N ;i + + )$

$if(a[i] > 0)t + +; » class=»math» width=»auto»> //если элемент больше нуля, увеличиваем переменную <img decoding=$ , которая отвечает за количество положительных элементов, на 1.

$if (t < N − t){$ //если положительных элементов оказалось меньше, чем неположительных

$t = 0;$ //обнулим $t$

if(a[0] > a [1]){ » class=»math» width=»auto»> //если первый элемент больше второго </p>
<p class= $t = a[0];$ //то первый максимум — это $a[0]$

$k = a [1];$ //а второй — это $a[1]$

$}$

$else{$ //иначе

$k = a [0];$ //второй максимум — это $a[0]$

$t = a[1];$ //а первый — $a[1]$

$}$

$for(i = 2;i < N ;i + + ){$

if(a[i] > t){ » class=»math» width=»auto»> //если элемент больше первого максимума </p>
<p class= $k = t;$ //приравняем второй максимум к текущему значению первого максимума

$t = a[i];$ //и обновим первый максимум

$}$

$if((a[i] > k)& & (a[i] < t))$ //если элемент больше второго максимума, но меньше первого

$k = a[i];$

$}$

if (t > N − t){ » class=»math» width=»auto»> //если положительных элементов оказалось больше, чем неположительных </p>
<p class= $t = 0;$ //обнулим $t$