На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Rust
  
> ЕГЭ по информатике 2020, часть 1, № 17, поиск в поисковых системах
    ЕГЭ по информатике 2020, вариант Москва
    Поиск в поисковых системах
    Часть 1, № 17
    Задание взято с сайта
    http://kotolis.ru/realegeinf_2020

    Условие.
    В таблице приведены запросы и количество страниц, которые нашёл поисковый сервер по этим запросам в некотором сегменте интернета:

    ЗапросКоличество страниц (тыс.)
    Аврора50
    Крейсер45
    Заря23
    Аврора & Заря9
    Заря & Крейсер0
    Заря / Крейсер / Аврора93


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

    Решение.
    Будем обозначать операцию объединения двух множеств знаком «+», а операцию пересечения двух множеств знаком «&».
    На рисунке показано объединение двух множеств A + B, это вся закрашенная фигура; часть, закрашенная зелёным цветом – пересечение A & B.
    Пусть A и B – конечные множества, |A| - количество элементов первого множества, |B| - второго. Теперь подсчитаем количество элементов их объединения |A + B|:
    |A + B| = |A| + |B| – |A & B|.
    Если просто сложить количество элементов первого и второго множества, то каждый элемент, принадлежащий обоим множествам, будет посчитан дважды. Поэтому из суммы |A| + |B| вычитается количество элементов пересечения |A & B|.

    user posted image

    Теперь рассмотрим объединение трёх множеств и подсчитаем сумму его элементов.
    Если из суммы элементов множеств по отдельности вычесть количество элементов по всем попарным пересечениям двух множеств, то мы вычтем количество элементов, принадлежащих одновременно всем множествам (этот кусочек на рисунке закрашен оранжевым). Поэтому:
    |A V B V C| = |A| + |B| +|C| – |A Λ B| – |A Λ C| – |B Λ C| + |A Λ B Λ C|.

    user posted image

    В общем случае в эту формулу нечётные количества множеств входят со знаком плюс, чётные – со знаком минус.

    В обозначениях задачи операция объединения запросов обозначается знаком «/», операция пересечения – знаком «&», количество страниц – «||».
    |Заря / Крейсер / Аврора| = |Заря| + |Аврора| + |Крейсер|
    – |Аврора & Заря| – |Аврора & Крейсер| – |Заря & Крейсер|
    + |Заря & Аврора & Крейсер|
    Известно, что |Заря & Крейсер| = |Заря & Аврора & Крейсер| = 0
    93 = 23 + 50 + 45 – 9 - |Аврора & Крейсер|
    |Аврора & Крейсер| = 109 – 93 = 16

    Ответ: 16 .
    Сообщение отредактировано: swf -
    0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
    0 пользователей:


    Рейтинг@Mail.ru
    [ Script execution time: 0,0159 ]   [ 16 queries used ]   [ Generated: 24.07.21, 08:11 GMT ]