Найти два максимальных элемента массива

Задача

В массиве чисел найти два максимальных элемента.

Данная задача требует пояснений и конкретизации:

  • должны ли быть равны между собой эти элементы;
  • или они могут быть разными, но больше, чем все остальные элементы. Например, в массиве [4, 7, 2, 6, 9] два максимальных элемента - это числа 9 и 7.

В данном случае будем считать, что надо найти два наибольших элемента одномерного массива. При этом они могут быть как равны между собой, так и различаться.

Решение

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

const
    N = 10; 
var
    a: array[1..N] of integer;
    i, max1, max2: byte;
begin 
    randomize;
    for i:=1 to N do begin
        a[i] := random(10);
        write(a[i]:3);        
    end;
    writeln;
 
    max1 := 1;
    for i:=2 to N do
        if a[i] > a[max1] then
            max1 := i;
 
    if max1=1 then 
        max2 := 2
    else 
        max2 := 1;
 
    for i:=2 to N do 
        if i <> max1 then // чтобы пропустить max1
            if a[i] > a[max2] then
                max2 := i;
 
    writeln(max1,' ', a[max1]);
    writeln(max2,' ', a[max2]);
end.

Здесь переменные max1 и max2 хранят не значения элементов, а их индексы (этого достаточно, т. к. по индексу всегда можно получить значение).

Обратите внимание на конструкцию if max1=1 then max2 := 2 else max2 := 1; . Она необходима по следующей причине. Мы не знаем, какое начальное значение следует присвоить переменной max2. Ведь если первый наибольший элемент будет первым, и мы присвоим max2 значение 1, то никогда не найдем второй наибольший.

В цикле, определяющем второй максимум, сначала проверяется, не совпадает ли номер текущего элемента с уже учтенным в max1.  Только после этого происходит сравнение значения текущего элемента со значением элемента с индексом max2.

Второй вариант решения задачи - когда оба максимума ищутся в одном цикле:

const
    N = 10; 
var
    a: array[1..N] of integer;
    i, max1, max2, buff: byte;
begin 
    randomize;
    for i:=1 to N do begin
        a[i] := random(10);
        write(a[i]:3);        
    end;
    writeln;
 
    if a[1] > a[2] then begin
        max1 := 1;
        max2 := 2;
    end
    else begin
        max1 := 2;
        max2 := 1;
    end;
 
    for i:=3 to N do
        if a[i] > a[max1] then begin
            buff := max1;
            max1 := i;
            if a[buff] > a[max2] then
                max2 := buff;
        end
        else
            if a[i] > a[max2] then
                max2 := i;    
 
    writeln(max1,' ', a[max1]);
    writeln(max2,' ', a[max2]);
end.

Сначала предполагается, что первые два элемента массива и являются наибольшими. Какой из них первый максимум, а который второй, определяется с помощью конструкции if-else вне цикла. Перебор массива начинается с третьего элемента. Если очередной элемент массива больше первого максимального, то его индекс записывается в первую переменную. (При этом может оказаться, что ранее хранившийся в max1 индекс указывал на второй максимум. Если это так, то он будет записан в max2. Для этого используется переменная buff и вложенное if.) Иначе осуществляется проверка переменной max2.

Пример выполнения кода:

  1  2  0  8  8  7  2  9  6  0
8 9
5 8

Тема

Одномерные массивы

Уровень

Комбинированные задачи

Последняя редакция

Добавить комментарий