8 задание егэ информатика itertools

Егэ по информатике 2021. как можно решить задание 8 тип заданий со списком слов на языке python группа вк https://vk.com/ogeegeinformatika

ЕГЭ по информатике 2021. Как можно решить задание 8 (тип заданий со списком слов) на языке Python

Группа ВК
https://vk.com/oge_ege_informatika

Если у вас есть желание поддержать канал, можете это сделать тут
https://donate.stream/devinf

Полезные ресурсы
http://kpolyakov.spb.ru/school/ege.htm

Дистанционные курсы автора роликов
https://devinf.ru
Репозиторий с программами
https://github.com/Grunger/EGE

Видео ЕГЭ по информатике. Функция product модуля itertools в задании 8 канала /dev/inf

Показать

Учитель информатики высшей
категории Жевтило Ирина Аскольдовна

МБОУ «Лицей «Дубна»

Использование
библиотеки itertools при решении задач ЕГЭ по информатике

В встроенном в Python модуле itertools существует
ряд комбинаторных функций. Рассмотрим некоторые из них:

· product() –
прямое произведение одного или нескольких итераторов.

· permutations() –
перестановки и размещения элементов множества.

Данная библиотека позволяет
решать задачи с комбинаторикой, упрощая программу решения.

Вызов модуля itertools:

from itertools import *

Данный модуль можно
использовать для решения задач №8 ЕГЭ по информатике.

Примеры заданий и способы
использования данного модуля.

Пример 1. МАРИНА из букв своего имени составляет слова перестановкой
исходных букв. Сколько различных слов может составить МАРИНА, если первая буква
не может быть гласной?

Аналитический способ решения

Общее количество слов с
учетом, что в слове две буквы «А» (перестановка этих букв не дает нового слова)

Вычтем количество слов,
начинающихся с гласной с учетом 2 букв «А»:

Позиция в слове

*

*

*

*

*

*

Количество букв

3 (МРН)

5

4

3

2

1

Получаем =180 слов

Итого: 360 – 180 = 180

Программа для решения данной
задачи:

from itertools import *

a=’МАРИНА

k=0

for i in set(permutations(a)):

    s=».join(i)

    if s[0] not in ‘АИ‘:

        k+=1

print(k)

В программе
используем

1)    функцию: 
permutations(a), т.к. слова составляются
перестановкой букв;

2)   
используем множества (set), чтобы слова не повторялись;

3)    в условии проверяем отсутствие гласных  в начале слова.

Пример 2. Используем функцию product

Миша составляет
5-буквенные коды из букв К, А, Л, Ь, К, А. Каждая допустимая гласная буква
может входить в код не более одного раза. Сколько кодов может составить Миша?

Аналитический способ решения

Количество слов без «А»

3*3*3*3*3= 35 =243

Количество слов с одной  «А»

5 вариантов *3*3*3*3 = 405

Итого: 243 + 405 = 648

Программа для решения данной
задачи:

from itertools import*

a=’КАЛЬ’

k=0

for i in product(a, repeat=5):

    s=».join(i)

    if s.count(‘А’)<=1 :

        k+=1                               

print (k)

В программе
используем

1)    функцию
product (a, repeat=5):
, т.к. буквы в слове могут повторяться;

2)    в условии проверяем количество гласных  не более 1.

Сегодня на повестке дня 8 задание из ЕГЭ по информатике 2021. Данный тип заданий включает в себя нахождение количества вариантов, элементы комбинаторики и другие математические понятия.

Перейдём к практике решения задач задания 8 ЕГЭ по информатике 2021.

Задача (Классика)

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

1. АААА
2. АААЕ
3. АААИ
4. АААО
5. ААЕА

Запишите слово, стоящее на 248-м месте от начала списка.

Решение:

Обозначим условно А0, Е1, И2, О3.

Важно: Нужно буквам присваивать цифры именно в том порядке, в котором они идут в самом правом столбце, потому что буквы могут дать в «перепутанном порядке» (например Е, А, И, О), и тогда ничего не получится.

ЕГЭ по информатике - задание 8 (Правильное кодирование букв)

Теперь запишем список с помощью цифр.

1. 0000
2. 0001
3. 0002
4. 0003
5. 0010

Получился обычный счёт в четверичной системе!! (всего используются 4 цифры: 0, 1, 2, 3). А слева нумерация показывает соответствие нашей десятичной системе. Но все числа десятичной системы в этой таблице соответствия сдвинуты на 1, ведь мы должны были начать с нуля.

Нас просят записать слово стоящее на 248, т.е. если была обычная таблица соответствия чисел десятичной системы и четверичной системы, слово стоящее на 248 месте, находилось бы на 247 (248 — 1) месте. Значит, наше искомое четверичное число соответствует 247 в десятичной системе.

Переведём число 247 в четверичную систему!

ЕГЭ по информатике - задание 8 (перевод числа из десятичной системы в четверичную)

Получилось число 33134 в четверичной системе. Сделаем обратное декодирование в буквы. Таким образом, ответ будет ООЕО.

Ответы: ООЕО

Ещё одна похожая задача 8 задания из примерных вариантов ЕГЭ по информатике, но другой вариации.

Задача (Классика, Другая вариация)

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

1. ААААА
2. ААААК
3. ААААР
4. ААААУ
5. АААКА
……
Укажите номер слова УКАРА

Решение:

Закодируем буквы цифрами: А0, К1, Р2, У3. Здесь как раз буквы даны не в том порядке, как они идут в самом правом столбце. Но мы должны кодировать именно в том порядке, как буквы идут в самом правом столбце.

ЕГЭ по информатике - задание 8 (кодирование букв цифрами)

