Разбор 10 задания ЕГЭ по информатике

На уроке рассматривается разбор 10 задания ЕГЭ по информатике

Объяснение заданий 10 ЕГЭ по информатике

10 тема — «Измерение количества информации» — характеризуется, как задания базового уровня сложности, время выполнения – примерно 4 минуты, максимальный балл — 1

Рассмотрим кратко необходимые для решения 10 задания ЕГЭ понятия и формулы.

Измерение количества информации

  • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
  • 1 бит – это количество информации, которое можно передать с помощью одного знака в двоичном коде (0 или 1).
  • Единицы измерения:
    1 байт (bytе) = 8 бит
    1 Кб (килобайт) = 1024 байта
    1 Мб (мегабайт) = 1024 Кб
    1 Гб (гигабайт) = 1024 Мб
    1 Тб (терабайт) = 1024 Гб
    1 Пб (петабайт) = 1024 Тб


    8 = 23
    1024 = 210

    Рассмотрим еще несколько определений:

  • Алфавит — это набор знаков, используемый в том или ином языке.
  • Мощность алфавита — это количество используемых в алфавите знаков.
  • Мощность алфавита

    Мощность алфавита

  • Сообщение — это любая последовательность символов какого-либо алфавита.

Для вычисления количества информации применяются несколько различных формул в зависимости от ситуации:

Двоичное кодирование сообщений (равновероятностные события)

При вычислении количества информации в сообщении для равновероятностных событий, общее количество которых равно N, используется формула:

