Задание 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 комментариев
Подобные?
сомики 250
меченосцы 200
гуппи 500
сомики & гуппи 0
сомики & меченосцы 20
меченосцы & гуппи 10
Сколько страниц будет найдено по запросу
сомики | меченосцы | гуппи
См. http://ege-go.ru/zadania/grb/b12/zadachi-pro-tri-slova/
Если что непонятно - пиши. Успехов!
А как выполнять например такой?
мезозой 500
кроманьонец 600
неандерталец 700
мезозой | кроманьонец 800
мезозой | неандерталец 1000
неандерталец & (мезозой | кроманьонец) 200
Сколько страниц будет найдено по запросу
кроманьонец & (мезозой | неандерталец)
СМ. http://ege-go.ru/zadania/grb/b12/zadachi-pro-tri-slova/
"B12 РазБор демо-варианта"