У нас получилось четыре цифры! Значит снова можно слова превратить в таблицу соответствия между десятичной системой и четверичной системой. Но десятичная система смещена на 1 позицию.

1. 00000
2. 00001
3. 00002
4. 00003
5. 00010
……

Выписываем данное нам слово и посмотрим, какое число в четверичной системе было бы, если бы у нас были в место слов числа в четверичной системе!

ЕГЭ по информатике - задание 8 (кодируем слово цифрами)

Получили число в четверичной системе 310204. Узнаем, какое число в десятичной системе соответствовало этому числу, если бы была обычная таблица соответствия. Для этого переведём число 310204 из четверичной системы в десятичную. Перевод делаем по аналогии перевода из двоичной системы в десятичную.

ЕГЭ по информатике - задание 8 (Перевод из четверичной в десятичную систему)

Но помним, что у нас нумерация идёт на 1 быстрее, нежели мы бы поставили десятичные числа, как в таблице соответствия, потому что нумерация начинается не с нуля, а с 1. Поэтому к числу 840 нужно прибавить 1, и в ответе будет 841

Ответ: 841

Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)

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

1. ИИИИ
2. ИИИК
3. ИИИН
4. ИИИО
5. ИИИТ
6. ИИКИ

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

Решение:

Закодируем буквы цифрами.

ЕГЭ по информатике - задание 8 (кодируем буквы цифрами от 0 до 4)

Получилось 5 цифр ( 0, 1, 2, 3, 4 ), значит, будем работать в пятеричной системе.

Нужно найти номер первого слова, которое начинается с буквы О. Если говорить на языке пятеричных чисел, то нужно найти номер числа 30005. Мы «забиваем нулями», чтобы число было четырёхразрядное, т.к. слова 4-х буквенные. Именно нулями, потому что нужно именно первое слово найти.

Теперь, как в предыдущей задаче, переведём число 30005 из пятеричной системы в десятичную.

0 * 5 0 + 0 * 5 1 + 0 * 5 2 +
3 * 5 3 = 375 (в десят. системе)

Но опять же должны прибавить 1 к числу 375, т.к. нумерация отличается от десятичных чисел на 1 в большую сторону.

Ответ: 376

Задача (Досрочная волна 2020 ЕГЭ по информатике, вариант 1)

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

Решение:

Для начала решим вводную подзадачу.

Пусть у нас есть те же буквы В, О, Л, К, каждая из букв может встречаться в слове любое количество раз или
не встречаться совсем. Сколько можно составить 5-буквенных слов ?

Т.е буквы могут повторяться!

Например

ЕГЭ по информатике - задание 8 (пятизначное число, перебор вариантов)

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

Рассмотрим перебор трёхразрядных чисел. Вместо 5 букв теперь можно использовать 10 цифр ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ). Цифры так же могут повторяться. Сколько получится вариантов ?

ЕГЭ по информатике - задание 8 (трёхзначное число, перебор вариантов)

Выведем общую формулу для количества вариантов, когда символы могут повторяться!

ЕГЭ по информатике - задание 8 (Общая формула для количества вариантов)

Для трёхразрядных чисел от 000 до 999:

N = 103 = 1000 вариантов.

Вернёмся к пятибуквенным словам и нашей подзадаче. Здесь количество букв (разрядов) в слове равно 5, количество допустимых символов равно 4 ( В, О, Л, К ).

N = 45 = 1024 вариантов.

Вернёмся к изначальной задаче. Сначала найдём количество вариантов, когда буква В находится в самой левой ячейке!

ЕГЭ по информатике - задание 8 (Буква В встречается один раз)

Применим формулу! Здесь слово сократилось до четырёхразрядного. А количество букв для использования 3 (О, Л, К).

N = 34 = 81 комбинация.

Но буква В так же может стоять во второй ячейке слева. Этот случай тоже даст 81 других комбинаций. Буква В может стоять в каждой из 5-ти ячеек, и везде будет получатся 81 комбинация.

Таким образом, окончательный ответ будет:

N = 81 * 5 = 405 различных вариантов.

Ответ: 405

Разобравшись с этой задачей, больше половины тренировочных задач десятого задания из различных книг и сайтов по подготовке к ЕГЭ по информатике будут решаться, как по маслу!

Задача(Закрепление формулы)

Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите {У, Ч, Е, Н, И, К}. Сколько существует таких последовательностей, которые начинаются с буквы У и заканчиваются буквой К?

Решение:

ЕГЭ по информатике - задание 8 (количество последовательностей)

Применим главную формулу 8 задания из ЕГЭ по информатике

N = mi = 63 = 216

Здесь буквы могут изменяться на 3 ячейках! Значит, в формуле i=3. Количество допустимых символов, которые можно поставить в каждую ячейку равно 6. Значит, в формуле m=6.

В ответе будет 216.

Примечание: Здесь можно использовать все буквы в каждой ячейке, включая У и К. В некоторых задачах их уже использовать нельзя, т.е. сказано, что буквы У и К используются один раз в слове. Тогда в формуле m, будет на 2 единицы меньше. Нужно внимательно читать задачу!

Ответ: 216

Задача (Демонстрационный вариант ЕГЭ по информатике, 2019)

Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А,
причём в каждом слове есть ровно одна гласная буква и она встречается
ровно 1 раз. Каждая из допустимых согласных букв может встречаться
в слове любое количество раз или не встречаться совсем. Словом считается
любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Вася?

Решение:

Рассмотрим количество вариантов, когда гласная И стоит в первом месте!

ЕГЭ по информатике - задание 8 (количество слов)

