Задача 36. Перебор всех пар элементов в массиве. Вложенные циклы

Условие задачи. Дан целочисленный массив. Найти в нём пару чисел, наиболее близких друг к другу по значению.

Исходными данными в данном примере являются количество элементов заданного массива N и сами целочисленные элементы массива А. Результатами будут номера и значения двух элементов, удовлетворяющих условию.

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

Перебор всех возможных пар элементов требует организации двух циклов, вложенных друг в друга. Так, первый элемент должен быть рассмотрен в паре со всеми остальными элементами – со второго до последнего. Для второго элемента пары будут составлять все элементы, кроме него самого, но в паре с первым элементом он уже был рассмотрен, поэтому остаётся перебрать только элементы с третьего до последнего. Третий элемент уже рассмотрен в паре с первыми двумя, и для него остаётся перебрать элементы с четвёртого до последнего, и так далее. Когда дело дойдёт до последнего элемента, окажется, что он уже рассмотрен в паре со всеми предыдущими элементами. Таким образом, для полного перебора всех пар каждый элемент A[i] (его номер i будет изменяться от 1 до N -1) нужно сопоставлять со всеми элементами A [ j ], стоящими правее него, где j будет изменяться от i +1 до N. Переменная i будет управляющей переменной внешнего цикла, j – внутреннего цикла.

Как всегда делается при поиске минимума, сначала надо задать начальные значения: переменной Min – модуль разности первых двух элементов, переменным Pos1 и Pos 2 – номера этих элементов (1 и 2). Далее во вложенных циклах (i =1, N -1 и j = i +1 ,N) надо для всех пар элементов вычислять модуль их разности R= abs (A[i] - A[j]) и сравнивать его с текущим значением Min, если очередная разность элементов окажется меньше Min, то в переменную Min надо занести эту меньшую разность R для последующих сравнений, а в переменные Pos1 и Pos 2 – номера элементов, для которых вычислялась эта разность (i и j). Тогда по окончании всех переборов в переменной Min окажется самая маленькая разность между элементами, взятая по модулю, а в переменных Pos1 и Pos 2 – номера этих двух элементов.

В качестве результата нужно вывести найденные номера элементов Pos1 и Pos 2, а также значения этих элементов A [Pos1] и A [ Pos 2].

Структурированная запись алгоритма 36

1. Ввести размер массива N и сам массив А.

2. Задать начальные значения Min=abs (A[1] - A[2]); Pos 1 =1; Pos 2 =2.

3. Повторять в цикле для i =1, N -1

3.1. Повторять в цикле для j = i +1, N

3.1.1. Вычислять R = abs(A[i]-A[j])

3.1.2. Сравнивать R c Min: если R < Min, то

3.1.2.3. Min=R

3.1.2.4. Pos1=i; Pos2=j.

4. Вывести Pos1, A[Pos1], Pos2, A[Pos2].

Схема алгоритма

 

Текст программы на языке Си

#include <stdio.h>

#include <math.h>

#define N 25

int main (void)

{

int a[N], n, i, j, min, r, pos1, pos2;

printf ("Введите количество элементов массива");

scanf ("%d", &n);

printf ("Введите элементы массива");

for (i=0; i<n; i++)

scanf ("%d", &a[i]);

min=abs(a[0]-a[1]);

pos1=0; pos2=1;

for (i=0; i<n-1; i++)

for (j=i+1; j<n; j++)

{

    r=abs(a[i]-a[j]);

    if (r<min)

    {

       r=min; pos1=i; pos2=j;

    }

}

printf ("Наиболее близкие элементы a[%d]=%d и \

a[%d]=%d\n", pos1,a[pos1],pos2,a[pos2]);

return 0;

}

Текст программы на языке Паскаль

Program Pr_36;

Var

A: array of integer;

i, N, j, Pos1, Pos2, Min, R: integer;

begin

writeln('Введите количество элементов массива');

readln(N);

SetLength(A,N+1);

{ Памяти выделено на 1 элемент больше, чтобы

использовать более удобную индексацию элементов

  от 1 до N, а не от 0 до N-1 }

writeln('Введите элементы массива');

for i:=1 to N do readln(A[i]);

Min:=abs(A[1]-A[2]);

Pos1:=1; Pos2:=2;

for i:=1 to N-1 do

for j:=i+1 to N do

begin

    R:=abs(A[i]-A[j]);

    if R<Min then

  begin

    Min:=R; Pos1:=i; Pos2:=j

  end;

end;

writeln(ʹНаиболее близкие элементы A[ʹ,Pos1,’]=’,

       A[Pos1],’ и A[ʹ,Pos2,’]=’,A[Pos2]);

A:=Nil

end.