В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «», а для логической операции «И» — символ «&». Ниже приведены запросы и…
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «», а для логической операции «И» — символ «&». Ниже приведены запросы и количество страниц, которые нашёл поисковый сервер по этим запросам в некотором сегменте Интернета. Сколько страниц будет найдено по запросу Кинза & Руккола? Запрос Найдено страниц (в сотнях тысяч) Кинза 85 Базилик 79 Руккола 52 Кинза | Базилик | Руккола 157 Кинза & Базилик 34 Руккола & Базилик
К сожалению, по данным заданием точное число страниц определить нельзя. Можно лишь зафиксировать допустимый диапазон.
Обозначения:
- A — страницы, содержащие Кинзу; |A| = 85
- B — страницы, содержащие Базилик; |B| = 79
- C — страницы, содержащие Рукколу; |C| = 52
- A ∪ B ∪ C — найдено страниц: |A ∪ B ∪ C| = 157
- A ∩ B — страницы с Кинзой и Базиликом: |A ∩ B| = 34
- x = |A ∩ C| (нужно найти)
- y = |B ∩ C|
- z = |A ∩ B ∩ C| (тройное пересечение)
Используем Inclusion-Exclusion: 157 = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C| substituting: 157 = 85 + 79 + 52 - 34 - x - y + z = 182 - x - y + z
Отсюда x + y = 182 + z - 157 = 25 + z.
Заметим, что z ≤ |A ∩ B| = 34 и z ≤ |C| = 52, а тройное пересечение z является подмножеством пересечения B и C, поэтому z ≥ 0 и y ≥ z.
Из уравнения x + y = 25 + z следует:
- x ≤ 25 + z - y ≤ 25, потому что y ≥ z (то есть максимальное значение x достигается при y = z, тогда x = 25).
- естественно, x ≥ 0.
Следовательно, допустимый диапазон для x = |A ∩ C|: 0 ≤ x ≤ 25 (в сотнях тысяч страниц).
Примеры допустимых сценариев:
- Пусть z = 0 и y = 25, тогда x = 0.
- Пусть z = 34 и y = 34, тогда x = 25. Оба варианта совместимы с данными и дают корректные значения для объединения и пересечений.
Итак, по заданным данным точное число страниц найти нельзя; оно может быть любым от 0 до 25 (в сотнях тысяч страниц).