Подсчитаем количество слов с помощью супер-формулы

N = mi = 24 = 16

Длина изменяющихся ячеек равна 4, а количество допустимых букв равно 2.

Но буква И может стоять не только на первом месте. Она так же может стоять и на 2, и на 3, и на 4, и на 5 месте. Каждый такое случай добавляет столько же новых слов.

Значит, при использовании только буквы И будет количество слов 16 * 5 = 80. Ещё столько же слов добавится, если в словах вместо буквы И будет использоваться буква А. Поэтому окончательный ответ будет 80 * 2 = 160

Ответ: 160

Отработаем главную формулу 8 задания из ЕГЭ по информатике.

Задача (Развиваем понимание формулы!)

Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение:

Рассмотрим, какие варианты могут быть, если у нас на первом месте стоит согласная, а на последнем месте гласная

ЕГЭ по информатике - задание 8 (количество вариантов первая согласная, последняя гласная)

Получилось 4 разных случая. Подсчитаем, сколько слов можно составить при одном случае.

N = mi = 43 = 64

Длина изменяющихся ячеек равна 3, а количество возможных букв 4.

Но т.к. таких случая у нас четыре, то ответ будет 4 * 64 = 256

Ответ: 256

Рассмотрим важнейший «метод умножения» при решении 8 задания из ЕГЭ по информатике.

Задача (Другой метод решения!!)

Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз , при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?

Решение:

Эта задача отличается от уже разобранных тем, что каждую букву можно использовать один раз. В этой задаче удобнее воспользоваться немного другим методом решения! «Методом умножения»!

Решим вводную подзадачу (без дополнительных ограничений).

Сколькими способами можно составить 6-x буквенное слово из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз .

ЕГЭ по информатике - задание 8 (метод умножения)

Чтобы найти возможные варианты, перемножаем для каждой ячейки количество букв из которых у нас есть выбор!

N = 6 * 5 * 4 * 3 * 2 * 1 = 720

Вернёмся к изначальной задаче!

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

ЕГЭ по информатике - задание 8 (метод умножения комбинаторика)
N = 5 * 5 * 4 * 3 * 2 * 1 = 600

В формуле стоят почти все те же самые числа, как и в вводном примере, только первый множитель не 6, а 5. Это произошло из-за того, что у нас в задаче слово не может начинаться на букву Й. Значит, выбор на первую позицию будет не из 6 букв, а из 5.

Но в 600 комбинаций входят и те случаи, когда в слове присутствует сочетание АЕ. Теперь найдём сколько таких слов, где присутствует сочетание АЕ

Узнаем количество вариантов в каждом таком случае.

ЕГЭ по информатике - задание 8 (метод умножения комбинаторика 1)

N1 = 4 * 3 * 2 * 1 = 24

ЕГЭ по информатике - задание 8 (метод умножения комбинаторика 2)

На первом месте мы не можем использовать букву Й, поэтому мы на первом месте выбираем из 3 букв.

N2 = 3 * 3 * 2 * 1 = 18

ЕГЭ по информатике - задание 8 (метод умножения комбинаторика 3)

Аналогично предыдущему случаю.

N3 = 3 * 3 * 2 * 1 = 18

ЕГЭ по информатике - задание 8 (метод умножения комбинаторика 4)

N4 = 3 * 3 * 2 * 1 = 18

ЕГЭ по информатике - задание 10 (метод умножения комбинаторика 5)
N5 = 3 * 3 * 2 * 1 = 18

Всего слов с сочетанием АЕ будет

24 + 18 + 18 + 18 + 18 = 96

Значит, всего слов, которые удовлетворяют условию задаче будет

N = 60096 = 504

Примечание: Метод умножения можно было использовать и в задачах, которые мы рассмотрели ранее. Например, в задаче «Закрепление формулы» в первой свободной ячейке выбираем из 6 букв, во второй свободной ячейке тоже из 6 букв, и в третий свободной ячейке тоже можно использовать 6 букв. Значит, по методу умножения получается N = 6 * 6 * 6 = 63 = 216

Ответ: 504

Задача (Закрепления «метода умножения»)

Полина составляет 6-буквенные коды из букв П, О, Л, И, Н, А. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Полина?

Решение:

ЕГЭ по информатике - задание 8 (закрепление метода умножения комбинаторика)

Опять сказано, что каждая буква используется 1 раз, следовательно, нужно применять «метод умножения».

На первое место можно выбрать из 6 букв, предположим, мы выберем согласную. Тогда на второе место нужно выбирать из 3 гласных. Потом опять должна идти согласная, но их у нас осталось только 2. Далее, на следующее место выбираем из 2 гласных букв. И на предпоследнее место выбирается 1 согласная, а на последнее место остаётся 1 гласная.

Т.к. количество гласных букв и согласных одинаковое, и равно трём, то если мы бы начали делать «метод умножения» с гласной буквы, количество вариантов бы не поменялось.

N = 6 * 3 * 2 * 2 * 1 * 1 = 72

Ответ: 72

Задача (Азбука Морзе)

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее трёх и не более четырёх сигналов (точек и тире) ?

Решение:

Зная формулу, без проблем решим данную примерную задачу из ЕГЭ по информатике.

У нас есть 2 символа, которые можно использовать: точка и тире. Фраза, что сообщение может иметь «не менее трёх и не более четырёх сигналов», означает, что сообщения могут быть длиною 3 символа и длиною 4 символа.

Подсчитаем общее количество вариантов.

N = 23 + 24 = 8 + 16 = 24 комбинаций.

Значит, для 24 различных символов (цифр, букв, знаков пунктуации и т.д.) мы найдём различные комбинации, чтобы их закодировать

