В таблице приведены запросы и количество… (информатика)

Запросы к поисковым системам, формула включений и исключений

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос	Найдено страниц (в сотнях тысяч)
Стихотворение	113
Пушкин	83
Лесков	70
Стихотворение \| Пушкин \| Лесков	211
Стихотворение & Пушкин	22
Стихотворение & Лесков	0

Какое количество страниц (в сотнях тысяч) будет найдено по запросу (Стихотворение | Лесков) & Пушкин?

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение

Обозначим: С — «Стихотворение», П — «Пушкин», Л — «Лесков». Символ «|» означает «ИЛИ» (объединение), «&» означает «И» (пересечение).

Так как , то и .

Шаг . Найдём, сколько страниц содержат и «Пушкин», и «Лесков». Пусть . По формуле включений и исключений:

Шаг . Раскроем искомый запрос:

По формуле включений и исключений для двух множеств:

Проверка по кругам Эйлера: только С: ; только П: ; только Л: . Сумма: , это совпадает с данными.

Запросу (Стихотворение | Лесков) & Пушкин соответствуют области «С и П» () и «П и Л» (): .

💡 Почему так

Запрос с «&» ищет страницы, где есть все слова, а с «|» — хотя бы одно из них. Страницы с «Пушкин» и «Лесков» входят в сумму дважды, поэтому их число находят по формуле включений и исключений. Пересечения «Стихотворение & Лесков» и тройного нет, поэтому области «С и П» и «П и Л» не перекрываются и просто складываются.

Ответ

✓ dzmen.ru

(в сотнях тысяч страниц). Промежуточно: по запросу Пушкин & Лесков найдено .

Помогло?

В таблице приведены запросы и количество найденных по ним страниц некоторого…