N = 2L
  • N — количество сообщений
  • L — длиной битов
  •  

    * следует иметь в виду, что также приняты следующие обозначения: Q = 2k

    Пример 2: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
    двоичное кодирование

    Решение:

    Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодовых слов (L = 2).

    Количество сообщений длиной L битов:

    N = 2L

    Т.е. количество сообщений длиной 2 бита, как в примере с нашими буквами, будет равно N = 22 = 4

    Ответ: 4

    Количество различных сообщений в алфавите разной мощности

    Рассмотрим вариант с 5 буквами (мощность алфавита = 5), которые надо разместить в сообщении длиной 2 символа:

    объяснение 10 задания ЕГЭ по информатике

    Найдем формулу для нахождения количества различных сообщений в алфавите различной мощности:

    Если мощность некоторого алфавита составляет N, то количество различных сообщений длиной L знаков:
    количество сообщений

    • N – мощность алфавита
    • L – длина сообщения
    • Q – количество различных сообщений

    Пример: Сколько существует всевозможных трехбуквенных слов в английском языке?

    Решение:

    В английском алфавите 26 букв. Значит, мощность алфавита = 26. Длина сообщения = 3. Найдем по формуле количество трехбуквенных слов:
    Q = 263
    или
    26 * 26 * 26 = 17576

    Ответ: 17576

  • Таким, образом, если слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение:
  • N = n1 * n2 * … * nL

    Количество сообщений при различном вхождении (встречаемости) букв

    Иногда в заданиях 10 приходится использовать формулу комбинаторики для проверки полученных результатов перебора. Число сочетаний из n элементов по k элементов:

    \[ C{\binom{k}{n}}= \frac{n!}{k!(n-k)!} \]

  • I – количество информации в битах
  • N – количество вариантов
  •  

    Факториал числа n:
    n! = 1 * 2 * 3 * … * n

    Пример: Сколько существует всевозможных четырехбуквенных слов в алфавите из 4 букв: А, Б, В, Г, если известно, что буква А встречается ровно два раза?

    Решение:

    • Длина сообщения = 4. Мощность алфавита = 4. Но мешает условие: буква А встречается ровно два раза.
    • В таких заданиях можно использовать способ перебора всевозможных вариантов:
    • два раза буква А, на остальных местах - одна из трех оставшихся букв:
      А А 3 3     = 3 * 3 = 32 = 9
      А 3 А 3     = 9
      А 3 3 А     = 9 
      3 А А 3     = 9
      3 А 3 А     = 9
      3 3 А А     = 9
        
      
    • Получили 6 вариантов, каждый из которых равен 9.
    • Проверим формулой числа сочетаний:
    • Число сочетаний из n элементов по k элементов:

      \[ C{\binom{k}{n}}= \frac{n!}{k!(n-k)!} \]

    • В задаче:
    • \[ C{\binom{2}{4}}= \frac{4!}{2!(4-2)!} = \frac{24}{2*2} = 6 \]

      * Факториал числа n! = 1 * 2 * 3 *..* n
    • Т.е. проверка прошла успешно, мы получили 6 вариантов.
    • Осталось посчитать количество всех сообщений:
    • 6 * 9 = 54

    Дополнительные формулы

    Количество информации и равновероятные события

    При определении количества информации для равновероятностных событий могут понадобиться две формулы:

  • Формула Шеннона:
  • x = log2(1/p)
  • x — количество информации в сообщении о событии
  • p — ве­ро­ят­ность со­бы­тия
  •  

  • Формула вероятности случайного события:
  • p(A) = m / n
  • m — количество благоприятных исходов (число случаев, способствующих событию А)
  • n — количество общих исходов (общее число равновозможных случаев)
  •  

    Количество информации и неравновероятные события

    При использовании неравновероятного события, вероятность которого равна p, для вычисления количества информации используется формула:

    i = -[log2p]

    *квадратные скобки означают ближайшее целое, меньшее или равное значению выражения в скобках

    Формула Хартли:
    Формула Хартли

    Формула Хартли

  • I – количество информации в битах
  • N – количество вариантов
  •  

    Алфавитный подход:

    Информационный объем сообщения длиной L:

    Алфавитный подход

    Алфавитный подход

  • N — мощность алфавита
  • L — длина сообщения
  •  

    Решение заданий 10 ЕГЭ по информатике

    Сколько вариантов шифра или кодовых слов


    10_1: ЕГЭ по информатике 2017 задание 10 ФИПИ вариант 1 (Крылов С.С., Чуркина Т.Е.):

    Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 6.

    Сколько различных вариантов шифра можно задать, если известно, что цифра 1 должна встречаться в коде ровно 1 раз, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?

    Типовые задания для тренировки


    ✍ Решение:

    • Формула нахождения количества различных сообщений:
    • Q = NL
    • Итак, что у нас дано из этой формулы:
    • Длина сообщения (L) = 5 символов
    • Мощность алфавита (N) = 6 (цифры от 1 до 6).
    • Но так как цифра 1 встречается по условию ровно один раз, а остальные 5 цифр — любое количество раз, то будем считать, что N = 5 (цифры от 2 до 6, исключая 1). Т.е. возьмем вариант, когда 1 стоит на первом месте, а остальные 5 цифр размещаем на 4 позиции:
    • 1 5 5 5 5 - 1 * Q = 54 = 625
      

      ✎ 1 способ. Найдем количество вариантов методом перебора:

    • Методом перебора найдем количество вариантов размещения:
    • 1 5 5 5 5 - 1 * Q=54 = 625
      5 1 5 5 5 - 1 * Q=54 = 625
      5 5 1 5 5 - 1 * Q=54 = 625
      5 5 5 1 5 - 1 * Q=54 = 625
      5 5 5 5 1 - 1 * Q=54 = 625
      
    • получили 5 вариантов;
    • ✎ 2 способ. Найдем количество вариантов при помощи формулы комбинаторики:

      \[ C{\binom{4}{5}}= \frac{5!}{4!(5-4)!} = 5 \]

    • получили 5 вариантов;
    • В итоге получим:
    • 625 * 5 = 3125
      

    Результат: 3125

    Детальный разбор задания 10 ЕГЭ по информатике предлагаем посмотреть в видеоуроке:



    10_2: ЕГЭ по информатике 2017 задание 10 ФИПИ вариант 10 (Крылов С.С., Чуркина Т.Е.):

    Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является либо буквой (A или B) или цифрой (1, 2 или 3).

    Сколько различных вариантов шифра можно задать, если известно, что в коде присутствует ровно одна буква, а все другие символы являются цифрами?


    ✍ Решение:

    • Формула нахождения количества различных сообщений:
    • Q = NL
    • Посчитаем количество возможных шифров для одного из вариантов (например, когда буквы находятся на первой позиции). Так как цифры (1, 2, 3) могут занимать 4 позиции из пяти, а две буквы (А и В) одну из позиций, значит:
    • Q = 2 * 34 = 162
      
    • Имеем 162 вариантов шифра для слова, в котором буквы могут стоять на первой позиции:
    • AB  123 123 123 123 = 162
    • Получим все варианты размещения:
    • "2" означает одна из двух букв: А или B, "3" - одна из трех цифр:
      
      2 3 3 3 3 -> Q = 2 * 34 = 162
      3 2 3 3 3 -> Q = 2 * 34 = 162
      3 3 2 3 3 -> Q = 2 * 34 = 162
      3 3 3 2 3 -> Q = 2 * 34 = 162
      3 3 3 3 2 -> Q = 2 * 34 = 162
      
    • Получили 5 вариантов с размещением букв А и B.
    • Осталось умножить:
    • 5 * 162 = 810
      

    Результат: 810

    Подробное решение данного задания предлагаем посмотреть на видео:



    10_3: Разбор 10 задания ЕГЭ по информатике (К. Поляков, задание 69):

    Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 4-буквенные слова, в которых есть только буквы A, Б, В, Г, Д и Е, причём буква Г появляется ровно 1 раз и только на первом или последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.

    Сколько различных кодовых слов может использовать Олег?

    ✍ Решение:

    • Вспомним формулу получения количества возможных вариантов слов:
    • N = n1 * n2 * n3 * … * nL = nL

    • где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
    • Рассмотрим варианты, когда буква Г встречается на первом или последнем месте:
    • Г ? ? ? = 1 * 5 * 5 * 5 = 53 = 125 
      ? ? ? Г = 5 * 5 * 5 * 1 = 53 = 125
      
    • Вместо знаков ? может стоять одна из пяти букв (А, Б, В, Д, Е), т.к. буква Г там стоять не может
    • Теперь суммируем количество найденных вариантов:
    • 125 + 125 = 250

    Результат: 250

    Видеоразбор данного задания:



    10_4: ЕГЭ по информатике 2017 задание 10 ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

    Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является одной из букв X, Y или Z.

    Сколько различных вариантов шифра можно задать, если известно, что буква X должна встречаться в коде ровно 2 раза, а каждая из других допустимых букв может встречаться в шифре любое количество раз или не встречаться совсем?
      
    Типовые задания для тренировки


    ✍ Решение:

    • Формула нахождения количества различных сообщений:
    • Q = NL
    • Итак, что у нас дано из этой формулы:
    • Начальная мощность алфавита (N) = 3 (буквы X, Y, Z). Но так как буква X встречается ровно два раза, то мы ее рассмотрим отдельно, а остальные 2 буквы — встречаются любое количество раз, значит, будем считать, что:
    • N = 3 - 1 = 2 (Y и Z)
    • Исходя из предыдущего пункта, длина сообщения тоже сократится:
    • (L) = 5 - 2 = 3 символа (остальные два символа отведем на размещение X)
    • Количество различных сообщений (вариантов шифра) = Q = ?
    • Т.е. для одного варианта размещения (для одного варианта шифра) имеем:
    • X X ? ? ? -> 12 * Q = 23 = 8
      
    • Согласно условию получим следующие варианты размещения:
    • ✎1 способ. Перебор всех вариантов:

      X X ? ? ? - 12 * Q = 23 = 8
      X ? X ? ? - 12 * Q = 23 = 8
      X ? ? X ? - 12 * Q = 23 = 8
      X ? ? ? X - 12 * Q = 23 = 8
      ? X X ? ? - 12 * Q = 23 = 8
      ? X ? X ? - 12 * Q = 23 = 8
      ? X ? ? X - 12 * Q = 23 = 8
      ? ? X X ? - 12 * Q = 23 = 8
      ? ? X ? X - 12 * Q = 23 = 8
      ? ? ? X X - 12 * Q = 23 = 8
      

      ✎ 2 способ. При помощи формулы поиска числа сочетаний:

      \[ C{\binom{k}{n}}= \frac{n!}{k!(n-k)!} \]

      Число сочетаний из n элементов по k элементов:

      \[ C{\binom{2}{5}}= \frac{5!}{2!(5-2)!} = \frac{120}{12} = 10 \]

      * Факториал числа: n! = 1 * 2 * 3 * .. * n

    • Количество вариантов найдено верно, т.к. результат обоих способов = 10. В итоге получаем:
    • 8 * 10 = 80
      
    * задание достаточно решить одним из способов!

    Результат: 80

    Детальный разбор задания 10 ЕГЭ по информатике предлагаем посмотреть в видеоуроке:



    10_5: Разбор 10 задания Тренировочный вариант №1 2018 (от 03.09.2018):

    Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв ОСЕНЬ? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
      
    Типовые задания для тренировки


    ✍ Решение:

    • Из букв слова ОСЕНЬ имеем 2 гласных буквы (О, Е) и 2 согласных буквы (С, Н). Буква мягкий знак «нейтральна».
    • Подсчитаем количество букв на каждой из 5 позиций:
    • 2   5   5   5   2
      СН   все  все  все   ОЕ
      
    • Вспомним формулу получения количества возможных вариантов слов:
    • N = n1 * n2 * n3 * … * nL = nL

    • где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
    • Т.е. количество вариантов равно произведению полученных чисел:
    • N = 2 * 5 * 5 * 5 * 2 = 500
      

    Результат: 500

    Разбор можно также посмотреть на видео:



    10_6: Разбор 10 задания ЕГЭ по информатике (К. Поляков, задание 42):

    Вася составляет 4-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.

    Сколько существует таких слов, которые может написать Вася?
      
    Типовые задания для тренировки

    ✍ Решение:

      ✎ 1 способ:

    • Количество вариантов различных слов вычислим по формуле:
    • N = n1 * n2 * n3 * …
      где

    • n1 — количество вариантов выбора первой буквы и т.п.
    • Рассмотрим все варианты расположения буквы Е:
    • 1. Е ? ? ? или 
      2. ? Е ? ? или 
      3. ? ? Е ? или
      4. ? ? ? Е 
      
      Где вопросительный знак означает любую букву из Л, Е, Т, О.
      
    • Подсчитаем по формуле количество слов для варианта 1:
    • Е ? ? ? = 1 * 4 * 4 * 4 = 64
      
      т.е. на первой позиции - только 1 буква - Е, на каждой последующей - одна из четырех букв Л, Е, Т, О.
      
    • Подсчитаем по формуле количество слов для варианта 2; учтем, что на первой позиции букву Е мы уже посчитали для первого варианта!:
    • ? Е ? ? = 3 * 1 * 4 * 4 = 48
    • Подсчитаем по формуле количество слов для варианта 3; учтем, что на первой и второй позициях букву Е мы уже посчитали в предыдущих вариантах!:
    • ? ? Е ? = 3 * 3 * 1 * 4 = 36
    • Подсчитаем по формуле количество слов для варианта 4; учтем, что на первой, второй и третьей позициях букву Е мы уже посчитали в предыдущих вариантах:
    • ? ? ? Е = 3 * 3 * 3 * 1 = 27
    • Поскольку у нас каждый вариант связан операцией логическое ИЛИ, то теперь суммируем все варианты:
    • 64 + 48 + 36 + 27 = 175

    Результат: 175
    ✎ 2 способ:

    • Так как по условию буква Е встретится хотя бы 1 раз, значит, можно утверждать, что не может быть такого, чтобы буква Е не встретилась бы ни одного раза.
    • Таким образом, рассчитаем случай, когда буква Е встречается все 4 раза (т.е. все случаи) и отнимем от результата невозможный случай: когда буква Е не встретится ни одного раза:
    • 1. Буква Е используется 4 раза (т.е. на всех позициях):
      4 * 4 * 4 * 4 = 256
      
      2. Буква Е не используется совсем (т.е. только 3 буквы):
      3 * 3 * 3 * 3 = 81
      
    • Вычтем из первого варианта невозможный вариант № 2:
    • 256 - 81 = 175
      

    Результат: 175

    Решение задания 10 смотрите в видеоуроке:



    10_7: Разбор 10 задания ЕГЭ по информатике (К. Поляков, задание 50):

    Вася составляет 4-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.

    Сколько существует таких слов, которые может написать Вася?
      
    Типовые задания для тренировки

    ✍ Решение:

    • Количество возможных вариантов слов вычислим по формуле:
    • N = n1 * n2 * n3 * … * nL = nL

    • где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
    • Сначала по формуле получим все варианты для всех пяти букв, включая букву Р:
    • 5 * 5 * 5 * 5 = 54 = 625
    • Из общего количества вариантов нам необходимо исключить те варианты, где Р не встречается вообще и Р встречается только 1 раз. Найдем их последовательно:
    • 1. Буква Р не встречается совсем:
    • 4 * 4 * 4 * 4 = 44 = 256
    • 2. Буква Р встречается только один раз:
    • р ? ? ? = 1 * 4 * 4 * 4 = 43
      ? р ? ? = 4 * 1 * 4 * 4 = 43
      ? ? р ? = 4 * 4 * 1 * 4 = 43
      ? ? ? р = 4 * 4 * 4 * 1 = 43
      
      Получим  43 * 4 = 256
      
    • Теперь вычтем из общего количества найденные варианты (№ 1 и № 2):
    • 625 - 256 - 256 = 113

    Результат: 113

    Решение 10 задания предлагаем посмотреть в видеоуроке:



    10_8: Разбор 10 задания ЕГЭ по информатике (К. Поляков, задание 70):

    Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 5-буквенные слова, в которых есть только буквы A, Б, В, и Г, причём буква Г появляется не более одного раза и только на последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.

    Сколько различных кодовых слов может использовать Олег?

    ✍ Решение:

    • Вспомним формулу получения количества возможных вариантов слов:
    • N = n1 * n2 * n3 * … * nL = nL

    • где n1 — количество вариантов выбора первой буквы,
    • n2 — количество вариантов выбора второй буквы и т.п.
    • Так как буква Г появляется не более одного раза и только на последнем месте, значит, она может либо появиться 1 раз на последнем месте, либо не появиться совсем.
    • Рассмотрим варианты, когда буква Г встречается 1 раз на последнем месте и встречается 0 раз:
    • 1 раз: ? ? ? ? Г = 3 * 3 * 3 * 3 * 1 = 34 = 81 
      0 раз: ? ? ? ? ? = 3 * 3 * 3 * 3 * 3 = 35 = 243
      
    • Вместо знаков ? может стоять одна из трех букв (А, Б, В), т.к. буква Г там стоять не может
    • Теперь суммируем количество найденных вариантов:
    • 81 + 243 = 324

    Результат: 324



    10_9: Разбор 10 задания ЕГЭ по информатике (К. Поляков, задание 52):

    Вася составляет 4-буквенные слова, в которых есть только буквы К, О, М, А, Р, причём буква А используется в них не более 3-х раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.

    Сколько существует таких слов, которые может написать Вася?
      
    Типовые задачи для тренировки

    ✍ Решение:

    • Вспомним формулу получения количества возможных вариантов слов:
    • N = n1 * n2 * n3 * … * nL = nL

    • где n1 — количество вариантов выбора первой буквы,
    • n2 — количество вариантов выбора второй буквы и т.п.
    • Так как буква А по условию используется не более 3-х раз, это значит, что она используется либо 3 раза, либо 2 раза, либо 1 раз, либо не используется совсем. Рассмотрим все эти варианты отдельно.
    • 1. Буква А используется 3 раза:
    • А А А _  -> 1 * 1 * 1 * 4 = 4
      А А _ А  -> 1 * 1 * 4 * А = 4
      А _ А А  -> 1 * 4 * 1 * 1 = 4
      _ А А А  -> 4 * 1 * 1 * 1 = 4
      
    • Итого получаем 4 варианта, в которых вместо символа _ может быть любая из 4 букв: К О М Р. Значит, имеем:
    •  4 * 4 = 16 вариантов
      
    • 2. Буква А используется 2 раза:
    • А А _ _  -> 1 * 1 * 4 * 4 = 16
      А _ А _  -> 1 * 4 * 1 * 4 = 16
      А _ _ А  -> 1 * 4 * 4 * 1 = 16
      _ А А _  -> 4 * 1 * 1 * 4 = 16
      _ А _ А  -> 4 * 1 * 4 * 1 = 16
      _ _ А А  -> 4 * 4 * 1 * 1 = 16
      
    • Итого получаем 6 вариантов, в которых вместо символа _ может быть любая из 4 букв: К О М Р. Значит имеем:
    •  16 * 6 = 96 вариантов
      
    • 3. Буква А используется 1 раз:
    • А _ _ _  -> 1 * 4 * 4 * 4 = 64
      _ А _ _  -> = 64
      _ _ А _  -> = 64
      _ _ _ А  -> = 64
      
    • Итого имеем:
    • 64 * 4 = 256 вариантов
      
    • Буква А используется 0 раз:
    • _ _ _ _ -> 44 = 256
      
    • Суммируем результаты всех трех случаев:
    • 16 + 96 + 256 + 256 = 624

    Результат: 624

    Решение смотрите также на видео:



    10_10: Разбор 10 задания ЕГЭ по информатике (К. Поляков, задание 32):

    Сколько существует различных символьных последовательностей длины 3 в четырёхбуквенном алфавите {A,B,C,D}, если известно, что одним из соседей A обязательно является D, а буквы B и C никогда не соседствуют друг с другом?

    ✍ Решение:

    • Вспомним формулу получения количества возможных вариантов слов:
    • N = n1 * n2 * n3 * … * nL = nL

    • где n1 — количество вариантов выбора первой буквы,
    • n2 — количество вариантов выбора второй буквы и т.п.
    • Будем рассматривать варианты, расставляя каждую букву последовательно по алфавиту, начиная с первой буквы. При этом будем учитывать указанные ограничения для букв А, B и С:
    • Начинаем с A: A D 4ABCD = 1 * 1 * 4 = 4 
      Начинаем с B: B A D, B B 2BD, B D 4ABCD = 7
      Начинаем с C: C A D, C C 2CD, C D 4ABCD = 7
      Начинаем с D: D A 3BCD, D B 2BD, D C 2CD, D D 4ABCD = 11
      
    • Теперь суммируем количество найденных вариантов:
    • 4 + 7 + 7 + 11 = 29

    Результат: 29

    Видеоурок демонстрирует подробное решение задания:



    10_11: Разбор 10 задания Тренировочный вариант №3 2018 (от 01.10.2018):

    Из букв С, Р, Е, Д, А составляются трехбуквенные комбинации по следующему правилу – в комбинации не может быть подряд идущих гласных и одинаковых букв.

    Например, комбинации ААР или ЕСС не являются допустимыми.

    Сколько всего комбинаций можно составить, используя это правило?


    ✍ Решение:

    • Рассмотрим два варианта: когда слово начинается с гласной буквы, и когда оно начинается с согласной.
    • 1. С гласной:

      1.1
      2 3 2 = 2 * 3 * 2 = 12
      гл с  с
      
      1.2
      2 3 2 = 2 * 3 * 2 = 12
      гл с гл
      

      2. С согласной:

      2.1
      3  2  2 = 3 * 2 * 2 = 12
      с  с  с
      
      2.2
      3  2  3 = 3 * 2 * 3 = 18
      с гл  с
      
      2.3
      3  2  2 = 3 * 2 * 2 = 12
      с  с  гл
      
    • Подсчитаем общее количество вариантов:
    • 12 + 12 + 12 + 18 + 12 = 66
      

    Результат: 66


    10_12: Разбор 10 задания (К. Поляков, задание 76):

    Дано слово КОРАБЛИКИ. Таня решила составлять новые 5-буквенные слова из букв этого слова по следующим правилам:
    1) слово начинается с гласной буквы;
    2) гласные и согласные буквы в слове должны чередоваться;
    3) буквы в слове не должны повторяться.

    Сколько существует таких слов?
      
    Типовые задачи для тренировки


    ✍ Решение:

    • Учтем, что в слове КОРАБЛИКИ две буквы К и две И.
    • Всего в слове 4 гласных, но поскольку две буквы И, то необходимо считать только 3 гласных.
    • Всего в слове 5 согласных, однако две из них — буквы К, поэтому считать следует 4 согласных.
    • Посчитаем количество согласных и гласных для каждой из 5 позиций слова, учитывая, что с каждой последующей буквой количество используемых гласных/согласных уменьшается. Под позициями приведем пример букв:
    • гл   с   гл   с   гл  
      3    4    2   3    1
      оаи   крбл   оа   крб    и
      
    • Количество слов вычисляется как произведение полученных чисел:
    • 3 * 4 * 2 * 3 * 1 = 72
      

    Результат: 72


    Список в алфавитном порядке


    10_13: ЕГЭ по информатике 2017 задание 10 ФИПИ вариант 20 (Крылов С.С., Чуркина Т.Е.):

    Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Ниже приведено начало списка:

    1. ААААА
    2. ААААО
    3. ААААУ
    4. АААОА

    Запишите слово, которое стоит под номером 242 от начала списка.

    ✍ Решение:

    • Данное задание лучше решать следующим образом. Подставим вместо букв цифры (А -> 0, О -> 1, У -> 2):
    • 1. 00000
      2. 00001
      3. 00002
      4. 00010
      ...
      
    • Видим, что каждая последующее число получается путем прибавления в столбик единицы к предыдущему числу. В троичной системе счисления! Т.к. цифр всего три.
    • Порядковый номер, написанный рядом с пунктом, всегда на единицу больше располагающейся рядом цифры в троичной системе счисления.
    • Значит, пункту под номером 242 будет соответствовать число 241 в троичной системе счисления.
    • Переведем 241 в 3-ю систему делением на 3:
    •         остатки
      241 | 3 | 1
       80 | 3 | 2
       26 | 3 | 2
        8 | 3 | 2
        2 |   |
      
    • Перепишем остатки снизу вверх: 22221, им соответствуют буквы УУУУО

    Результат: УУУУО

    Подробное решение смотрите на видео:



    10_14: 10 задание. Демоверсия ЕГЭ 2018 информатика:

    Все 4-буквенные слова, составленные из букв Д, Е, К, О, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1.
    Ниже приведено начало списка.

    1. ДДДД
    2. ДДДЕ
    3. ДДДК
    4. ДДДО
    5. ДДДР
    6. ДДЕД
    …
    

    Под каким номером в списке идёт первое слово, которое начинается с буквы K?

    ✍ Решение:

    • Подставим вместо букв цифры (Д -> 0, Е -> 1, К -> 2, О -> 3, Р -> 4):
    • 1. 0000
      2. 0001
      3. 0002
      4. 0003
      5. 0004
      6. 0010
      ...
      
    • Видим, что каждое последующее число получается путем прибавления единицы в столбик к предыдущему (в пятеричной системе счисления! т.к. цифр всего пять).
    • Порядковый номер, написанный рядом с пунктом, всегда на единицу больше располагающейся рядом цифры в пятеричной системе счисления.
    • Определим число, которое получится, если мы в начале слова поставим букву К (остальные должны остаться нулями, т.к. числа идут по порядку, а нам необходимо первое, начинающееся с К):
    • K -> 2 -> 2000
    • Полученное число — 2000 — необходимо перевести из пятеричной системы счисления в десятичную, чтобы узнать порядковый номер:
    • По формуле разложения числа по степеням основания:
      
      20005 = 2 * 53 + 0 * 22 + 0 + 0 = 2 * 125 = 25010 
      
    • Поскольку порядковый номер числа всегда на единицу больше самого числа, то имеем 251.

    Результат: 251

    Подробное решение 10 задания демоверсии ЕГЭ 2018 года смотрите на видео:



    10_15: Решение 10 задания ЕГЭ по информатике 2018 (контрольный вариант № 2 экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков, Тренажер ЕГЭ):

    Все 4-буквенные слова, составленные из букв П, Р, С, Т, записаны в алфавитном порядке.
    Вот начало списка:

    1. ПППП
    2. ПППР
    3. ПППС
    4. ПППТ
    5. ППРП
    ... ...
    

    На каком месте в списке стоит первое слово, начинающееся с буквы Р?
      
    Типовые задачи для тренировки


    ✍ Решение:

    Результат: 65

    Видеоразбор задания смотрите ниже:



    10_16: Разбор 10 задания (К. Поляков, задание 80):

    Все четырёхбуквенные слова, составленные из букв В, Е, Г, А, Н записаны в алфавитном порядке и пронумерованы, начиная с 1. Начало списка выглядит так:

    1. АААА
    2. АААВ
    3. АААГ
    4. АААЕ
    5. АААН
    6. ААВА
    …
    

    Под каким номером в списке идёт первое слово, в котором нет буквы А?


    ✍ Решение:

    • Пронумерованный список начинается со всех букв А. Представим, что А — 0, В — 1, Г — 2, Е — 3, Н — 4. Получим следующий список:
    • 1. 0000
      2. 0001
      3. 0002
      4. 0003
      5. 0004
      6. 0010
      
    • Такой список представляет из себя увеличивающиеся числа 5-й системы счисления.
    • Так как букве А соответствует 0, то первое (самое младшее) четырехзначное число без нуля — это 1111.
    • Чтобы вычислить под каким номером стоит данное число, переведем его в 10-ю систему и прибавим к результату единицу (так как порядковые номера в списке на единицу больше самих чисел):
    • 11115 = 1 * 53 + 1 * 52 + 1 * 51 + 1 * 50 = 156
      156 + 1 = 157
      

    Результат: 157

    Видеорешение задания:


    Вероятность событий


    10_17: Разбор 10 задания ЕГЭ по информатике (сайт «Решу ЕГЭ», задание № 4795):

    За чет­верть Ва­си­лий Пуп­кин по­лу­чил 20 оценок. Со­об­ще­ние о том, что он вчера по­лу­чил четверку, несет 2 бита информации.

    Сколь­ко чет­ве­рок по­лу­чил Ва­си­лий за четверть?


    ✍ Решение:

    • Для решения данного задания необходимо вспомнить две формулы:
    • 1. Формула Шеннона:

      x = log2(1/p)
      x - количество информации в сообщении о событии
      p - ве­ро­ят­ность со­бы­тия

      2. Формула вероятности случайного события:

      p(A) = m/n
      m - число случаев, способствующих событию А
      n - общее число равновозможных случаев
    • Подставим в первую формулу известное значение — вероятность того, что Ва­си­лий по­лу­чил чет­вер­ку:
    • 2 = log2(1/p);
          => 
      1/p = 4; 
          =>
      p = 1/4
    • Затем подставим известное по условию значение в формулу вероятности случайного события:
    • p = ?/20
    • Поскольку p мы уже нашли, подставим найденное значение и найдем искомое число — количество четверок за четверть:
    • 1/4 = ?/20
      
      ? = 1/4 * 20 = 5

    Результат: 5

    Видеоразбор задания:


    Поделитесь уроком с коллегами и друзьями:
    11 комментариев

      Александр

      10 задания ЕГЭ по информатике (К. Поляков, задание 52): можно решить другим способом: найти все возможные слова и исключить из него слово которое не может составить по условию. слово исключение одно когда все четыре буквы А, поэтому отномаем от 625-1 = 624

      admin

      да) совершенно верно. На такие задания практически всегда найдется несколько вариантов решений

      Роман

      У Вас ошибка в решении тренировочного варианта №3 2018 (от 01.10.2018).
      По условию задачи «в комбинации не может быть одинаковых букв». В большинстве пунктов решения идет просто перемножение исходного числа гласных и согласных. Поэтому вы учитываете лишние комбинации с одинаковыми буквами.
      Верным будет следующее решение:
      1. С гласной:
      (2 * 3 * 2) + (2 * 3 * 1) = 18
      2. С согласной:
      (3 * 2 * 1) + (3 * 2 * 2) + (3 * 2 * 2) = 30
      Итого: 18 + 30 = 48
      Результат: 48

        admin

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

          Татьяна

          Получается, что гласные — это не буквы. В условии отдельно сказано про подряд идущих гласных и не сказано, что они одинаковые. Условие не точно сформулировано.

            admin

            Да, согласна, немного некорректно сформулировано. Это тренировочный… там часто возникают «ляпы»

      Николай

      У вас везде написано, что n!=0*1*2*…*n, что является бредом, потому что 0 умножить на любое число равно 0. Исправьте, пожалуйста!

        admin

        да, конечно, спасибо, исправлено

      Yakov

      1 Килобайт — 1000 байт, а не 1024
      В ЕГЭ Кб — это Кибибайты.
      1Киби байт — 1024 байта.
      Также соответственно и с Мб, Гб….

        admin

        1 Килобайт — 1024 байт, и это пошло от специфики хранения информации в оперативной памяти: адреса ячеек оперативной памяти кратны степеням 2, и производителям удобно делать количество ячеек оперативной памяти кратным двум. Но иногда допускается упрощение, до 1000 байт, согласно международной системе единиц СИ

      surname

      в самом первом видеоролике сказано от 1 до 6 ,и выбирают все 6 цифры , хотя должны быть цифры 2,3,4,5 ,так как от1 до 6

    Добавить комментарий

    Ваш e-mail не будет опубликован. Обязательные поля помечены *

    *
    *


    Вставить формулу как
    Блок
    Строка
    Дополнительные настройки
    Цвет формулы
    Цвет текста
    #333333
    Используйте LaTeX для набора формулы
    Предпросмотр
    \({}\)
    Формула не набрана
    Вставить