Блог учителя Информатики

Решение задачи ExamBegin57


Условие задачи:

На вход в первой строке подается целое число N (> 1), а во второй строке — массив из N целых чисел. Рассматривая всевозможные пары элементов массива, найти минимальное расстояние между элементами (расстояние между числами x и y равно модулю их разности: |x − y|).


uses PT4Exam;

const
  P = 100;

var
  m: array[1..P] of integer;
  i, j, n, k, max, min: integer;

begin
  Task('ExamBegin57');
  Readln(n);
  max := 0;
  for i := 1 to n do
  begin
    Read(m[i]);
    if max < m[i] then max := m[i];
  end;
  min := max; k := max;
  for i := 1 to n do
    for j := 1 to n do
      if i <> j then begin
        k := abs(m[i] - m[j]);
        if k < min then min := k;
      end;
  Write(min);
end.

Выше приведенный листинг с примером решения задачи ExamBegin57 является довольно затратным алгоритмом, основанным на переборе всех возможных пар. Но этот алгоритм можно оптимизировать. Ниже приведен более легкий алгоритм нахождения минимальной разности двух чисел. Давайте рассмотрим его.
Чтобы определить максимальную сумму, надо среди всех чисел найти самое больше число и следующее за ним. Чтобы найти максимальную разность, надо определить максимальное и минимальное число в ряде. Для минимальной суммы нам надо искать самое минимальное число и следующий за ним минимум. Казалось бы, чтобы определить минимальную разность, надо взять минимумы ряда и из одного вычесть другой. Но это будет неверным решением, потому как минимальная разность — это минимальное значение между парой чисел. И обрабатывая числовой ряд мы это значение не найдем.
В любом случае нам нужен будем массив для хранения всех значений. После чего мы этот массив отсортируем используя для этого сортировку пузырьком. Так мы получим ряд друг за другом идущих по возрастанию чисел. Затем, перебирая соседние пары будем находить их разность и искать среди нее минимальную.
С 16 по 30 строку алгоритма мы сортируем массив пузырьком. Для этого используем два цикла. Один внешний, с условием, и второй внутренний со счетчиком. Внешний цикл отвечает за количество пробежек в нашей сортировке, по этому как только мы выстроим массив мы его прерываем меняя логическую переменную check на значение false. Во внутреннем цикле мы перебираем пары элементов, и если левый элемент оказывается больше правого, то меняем их местами. Так же у нас есть счетчик j, который мы увеличиваем при каждой итерации внешнего цикла, т.к. нам нет необходимости делать проверку с крайними правыми числами. Это особенность сортировки пузырьком, т.к. после первого же прогона нашего алгоритма в самую правую ячейку попадет самое больше значение из массива. И так будет происходить при каждой итерации. Поэтому мы и смещаем правую границу при итерации вложенным циклом. Это позволит не делать нам лишние итерации цикла когда они бесполезны.
С 31 по 33 строке мы пробегаемся по массиву и выбираем соседние пары, ищем среди них разность по модулю и среди этих разностей находим самую минимальную, которую запоминаем в переменную min.

uses PT4Exam;

const
  P = 100;

var
  a: array[1..P] of integer;
  n, i, j, t, min: integer;
  check: boolean;

begin
  Task('ExamBegin57');
  read(n);
  for i := 1 to n do
    read(a[i]);
  check := true;
  j := 1;
  while check do
  begin
    check := false;
    for i := 1 to n - j do
      if a[i] > a[i + 1] then
      begin
        t := a[i];
        a[i] := a[i + 1];
        a[i + 1] := t;
        check := true;
      end;
    j := j + 1;
  end;
  min := maxint;
  for i := 1 to n - 1 do
    if abs(a[i] - a[i + 1]) < min then min := abs(a[i] - a[i + 1]);
  write(min);
end.
Поделиться:
Вам также может понравится
Делаем Черепашку в виде снежинки
Перевод десятичных чисел в двоичные на Pascal
Решение задачи ExamBegin80
Решение задачи ExamBegin79

Оставьте комментарий