Задание 17. Пример

Условие: В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос Найдено страниц
(в тысячах)
Шахматы | Теннис 7770
Теннис 5500
Шахматы & Теннис 1000

Какое количество страниц (в тысячах) будет найдено по запросу

Шахматы?

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

Решение:  Через Ответ(Z) будем обозначать множество страниц, найденных по запросу Z, а через   N(Z) – размер множества Ответ(Z), то есть количество страниц, найденных по запросу Z. В этих обозначениях множество Ответ(X&Y) = это пересечение множеств Ответ(X) и Ответ(Y), а множество Ответ(X | Y) – объединение Ответ(X) и Ответ(Y).

Если по запросу Шахматы | Теннис было найдено 7770 страниц, то среди них были страницы, содержавшие либо оба этих слова, либо только одно из них. Так как страниц, содержащих оба эти слова, было найдено ровно 1000, то из 5500 страниц, содержащих слово «Теннис», 1000 содержит также слово «Шахматы», а 4500 – не содержат этого слова. Поэтому из общего количества 7770 страниц, надо вычесть 4500, на которых есть слово «Теннис», но нет слова «Шахматы». Полученное число в 3270 страниц и будет результатом запроса «Шахматы» и, соответственно, ответом на задание.

Ответ:3270

Замечание. Приведенные рассуждения отражают следующий простой факт из теории множеств. Применительно к нашей задаче его можно записать так. Для любых запросов X и Y выполнено:

N(X | Y) = N(X)+N(Y) – N(X&Y)

 
 

5 Комментов

  1. Подобные?
    сомики 250
    меченосцы 200
    гуппи 500
    сомики & гуппи 0
    сомики & меченосцы 20
    меченосцы & гуппи 10
    Сколько страниц будет найдено по запросу
    сомики | меченосцы | гуппи

  2. А как выполнять например такой?
    мезозой 500
    кроманьонец 600
    неандерталец 700
    мезозой | кроманьонец 800
    мезозой | неандерталец 1000
    неандерталец & (мезозой | кроманьонец) 200
    Сколько страниц будет найдено по запросу
    кроманьонец & (мезозой | неандерталец)

  3. Skazochnik:

    "B12 РазБор демо-варианта"

 
 

Что думаете?

 




 
 

 
 
Яндекс.Метрика