Номер 2.4, страница 424 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

2.4.!* Пусть имеется несколько неравенств и для каждого из них записаны их решения в виде объединения некоторого количества промежутков. Придумайте способ представления этих промежутков в виде, удобном для компьютерной обработки. Запишите алгоритм, который решает систему этих неравенств и выдаёт результат также в виде объединения некоторого количества промежутков.

Способ представления промежутков

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

Каждый промежуток можно представить структурой со следующими полями:

• left_value: числовое значение левой границы промежутка. Для представления $-\infty$ можно использовать специальное значение, например, константу -Infinity.
• right_value: числовое значение правой границы промежутка. Для представления $+\infty$ можно использовать константу +Infinity.
• left_inclusive: булево (логическое) значение, показывающее, включена ли левая граница в промежуток (true для `[` и false для `(`).
• right_inclusive: булево значение, показывающее, включена ли правая граница в промежуток (true для `]` и false для `)`).

Примеры:

• Промежуток $ [2, 5) $ будет представлен как:
  { left_value: 2, right_value: 5, left_inclusive: true, right_inclusive: false }
• Промежуток $ (-\infty, 10] $ будет представлен как:
  { left_value: -Infinity, right_value: 10, left_inclusive: false, right_inclusive: true }

Таким образом, решение одного неравенства, например $ x \in (-\infty, 0) \cup [3, 7) $, будет представлено как массив из двух таких структур:

[ {left_value: -Infinity, right_value: 0, left_inclusive: false, right_inclusive: false}, {left_value: 3, right_value: 7, left_inclusive: true, right_inclusive: false} ]

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

Ответ: Каждый промежуток представляется в виде объекта с четырьмя полями: значение левой границы, значение правой границы, флаг включения левой границы и флаг включения правой границы. Решение неравенства представляется в виде отсортированного списка (массива) таких объектов.

Алгоритм, который решает систему этих неравенств

Решение системы неравенств — это нахождение пересечения множеств решений каждого из неравенств. Если решения неравенств $ S_1, S_2, \dots, S_N $, то решение системы есть $ S_{системы} = S_1 \cap S_2 \cap \dots \cap S_N $.

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

Общий алгоритм:

1. Пусть имеется $ N $ списков промежутков $ L_1, L_2, \dots, L_N $, каждый из которых является решением одного из неравенств.
2. Инициализируем итоговый список решений: Result = L_1.
3. В цикле от $ i = 2 $ до $ N $ вычисляем новое значение Result как пересечение текущего Result и списка $ L_i $: Result = Intersect(Result, L_i).
4. После завершения цикла список Result будет содержать решение системы неравенств.

Ключевая часть — алгоритм нахождения пересечения двух списков промежутков Intersect(A, B).

На вход подаются два отсортированных и непересекающихся списка промежутков A и B. Алгоритм использует метод двух указателей.

1. Создаем пустой список для результата пересечения IntersectionResult.
2. Инициализируем два указателя: ptrA = 0 для списка A и ptrB = 0 для списка B.
3. Пока оба указателя не вышли за пределы своих списков (ptrA < A.length и ptrB < B.length):
   1. Берем текущие промежутки: intervalA = A[ptrA] и intervalB = B[ptrB].
   2. Находим их возможное пересечение. Левая граница пересечения — это максимум из левых границ: $ l = \max(intervalA.left\_value, intervalB.left\_value) $. Правая граница — это минимум из правых границ: $ r = \min(intervalA.right\_value, intervalB.right\_value) $.
   3. Если $ l < r $, или $ l=r $ и обе границы в этой точке включающие, то пересечение непустое. Создаем новый промежуток-пересечение и добавляем его в IntersectionResult. Флаги включения границ для нового промежутка определяются по более сложным правилам (например, левая граница $ l $ будет включающей, только если она была включающей в том исходном промежутке, из которого она взята, а в другом промежутке точка $ l $ также находилась внутри).
   4. Сдвигаем указатель того промежутка, который заканчивается раньше. Если intervalA.right_value < intervalB.right_value, увеличиваем ptrA. В противном случае увеличиваем ptrB. (Если правые границы равны, можно сдвинуть любой из указателей).
4. Возвращаем список IntersectionResult. Он уже будет отсортирован и состоять из непересекающихся промежутков.

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