Ответ: 24

Задача (Обратная предыдущей)

Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?

Решение:

Нам нужно закодировать 300 различных вариантов! Имеются 4 различных лампочки! (Они имеют смысл, как количество допустимых символов!) На этот раз нужно узнать количество лампочек (количество разрядов, «длину слова»). Применяем формулу.

N = 4x = 300

Не найдётся такое целое x, чтобы равенство стало верным. Поэтому берём целое минимальное x такое, чтобы 4x больше 300.

45 = 1024

Пять лампочек на табло хватит, чтобы закодировать 300 сигналов, но, к сожалению, много комбинаций просто не пригодится!

Ответ: 5

Задача (Важная!)

Нужно выбрать в подарок 3 книги из 5. Сколькими способами можно выбрать ?

Решение:

На рисунке показано две комбинации, как можно выбрать в подарок 3 книги из 5.

ЕГЭ по информатике - задание 8 (Сочетания, комбинаторика, пример)

Данную задачку нужно решать используя формулу сочетаний из раздела комбинаторика.

ЕГЭ по информатике - задание 8 (Сочетания, комбинаторика, формула)

n — количество книг, из которых мы выбираем подарок, m — количество книг, которое мы хотим выбрать, C — количество вариантов (способов).

Восклицательный знак — это факториал!

Факториалом числа «n» (условное обозначение n!- читается как «эн» — факториал) называется произведение чисел от 1 до «n»

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

ЕГЭ по информатике - задание 8 (Вычисляем сочетания, комбинаторика)

Ответ: 10

Следующая задача часто встречается в книгах по подготовке к ЕГЭ по информатике.

Задача (Главная формула + сочетания)

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

Решение:

В начале нужно посчитать, сколькими способами на 5-ти ячейках можно расположить 3 единицы!

ЕГЭ по информатике - задание 8 (кодовый замок)

Обратите внимание, как будто мы выбираем 3 книги в подарок из 5 возможных! Значит, опять применяем формулу сочетаний из комбинаторики. Мы вычисляли уже её точно с такими же числами в прошлой задаче, количество вариантов равно 10.

Подсчитаем, сколько вариантов кодового замка можно составить при одном определённом расположении трёх единиц.

ЕГЭ по информатике - задание 8 (количество вариантов для одного случая)

Применим формулу, есть две ячейки, в которых изменяются цифры, а в каждой ячейке может быть одна из 4 цифр.

N = mi = 42 = 16

Т.к. различных вариантов, как расположить единицы на 5 ячейках равно 10, то ответ будет 16 * 10 = 160

Ответ: 160

Ещё одна задача из примерных вариантов по подготовке к ЕГЭ по информатике.

Задача (Таблица соревнований)

Для записи результатов соревнований используется таблица, в которой для каждой из 20-ти команд по каждому из 10-ти видов состязаний записано 1, 2 или 3 (если команда заняла соответствующее место в этом состязании) или прочерк (если не заняла призовое место или не участвовала). Какое количество информации (бит) содержит таблица ?

Решение:

Есть таблица с 20 командами и для каждой команды есть результат по 10-ти видам состязаний.

1 команда 2 команда 3 команда 20 команда
1 дисциплина 1 1 3
2 дисциплина 2 1 2
10 дисциплина 1 1 2

В каждой ячейке может быть 4 различных значения ( 1, 2, 3, — ). Нужно узнать, сколько бит занимает одна ячейка таблицы. Один бит может быть либо единицей, либо нулём.

ЕГЭ по информатике - задание 8 (Таблица результатов соревнований)

Сделав рисунок, задача обрела привычные очертания.

Как будто мы решаем задачу с перебором слов. Но здесь длина слова неизвестна, а количество вариантов, которое должно получится уже дано и равно 4 (четырём). Применим главную формулу из 10 задания из ЕГЭ по информатике.

N = mi = 2i = 4

i=2 бита (длина равна «2 буквам», если воспринимать задачу, как со словами.)

Одна ячейка таблицы весит 2 бита. Найдём количество ячеек во всей таблице соревнований.

Всего ячеек = 20 * 10 = 200

Тогда вся таблица будет весит:

V = 2 бита * 200 = 400 бит.

Ответ: 400

Формула Шеннона

Задача (Формула Шеннона)

В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?

Решение:

Данную задачу нужно решать по формуле Шеннона

ЕГЭ по информатике - задание 8 (Формула Шеннона)

Найдём вероятность p того, что вытащили чёрный шарик.

p = (количество чёрных шаров) / (количество всех шаров) = 8 / (24 + 8) = 8 / 32 = 1 /4

p = 1 / 4

Применим формулу Шеннона.

x = log2(4)
2x = 4

x = 2 бита

Ответ: 2

Канал видеоролика: ГИА по информатике

ЕГЭ по информатике. Функция product модуля itertools в задании 8

Смотреть видео:

#информатика #егэинформатика #икт #экзамены #егэ_2020 #мгту #школьникам #помощь_студентам #подготовкакэкзаменам

Свежая информация для ЕГЭ и ОГЭ по Информатике (листай):

С этим видео ученики смотрят следующие ролики:

Массивы в 27 задании | ЕГЭ по информатике 2020

Массивы в 27 задании | ЕГЭ по информатике 2020

Evgenij Jobs

Стрим #44. ЕГЭ по информатике 2019, 11 класс.

Стрим #44. ЕГЭ по информатике 2019, 11 класс.

ЕГЭ по информатике

Стрим #45. ЕГЭ по информатике 2019, 11 класс. Задача 27

