Задача «Реки». В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
| Запрос | Найдено страниц (в тысячах) |
|---|---|
| Волга & (Ока | Кама) | 505 |
| Волга & Ока | 230 |
| Волга & Кама | 400 |
Какое количество страниц (в тысячах) будет найдено по запросу Волга & Ока & Кама?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Обозначим через
Запрос Волга & (Ока | Кама) раскрывается так:
Для числа страниц в объединении двух множеств:
Подставим данные (в тысячах):
Количество элементов объединения двух множеств равно сумме их количеств минус количество их пересечения. Здесь множества — страницы «Волга & Ока» и «Волга & Кама», а их пересечение — страницы со всеми тремя словами.
