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

Дан целочисленный массив из $N = 47$ элементов. Элементы массива различны и могут принимать значения от -10000 до 10000. Опишите на одном из языков программирования алгоритм, который находит и выводит номера двух элементов массива (в порядке возрастания), чья сумма минимальна.

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

-5

984

419

-101

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

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

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

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

Можно решать задачу двумя способами.

$Пер вый сп особ$ : найти первый и второй минимумы в массиве (наименьший элемент и элемент, следующий за минимальным в порядке возрастания) и запомнить их индексы. Для этого способа необходимо хранить индекс первого и второго минимумов и сами первый и второй минимум.

В переменной $k$ будем хранить первый минимум, в $p$ — второй, в $t$ — номер первого минимума, в $m$ — второго. Так как нам известны заранее ограничения на входные данные, приравняем изначально $k$ и $t$ к 10001. Тогда первый (и любой) элемент массива в любом случае будет меньше $k$ и меньше $p$ . Их номера $t$ и $m$ приравняем к -1 (так как нет такого элемента, у которого индекс равен -1).

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

После перебора всех элементов в $k$ будет храниться первый максимум, в $p$ — второй, а в $t$ и $m$ — их индексы. Выведем $t$ и $m$ в порядке возрастания (каждую переменную в новой строке).

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

$k = 10001,p = 10001;$

$t = − 1,m = − 1;$

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

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

$p = k;$ //то предыдущий первый минимум теперь второй

$k = a [i];$ //а первый — текущий элемент

$m = t;$ //индекс второго минимума равен индексу предыдущего первого минимума

$t = i;$ //а индекс нового первого минимума равен индексу текущего

$}$

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

$p = a[i];$ //обновим второй минимум

$m = i;$ //и индекс

$}$

$if (t < m )cout < < t << endl << m;$

$elsecout < < m < < endl < < t;$ //выведем индексы первого и второго максимумов в порядке возрастания

$Втор ой способ$ : в переменной $t$ будем хранить минимальную сумму элементов массива, в $k$ и $m$ — индексы элементов, дающих эту сумму. Для каждого элемента будем попарно считать его сумму с другими элементами. Если она окажется меньше минимальной суммы, то обновим $t$ , $k$ и $m$ .

Изначально предположим, что минимальная сумма — это сумма первых двух элементов, тогда $t = a[0] + a [1]$ , $k = 0$ , $m = 1$ .

В цикле $for$ от $i$ = 0 до $N − 1$ будем перебирать элементы массива. Во вложенном цикле от $j$ = $i + 1$ до $N$ будем считать сумму элементов $a[i]$ и $a [j]$ . Первый цикл от 0 до $N − 1$ , так как для элемента $a [i = N − 1]$ нет элементов $a[j]$ (начальное значение $j = i + 1 = N − 1 + 1 = N$ ). Второй цикл от $j = i + 1$ , потому что мы уже рассмотрели пары элемента $a[i]$ с элементами, расположенными левее в массиве. Если $a[i] + a[j] < t$ , то есть сумма элементов оказалась меньше минимальной, то обновим $t$ ( $t = a[i] + a[j]$ ) и $k$ ( $k = a[i]$ ) и $m$ ( $m = a[j]$ ).