Стрим #45. ЕГЭ по информатике 2019, 11 класс. Задача 27

ЕГЭ по информатике

Стрим #46. ЕГЭ по информатике 2019, 11 класс.

Стрим #46. ЕГЭ по информатике 2019, 11 класс.

ЕГЭ по информатике

Облегчи жизнь другим ученикам — поделись! (плюс тебе в карму):

08.06.2021

  • Комментарии

RSS

Нет комментариев. Ваш будет первым!

Загрузка…

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

8-е задание: «Измерение количества информации»

Уровень сложности

— базовый,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 4 минуты.
  
Проверяемые элементы содержания: Знание о методах измерения количества информации

До ЕГЭ 2021 года — это было задание № 10 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«При использовании способа решения со системой счисления с основанием N следует помнить, что слова в списке нумеруются с единицы, поэтому числу 0 будет соответствовать первое слово»

ФГБНУ «Федеральный институт педагогических измерений»

Объяснение темы

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

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

  • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
  • 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 символа:

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

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

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

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

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

    Решение:

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

    26

    *

    26

    *

    26

    = 17576

    Ответ: 17576

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

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

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

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

  • I – количество информации в битах
  • 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 — длина сообщения
  • Решение заданий 8 ЕГЭ по информатике

    Плейлист видеоразборов задания на YouTube: 8 задание егэ информатика itertools
    Задание демонстрационного варианта 2022 года ФИПИ


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

    8_1: ЕГЭ по информатике 2017 задание 8 (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
      
    ✎ Решение с использованием программирования:

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    begin
      var n := 0;
      var str := '123456';
      foreach var s1 in str do
        foreach var s2 in str do
          foreach var s3 in str do
            foreach var s4 in str do
              foreach var s5 in str do
              begin
                if (s1 + s2 + s3 + s4 + s5).CountOf('1') = 1 then
                  n += 1;
              end;
      print(n)
    end.
    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    
    ##
    var d:='123456'.Cartesian(5) 
    .where(w->w.countOf('1')=1)// кол-во '1' в слове
    .count.print

    Cartesian(5) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 5-знаковых слов из заданных символов

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    
    n=0
    str='123456'
    for s1 in str:
      for s2 in str:
        for s3 in str:
          for s4 in str:
            for s5 in str:
              if (s1+s2+s3+s4+s5).count('1')==1:
                n+=1
    print(n)
    С++:

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_2: ЕГЭ по информатике 2017 задание 8 (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
      
    ✎ Решение с использованием программирования:

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    
    begin
      var n := 0;
      var str := 'AB123';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              for var s5 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
                if (res.CountOf('A') = 1) and (res.CountOf('B') = 0) 
                or (res.CountOf('B') = 1) and (res.CountOf('A') = 0) then
                  n += 1;
              end;
      print(n)
    end.
    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    
    ##
    var d:='АВ123'.Cartesian(5) 
    .where(w->w.count(letter -> letter in 'АВ')=1)// кол-во букв в слове
    .count.print

    Cartesian(5) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 5-знаковых слов из заданных символов

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    
    n=0
    str='AB123'
    for s1 in str:
      for s2 in str:
        for s3 in str:
          for s4 in str:
            for s5 in str:
              if ((s1+s2+s3+s4+s5).count('A')==1 and (s1+s2+s3+s4+s5).count('B')==0) 
              or ((s1+s2+s3+s4+s5).count('B')==1 and (s1+s2+s3+s4+s5).count('A')==0):
                n+=1
    print(n)
    С++:

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_3: Разбор 8 (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

      
    ✎ Решение с использованием программирования:

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    
    begin
      var n := 0;
      var str := 'АБВГДЕ';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4];
                if (res[1]='Г') and (res[2]<>'Г') and (res[3]<>'Г') and (res[4]<>'Г')
                or (res[1]<>'Г') and (res[2]<>'Г') and (res[3]<>'Г') and (res[4]='Г') then
                  n += 1;
              end;
      print(n)
    end.
    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    
    ##
    var d:='АБВГДЕ'.Cartesian(4)
    .where(w->(w.countOf('Г')=1)and(w[1]<>'Г')and(w[2]<>'Г')and(w[2]<>'Г'))
    .count.print

    Cartesian(4) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 4-знаковых слов из заданных символов

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    
    n=0
    str='АБВГДЕ'
    for s1 in str:
      for s2 in str:
        for s3 in str:
          for s4 in str:
            if (s1 =='Г') and (s2!='Г') and (s3!='Г') and (s4!='Г') 
            or (s1 !='Г') and (s2!='Г') and (s3!='Г') and (s4=='Г'):
                n+=1
    print(n)
    С++:

    Видеоразбор данного задания (теоретический способ):

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_4: ЕГЭ по информатике 2017 задание 8 (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
      
    ✎ Решение с использованием программирования:

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    
    begin
      var n := 0;
      var str := 'xyz';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              for var s5 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
                if res.countOf('x') = 2 then // или if res.Count(y -> y = 'x') = 2 then
                  n += 1;
              end;
      print(n)
    end.
    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    
    ##
    var d:='XYZ'.Cartesian(5)
    .where(w->w.countOf('X')=2)
    .count.print

    Cartesian(5) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 5-знаковых слов из заданных символов

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    
    n=0
    str='xyz'
    for s1 in str:
      for s2 in str:
        for s3 in str:
          for s4 in str:
            for s5 in str:
              if (s1+s2+s3+s4+s5).count('x') == 2:
                n+=1
    print(n)
    С++:

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_5: Разбор 8 (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
    

    ✎ Решение с использованием программирования:

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    
    begin
      var n := 0;
      var str := 'ОСЕНЬ';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              for var s5 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
                if ((res[1] = 'С') or (res[1] = 'Н')) and ((res[5] = 'О') or (res[5] = 'Е')) then
                  n += 1;
              end;
      print(n)
    end.
    PascalABC.net (использование LINQ, быстрое решение):

    1
    
    'ОСЕНЬ'.Cartesian(5).Where(w->w[0] in 'СН').Where(w->w[4] in 'ОЕ').Count.Print

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    
    str = 'ОСЕНЬ'
    n = 0
    for s1 in str:
        for s2 in str: 
            for s3 in str:
                for s4 in str:
                    for s5 in str:
                        res = s1 + s2 + s3 + s4
                        if (s1 == 'С' or s1 == 'Н') and (s5 == 'О' or s5 == 'Е'):
                            n += 1
    print(n)
    С++:

    Результат: 500

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_6: Разбор 8 (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
      
    ✎ Решение с использованием программирования:

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    begin
      var n := 0;
      var str := 'ЛЕТО';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4];
                if res.countOf('Е') >= 1 then // или if res.Count(y -> y = 'Е') >= 1 then
                  n += 1;
              end;
      print(n)
    end.
    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    
    ##
    var d:='лето'.Cartesian(4).where(w->w.countOf('е')>=1).count.print

    Cartesian(4) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 4-знаковых слов из заданных символов

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    
    n=0
    str='ЛЕТО'
    for s1 in str:
      for s2 in str:
        for s3 in str:
          for s4 in str:
              if (s1+s2+s3+s4).count('Е') >= 1:
                n+=1
    print(n)
    С++:

    Теоретическое решение задания 8 смотрите в видеоуроке:

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_7: Разбор 8 задания ЕГЭ по информатике (К. Поляков, задание 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

    ✎ Решение с использованием программирования:

    PascalABC.net:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    begin
      var n := 0;
      var str := 'КАТЕР';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4];
                if res.CountOf('Р') >= 2 then
                  n += 1;
              end;
      print(n)
    end.
    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    
    n=0
    str='КАТЕР'
    for s1 in str:
      for s2 in str:
        for s3 in str:
          for s4 in str:
              if (s1+s2+s3+s4).count('Р') >= 2:
                n+=1
    print(n)
    С++:

    Результат: 113

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_8: Разбор 8 задания ЕГЭ по информатике (К. Поляков, задание 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

    ✎ Решение с использованием программирования:

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    
    begin
      var n := 0;
      var str := 'АБВГ';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              for var s5 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s4];
                if (res[1]<>'Г') and (res[2]<>'Г')and (res[3]<>'Г') and (res[4]<>'Г') then
                  n += 1;
              end;
      print(n)
    end.
    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    
    ##
    var d:='абвг'.Cartesian(5)
    .where(w->(w.countOf('г')<=1)and(w[0]<>'г')and(w[1]<>'г')and(w[2]<>'г')
         and(w[3]<>'г')).count.print

    Cartesian(5) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 5-знаковых слов из заданных символов

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    С++:

    Результат: 324


    8_9: Разбор 8 задания ЕГЭ по информатике (К. Поляков, задание 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

    ✎ Решение с использованием программирования:

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    begin
      var n := 0;
      var str := 'КОМАР';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4];
                if res.CountOf('А') <=3 then
                  n += 1;
              end;
      print(n)
    end.
    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    
    ##
    var d:='комар'.Cartesian(4)
    .where(w->w.countOf('а')<=3).count.print

    Cartesian(4) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 4-знаковых слов из заданных символов

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    
    str = 'КОМАР'
    n = 0
    for s1 in str:
        for s2 in str: 
            for s3 in str:
                for s4 in str:
                    res = s1 + s2 + s3 + s4
                    if res.count('А')<=3:
                        n += 1
    print(n)
    С++:

    Результат: 624

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_10: Разбор 8 задания ЕГЭ по информатике (К. Поляков, задание 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

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_11: Разбор 8 задания Тренировочный вариант №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
    

    ✎ Решение с использованием программирования:

    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    5
    6
    
    ### 
    'среда'.cart(3)// 
     .Select(w -> w.JoinToString('')) // собираем в строку;
     .where(w->w.Pairwise.All((a,b) -> a+b not in 'еае'))
     .where(w->w.Pairwise.All((a,b) -> a<>b))
     .count.print
    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    
    begin
      var n := 0;
      var str := 'СРЕДА';
      var glas := 'ЕА';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3];
            // условие для подряд идущих гласных
            if not ((res[1] in glas) and (res[2] in glas) or
               (res[2] in glas) and (res[3] in glas)) then
            // условие для подряд идущих одинаковых букв
              if not ((res[1] = res[2]) or (res[2] = res[3])) then
                n += 1;
          end;
      print(n)
    end.
    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    
    str = 'СРЕДА'
    glas = 'ЕА'
    n = 0
    for s1 in str:
        for s2 in str: 
            for s3 in str:
                res = s1 + s2 + s3 
                if not (s1 in glas and s2 in glas or
               s2 in glas and s3 in glas) :
                    if not (s1 == s2 or s2 == s3) :
                        n += 1
    print(n)
    С++:

    Результат: 66

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

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

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

    ✍ Решение:

      ✎ Решение теоретическое:

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

    Результат: 72


    8_21: Решение 8 задания (К. Поляков, задание 210):

    Ксюша составляет слова, меняя местами буквы в слове МИМИКРИЯ.
    Сколько различных слов, включая исходное, может составить Ксюша?

    ✍ Решение:

      ✎ Решение с использованием программирования:

      PascalABC.net (приближенный к традиционному, долгое решение):

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      
      begin
        var str := 'МИМИКРИЯ';
        var set1: set of string;
        set1 := [];
        for var s1 := 1 to length(str) do
          for var s2 := 1 to length(str) do 
            for var s3 := 1 to length(str) do
              for var s4 := 1 to length(str) do 
                for var s5 := 1 to length(str) do  
                  for var s6 := 1 to length(str) do
                    for var s7 := 1 to length(str) do  
                      for var s8 := 1 to length(str) do 
                      begin
                        var slovo := str[s1] + str[s2] + str[s3] + str[s4] + str[s5] + str[s6] + str[s7] + str[s8];
                        if (slovo.CountOf('М') = 2) and (slovo.CountOf('И') = 3)
                        and (slovo.CountOf('К') = 1)
                        and (slovo.CountOf('Р') = 1)
                        and (slovo.CountOf('Я') = 1) then
                          include(set1, slovo);
                      end;
        print(set1.count);
      end.

      Смысл решения в использовании типа множества (set). При добавлении новых элементов к множеству исключаются повторения.

      PascalABC.net (использование LINQ, быстрое решение):

      1
      2
      3
      4
      5
      
      ### 
       'МИМИКРИЯ'.Permutations // перестановки букв
       .Select(w->w.JoinToString('')) // собираем в строку
       .Distinct  // выбираем уникальные
       .Count.Print

      * LINQ (Language Integrated Query) — язык интегрированных запросов

      Python:

      С++:

      Ответ: 3360

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

    📹 Видеорешение на RuTube здесь (программное решение)


    8_19: Решение 8 задания (К. Поляков, задание 116):

    Петя составляет шестибуквенные слова перестановкой букв слова АДЖИКА. При этом он избегает слов с двумя подряд одинаковыми буквами. Сколько всего различных слов может составить Петя?

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

    ✍ Решение:

      ✎ Решение теоретическое:

    • Посчитаем количество слов без двух подряд одинаковых букв. Будем считать относительно буквы А, которых две в заданном слове АДЖИКА. Буквы не могут повторяться, поэтому их кол-во в каждом варианте будет уменьшается:
    А*А*** = 4*3*2*1 = 24 слова с данным расположением буквы А. 
    А**А** = 4*3*2*1 = 24
    А***А* = 4*3*2*1
    А****А = ...
    *А*А**
    *А**А*
    *А***А
    **А*А*
    **А**А
    ***А*А
    
  • Получили 10 вариантов, и в каждом из них можно составить по 24 слова.
  • Таким образом, получим общее количество слов:
  • 10 * 24 = 240

    ✎ Решение с использованием программирования:

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    
    begin
      var s: set of string;
      s := [];
      var str := 'АДЖИКА';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              for var s5 := 1 to length(str) do
                for var s6 := 1 to length(str) do
                begin
                  var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5] + str[s6];
                  if (res.CountOf('А') = 2) and (res.CountOf('Д') = 1) 
                      and (res.CountOf('Ж') = 1) and (res.CountOf('И') = 1) 
                      and (res.CountOf('К') = 1) then
                         if (res[1] <> res[2]) and (res[2] <> res[3]) and (res[3] <> res[4]) 
                            and (res[4] <> res[5]) and (res[5] <> res[6]) then
                               include(s, res);
                end;
      print(s.count)
    end.

    Смысл решения в использовании типа — множества (set). При добавлении новых элементов к множеству исключаются повторения.

    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    5
    6
    
    ### 
    'аджика'.Permutations
     .Select(w -> w.JoinToString('')) // собираем в строку;
     .distinct // исключаем дубли
     .where(s -> not ('аа' in s)) // исключаем две подряд буквы 'а'
     .count.pr
    Python:

    С++:

    Ответ: 240


    8_20: Разбор 8 задания (К. Поляков, задание 112):

    Маша составляет 7-буквенные коды из букв В, Е, Н, Т, И, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код буква Ь не может стоять на последнем месте и между гласными. Сколько различных кодов может составить Маша?

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

    ✍ Решение:

      ✎ Решение теоретическое:

    • Выполним задание следующим образом: 1. посчитаем общее количество слов, не учитывая никакие ограничения. 2. Затем посчитаем случаи, которые необходимо исключить. 3. Вычтем из результата пункта 1 результат пункта 2.
    • Общее количество независимо от ограничений (учтем, что буквы не должны повторяться):
    7 6 5 4 3 2 1 - количество возможных вариантов букв на семи позициях
    
    ИТОГО:
    7! = 5040 слов
  • Посчитаем варианты, которые необходимо исключить. Их будет несколько:
  • а) буква ь — на последнем месте:
  • 6 5 4 3 2 1 Ь = 6! = 720
  • б) буква ь — между гласными:
  • И Ь Е 4 3 2 1  = 24 варианта
    Так как буквы смещаются по всем позициям, то получим (4 И Ь Е 3 2 1, ...):
    24 * 5 = 120
    Е Ь И 4 3 2 1  = 24 варианта
    24 * 5 = 120
    
  • Посчитаем количество слов, согласно условию задачи:
  • 5040 - 720 - 120 - 120 = 4080

    ✎ Решение с использованием программирования:
    Стоит заметить, что теоретическое решение занимает меньше времени, чем программный способ!

    PascalABC.net (приближенный к традиционному, долгое решение):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    
    begin
      var n := 0;
      var str := 'ВЕНТИЛЬ';
      var glas := 'ЕИ';
      for var s1 := 1 to length(str) do
        for var s2 := 1 to length(str) do
          for var s3 := 1 to length(str) do
            for var s4 := 1 to length(str) do
              for var s5 := 1 to length(str) do
                for var s6 := 1 to length(str) do
                  for var s7 := 1 to length(str) do
                  begin
                    var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5] + str[s6] + str[s7];
                    if (res.CountOf('В') = 1) and (res.CountOf('Е') = 1) 
                        and (res.CountOf('Н') = 1) and (res.CountOf('Т') = 1) 
                        and (res.CountOf('И') = 1) and (res.CountOf('Л') = 1)
                        and (res.CountOf('Ь') = 1) then
                      if not (res[7] = 'Ь') then
                        if not ((res[1] in glas) and (res[3] in glas) and (res[2] = 'Ь') or
                            (res[2] in glas) and (res[4] in glas) and (res[3] = 'Ь') or
                            (res[3] in glas) and (res[5] in glas) and (res[4] = 'Ь') or
                            (res[4] in glas) and (res[6] in glas) and (res[5] = 'Ь') or
                            (res[5] in glas) and (res[7] in glas) and (res[6] = 'Ь')) then
                          n += 1
                  end;
      print(n)
    end.
    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    5
    
    ### 
    'вентиль'.Permutations// здесь можно без distinct, т.к. буквы не повторяются
     .Select(w -> w.JoinToString('')) // собираем в строку
     .where(s -> not ('еьи' in s) and not ('иье' in s) and (s.last <> 'ь'))
    .Count.Print
    Python:

    С++:

    Ответ: 4080


    Сколько существует n-значных чисел, записанных в m-ной системе счисления

    8_18: Объяснение 8 задания экзамена ЕГЭ 2020 г. (со слов учащегося):

    Сколько существует восьмизначных чисел, записанных в восьмеричной системе счисления, в которых все цифры различны и рядом не могут стоять 2 чётные или 2 нечётные цифры?
      
    Типовые задания для тренировки

    ✍ Решение:

      ✎ Решение теоретическое:

    • Выпишем все четные и нечетные цифры, которые могут использоваться в 8-й с.с.:
    четные: 0, 2, 4, 6 - итого 4 цифры
    нечетные: 1, 3, 5, 7 - итого 4 цифры
  • Рассмотрим два случая построения числа по заданию: 1) начиная с четной цифры и 2) начиная с нечетной цифры. Изобразим схематично числа, указывая сверху возможное количество цифр на разряд:
  • 1) с четной цифры:
    3  4  3  3  2  2  1  1 = 3*4*3*3*2*2*1*1 = 432
    ч  н  ч  н  ч  н  ч  н

    Самый старший разряд не может быть равен 0 (поэтому 3 цифры из 4 возможных), так как разряд просто потеряется, и число станет семизначным). Каждый последующий разряд включает на одну цифру меньше, так как по заданию цифры не могут повторяться.

    2) с нечетной цифры:
    4  4  3  3  2  2  1  1 = 4*4*3*3*2*2*1*1 = 576
    н  ч  н  ч  н  ч  н  ч

    Каждый последующий разряд включает на одну цифру меньше, так как по заданию цифры не могут повторяться.

  • Сложим количество вариантов в обеих случаях:
  • 432 + 576 = 1008

    ✎ Решение с использованием программирования:

    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    5
    
    ###
    '01234567'.Permutations // т.к. цифр итак 8 штук
    .where(w->w.First<>'0') // первая цифра не может быть 0
    .where(w->w.Pairwise.All((a,b)-> (a.ToDigit + b.ToDigit).IsOdd)) // проверка пар четных и нечетных
    .count.print

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    С++:

    Ответ: 1008


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

    8_13: ЕГЭ по информатике 2017 задание 8 (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, им соответствуют буквы УУУУО
  • ✎ Решение с использованием программирования:

    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    
    ##
    var d:='АОУ'.Order // сортируем по алфавиту
    .Cartesian(5)
    .Numerate.print

    Смотрим слова и находим по номеру нужное слово:

    … (241,[У,У,У,У,А]) (242,[У,У,У,У,О]) (243,[У,У,У,У,У])

    Cartesian(5) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 5-знаковых слов из заданных символов

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    С++:

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

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_14: 8 задание. Демоверсия ЕГЭ 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.
  • ✎ Решение с использованием программирования:

    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    5
    6
    
    ###
    var d:='декор'.Order // сортируем по алфавиту
    .Cartesian(4) // d - массива из массивов символов 
    .Numerate // нумерация
    .where((i,w)->w[0] = 'к') // рассматриваем и номер и слово
    .first[0].print // выводим именно номер

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    С++:

    Результат: 251

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


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

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

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

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

    ✍ Решение:

    Результат: 65

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)


    8_16: Разбор 8 задания (К. Поляков, задание 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
    

    ✎ Решение с использованием программирования:

    PascalABC.net (использование LINQ, быстрое решение):

    1
    2
    3
    4
    5
    6
    7
    
    ###
    var d:='веган'.Order // сортируем по алфавиту
    .Cartesian(4) // d - массива из массивов символов
    .Select(x->x.JoinToString(''))// d - массив из строк 
    .Numerate // нумерация
    .where((i,w)->'а' not in w) // рассматриваем и номер и слово
    .first[0].print // выводим именно номер

    * LINQ (Language Integrated Query) — язык интегрированных запросов

    Python:

    С++:

    Результат: 157

    Видеорешение задания (теоретическое):

    📹 Видеорешение на RuTube здесь (теоретическое решение)


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

    8_17: Решение 8 задания ЕГЭ по информатике (сайт «Решу ЕГЭ», задание № 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

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

    📹 Видеорешение на RuTube здесь (теоретическое решение)