ЕГЭ по информатике 2021 — Задание 8 (Супер-разбор!)

Сегодня на повестке дня 8 задание из ЕГЭ по информатике 2021. Данный тип заданий включает в себя нахождение количества вариантов, элементы комбинаторики и другие математические понятия.
Перейдём к практике решения задач задания 8 ЕГЭ по информатике 2021.
Все 4-буквенные слова, составленные из букв А, Е, И, О записаны в алфавитном порядке и пронумерованы. Вот начало списка:
Запишите слово, стоящее на 248-м месте от начала списка.
Обозначим условно А — 0 , Е — 1 , И — 2 , О — 3 .
Важно: Нужно буквам присваивать цифры именно в том порядке, в котором они идут в самом правом столбце, потому что буквы могут дать в «перепутанном порядке» (например Е, А, И, О), и тогда ничего не получится.
Теперь запишем список с помощью цифр.
Получился обычный счёт в четверичной системе!! (всего используются 4 цифры: 0, 1, 2, 3). А слева нумерация показывает соответствие нашей десятичной системе. Но все числа десятичной системы в этой таблице соответствия сдвинуты на 1, ведь мы должны были начать с нуля.
Нас просят записать слово стоящее на 248, т.е. если была обычная таблица соответствия чисел десятичной системы и четверичной системы, слово стоящее на 248 месте, находилось бы на 247 (248 — 1) месте. Значит, наше искомое четверичное число соответствует 247 в десятичной системе.
Переведём число 247 в четверичную систему!
Получилось число 33134 в четверичной системе. Сделаем обратное декодирование в буквы. Таким образом, ответ будет ООЕО.
Ответы: ООЕО
Ещё одна похожая задача 8 задания из примерных вариантов ЕГЭ по информатике, но другой вариации.
Задача (Классика, Другая вариация)
Все 5-буквенные слова, составленные из букв А, Р, У, К записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААК
3. ААААР
4. ААААУ
5. АААКА
……
Укажите номер слова УКАРА
Закодируем буквы цифрами: А — 0 , К — 1 , Р — 2 , У — 3 . Здесь как раз буквы даны не в том порядке, как они идут в самом правом столбце. Но мы должны кодировать именно в том порядке, как буквы идут в самом правом столбце.
У нас получилось четыре цифры! Значит снова можно слова превратить в таблицу соответствия между десятичной системой и четверичной системой. Но десятичная система смещена на 1 позицию.
1. 00000
2. 00001
3. 00002
4. 00003
5. 00010
……
Выписываем данное нам слово и посмотрим, какое число в четверичной системе было бы, если бы у нас были в место слов числа в четверичной системе!
Получили число в четверичной системе 310204. Узнаем, какое число в десятичной системе соответствовало этому числу, если бы была обычная таблица соответствия. Для этого переведём число 310204 из четверичной системы в десятичную. Перевод делаем по аналогии перевода из двоичной системы в десятичную.

0 * 4 0 + 2 * 4 1 + 0 * 4 2 + 1 * 4 3 + 3 * 4 4 = 840 (в десятичной системе) —>
Но помним, что у нас нумерация идёт на 1 быстрее, нежели мы бы поставили десятичные числа, как в таблице соответствия, потому что нумерация начинается не с нуля, а с 1. Поэтому к числу 840 нужно прибавить 1, и в ответе будет 841
Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)
Все 4-буквенные слова, в составе которых могут быть буквы Н, О, Т, К, И, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.
Под каким номером в списке идёт первое слово, которое начинается с буквы О?
Закодируем буквы цифрами.
Получилось 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 в большую сторону.
Задача (Досрочная волна 2020 ЕГЭ по информатике, вариант 1)
Вася составляет 5-буквенные слова, в которых есть только буквы В, О, Л, К, причём буква В используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Для начала решим вводную подзадачу.
Пусть у нас есть те же буквы В, О, Л, К, каждая из букв может встречаться в слове любое количество раз или не встречаться совсем. Сколько можно составить 5-буквенных слов ?
Т.е буквы могут повторяться!
Такая конструкция сильно напоминает перебор чисел, где вместо цифр используются буквы.
Рассмотрим перебор трёхразрядных чисел. Вместо 5 букв теперь можно использовать 10 цифр ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ). Цифры так же могут повторяться. Сколько получится вариантов ?
Выведем общую формулу для количества вариантов, когда символы могут повторяться!
Для трёхразрядных чисел от 000 до 999:
N = 10 3 = 1000 вариантов.
Вернёмся к пятибуквенным словам и нашей подзадаче. Здесь количество букв (разрядов) в слове равно 5, количество допустимых символов равно 4 ( В, О, Л, К ).
N = 4 5 = 1024 вариантов.
Вернёмся к изначальной задаче. Сначала найдём количество вариантов, когда буква В находится в самой левой ячейке!
Применим формулу! Здесь слово сократилось до четырёхразрядного. А количество букв для использования 3 (О, Л, К).
N = 3 4 = 81 комбинация.
Но буква В так же может стоять во второй ячейке слева. Этот случай тоже даст 81 других комбинаций. Буква В может стоять в каждой из 5-ти ячеек, и везде будет получатся 81 комбинация.
Таким образом, окончательный ответ будет:
N = 81 * 5 = 405 различных вариантов.
Разобравшись с этой задачей, больше половины тренировочных задач десятого задания из различных книг и сайтов по подготовке к ЕГЭ по информатике будут решаться, как по маслу!
Задача(Закрепление формулы)
Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите <У, Ч, Е, Н, И, К>. Сколько существует таких последовательностей, которые начинаются с буквы У и заканчиваются буквой К?
Применим главную формулу 8 задания из ЕГЭ по информатике
N = m i = 6 3 = 216
Здесь буквы могут изменяться на 3 ячейках! Значит, в формуле i=3. Количество допустимых символов, которые можно поставить в каждую ячейку равно 6. Значит, в формуле m=6.
В ответе будет 216.
Примечание: Здесь можно использовать все буквы в каждой ячейке, включая У и К. В некоторых задачах их уже использовать нельзя, т.е. сказано, что буквы У и К используются один раз в слове. Тогда в формуле m, будет на 2 единицы меньше. Нужно внимательно читать задачу!
Задача (Демонстрационный вариант ЕГЭ по информатике, 2019)
Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А, причём в каждом слове есть ровно одна гласная буква и она встречается ровно 1 раз. Каждая из допустимых согласных букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Рассмотрим количество вариантов, когда гласная И стоит в первом месте!
Подсчитаем количество слов с помощью супер-формулы
N = m i = 2 4 = 16
Длина изменяющихся ячеек равна 4, а количество допустимых букв равно 2.
Но буква И может стоять не только на первом месте. Она так же может стоять и на 2, и на 3, и на 4, и на 5 месте. Каждый такое случай добавляет столько же новых слов.
Значит, при использовании только буквы И будет количество слов 16 * 5 = 80. Ещё столько же слов добавится, если в словах вместо буквы И будет использоваться буква А. Поэтому окончательный ответ будет 80 * 2 = 160
Отработаем главную формулу 8 задания из ЕГЭ по информатике.
Задача (Развиваем понимание формулы!)
Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Рассмотрим, какие варианты могут быть, если у нас на первом месте стоит согласная, а на последнем месте гласная

Получилось 4 разных случая. Подсчитаем, сколько слов можно составить при одном случае.
N = m i = 4 3 = 64
Длина изменяющихся ячеек равна 3, а количество возможных букв 4.
Но т.к. таких случая у нас четыре, то ответ будет 4 * 64 = 256
Рассмотрим важнейший «метод умножения» при решении 8 задания из ЕГЭ по информатике.
Задача (Другой метод решения!!)
Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз , при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?
Эта задача отличается от уже разобранных тем, что каждую букву можно использовать один раз. В этой задаче удобнее воспользоваться немного другим методом решения! «Методом умножения»!
Решим вводную подзадачу (без дополнительных ограничений).
Сколькими способами можно составить 6-x буквенное слово из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз .
Чтобы найти возможные варианты, перемножаем для каждой ячейки количество букв из которых у нас есть выбор!
N = 6 * 5 * 4 * 3 * 2 * 1 = 720
Вернёмся к изначальной задаче!
В начале подсчитаем «методом умножения» количество слов, не обращая внимание, на условие, в котором сказано, что слово не может содержать сочетание АЕ.

N = 5 * 5 * 4 * 3 * 2 * 1 = 600
В формуле стоят почти все те же самые числа, как и в вводном примере, только первый множитель не 6, а 5. Это произошло из-за того, что у нас в задаче слово не может начинаться на букву Й. Значит, выбор на первую позицию будет не из 6 букв, а из 5.
Но в 600 комбинаций входят и те случаи, когда в слове присутствует сочетание АЕ. Теперь найдём сколько таких слов, где присутствует сочетание АЕ
Узнаем количество вариантов в каждом таком случае.
N1 = 4 * 3 * 2 * 1 = 24
На первом месте мы не можем использовать букву Й, поэтому мы на первом месте выбираем из 3 букв.

N2 = 3 * 3 * 2 * 1 = 18
Аналогично предыдущему случаю.
N3 = 3 * 3 * 2 * 1 = 18
N4 = 3 * 3 * 2 * 1 = 18

N5 = 3 * 3 * 2 * 1 = 18
Всего слов с сочетанием АЕ будет
24 + 18 + 18 + 18 + 18 = 96
Значит, всего слов, которые удовлетворяют условию задаче будет
N = 600 — 96 = 504
Примечание: Метод умножения можно было использовать и в задачах, которые мы рассмотрели ранее. Например, в задаче «Закрепление формулы» в первой свободной ячейке выбираем из 6 букв, во второй свободной ячейке тоже из 6 букв, и в третий свободной ячейке тоже можно использовать 6 букв. Значит, по методу умножения получается N = 6 * 6 * 6 = 6 3 = 216
Задача (Закрепления «метода умножения»)
Полина составляет 6-буквенные коды из букв П, О, Л, И, Н, А. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Полина?
Опять сказано, что каждая буква используется 1 раз, следовательно, нужно применять «метод умножения».
На первое место можно выбрать из 6 букв, предположим, мы выберем согласную. Тогда на второе место нужно выбирать из 3 гласных. Потом опять должна идти согласная, но их у нас осталось только 2. Далее, на следующее место выбираем из 2 гласных букв. И на предпоследнее место выбирается 1 согласная, а на последнее место остаётся 1 гласная.
Т.к. количество гласных букв и согласных одинаковое, и равно трём, то если мы бы начали делать «метод умножения» с гласной буквы, количество вариантов бы не поменялось.
N = 6 * 3 * 2 * 2 * 1 * 1 = 72
Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее трёх и не более четырёх сигналов (точек и тире) ?
Зная формулу, без проблем решим данную примерную задачу из ЕГЭ по информатике.
У нас есть 2 символа, которые можно использовать: точка и тире. Фраза, что сообщение может иметь «не менее трёх и не более четырёх сигналов», означает, что сообщения могут быть длиною 3 символа и длиною 4 символа.
Подсчитаем общее количество вариантов.
N = 2 3 + 2 4 = 8 + 16 = 24 комбинаций.
Значит, для 24 различных символов (цифр, букв, знаков пунктуации и т.д.) мы найдём различные комбинации, чтобы их закодировать
Задача (Обратная предыдущей)
Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?
Нам нужно закодировать 300 различных вариантов! Имеются 4 различных лампочки! (Они имеют смысл, как количество допустимых символов!) На этот раз нужно узнать количество лампочек (количество разрядов, «длину слова»). Применяем формулу.
N = 4 x = 300
Не найдётся такое целое x, чтобы равенство стало верным. Поэтому берём целое минимальное x такое, чтобы 4 x больше 300.
4 5 = 1024
Пять лампочек на табло хватит, чтобы закодировать 300 сигналов, но, к сожалению, много комбинаций просто не пригодится!
Нужно выбрать в подарок 3 книги из 5. Сколькими способами можно выбрать ?
На рисунке показано две комбинации, как можно выбрать в подарок 3 книги из 5.
Данную задачку нужно решать используя формулу сочетаний из раздела комбинаторика.
n — количество книг, из которых мы выбираем подарок, m — количество книг, которое мы хотим выбрать, C — количество вариантов (способов).
Восклицательный знак — это факториал!
Факториалом числа «n» (условное обозначение n!- читается как «эн» — факториал) называется произведение чисел от 1 до «n»
Примечание: При использовании формулы сочетаний, не важен порядок, в котором мы выбираем одни и те же книги. Это будет один и тот же вариант.

Ответ: 10
Следующая задача часто встречается в книгах по подготовке к ЕГЭ по информатике.
Задача (Главная формула + сочетания)
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 5. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 встречается ровно три раза, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?
В начале нужно посчитать, сколькими способами на 5-ти ячейках можно расположить 3 единицы!

Обратите внимание, как будто мы выбираем 3 книги в подарок из 5 возможных! Значит, опять применяем формулу сочетаний из комбинаторики. Мы вычисляли уже её точно с такими же числами в прошлой задаче, количество вариантов равно 10.
Подсчитаем, сколько вариантов кодового замка можно составить при одном определённом расположении трёх единиц.
Применим формулу, есть две ячейки, в которых изменяются цифры, а в каждой ячейке может быть одна из 4 цифр.
N = m i = 4 2 = 16
Т.к. различных вариантов, как расположить единицы на 5 ячейках равно 10, то ответ будет 16 * 10 = 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, — ). Нужно узнать, сколько бит занимает одна ячейка таблицы. Один бит может быть либо единицей, либо нулём.
Сделав рисунок, задача обрела привычные очертания.
Как будто мы решаем задачу с перебором слов. Но здесь длина слова неизвестна, а количество вариантов, которое должно получится уже дано и равно 4 (четырём). Применим главную формулу из 10 задания из ЕГЭ по информатике.
N = m i = 2 i = 4
i=2 бита (длина равна «2 буквам», если воспринимать задачу, как со словами.)
Одна ячейка таблицы весит 2 бита. Найдём количество ячеек во всей таблице соревнований.
Всего ячеек = 20 * 10 = 200
Тогда вся таблица будет весит:
V = 2 бита * 200 = 400 бит.
Ответ: 400
Формула Шеннона
В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?
Данную задачу нужно решать по формуле Шеннона
Найдём вероятность p того, что вытащили чёрный шарик.
p = (количество чёрных шаров) / (количество всех шаров) = 8 / (24 + 8) = 8 / 32 = 1 /4
p = 1 / 4
Применим формулу Шеннона.
x = log2(4)
2 x = 4
x = 2 бита
Ответ: 2
ХАРД КОМБИНАТОРИКИ
Вася составляет 5-буквенные слова, в которых есть только буквы П, И, Р, О, Г, причём в каждом слове буква Р может встречаться не более двух раз, при этом, если она есть, то после неё обязательно стоит гласная буква. Все допустимые буквы, кроме Р, могут встречаться в слове любое количество раз или не встречаться совсем. Сколько существует таких слов, которые может написать Вася?


Определим сколько раз может встречаться буква Р в слове длины 5: 0, 1, 2, 3,4 и 5 раз. Но по условию она может встречать 0, 1 или 2 раза, тогда найдем кол-во слов с данными вариантами
Р не встречается в слове:
на каждое место можно поставить по 4 буквы: 4^5=1024 слова
Р встречается 1 раз:
Р@***
*Р@**
Р@*
*Р@
каждая из «*» — 4 варианта постановки букв(П,И,О,Г), а каждая «@» — 2 варианта гласных букв(О,И), так как по условию после буквы Р встречается только гласная.
в каждом варианте: 4*4*4*1*2=128 слов для каждой позиции, для всех позиций: 128*4=512 случаев
Р встречается 2 раза:
Р@Р@*
P@*Р@
*Р@P@
то есть на каждую из 3х позиций получаем: 1*2*1*2*4=16 вариантов, тогда на все позиции: 3*16=48 слов
Комбинаторика
Например, в цифровом трехзначном кодовом замке на чемодане, когда в каждом из трех разрядов может быть 10 различных цифр: 10 3 = 10 ⋅ 10 ⋅ 10 = 1000 комбинаций.
Предположим, что мы забыли комбинацию замка, но точно помним, что первая цифра 5, а вторая 3 или 4, т.е первой может быть только одна цифра, а второй — 2. Тогда нам надо перебрать 1 ⋅ 2 ⋅ 10 = 20 комбинаций, чтобы открыть замок.
Рассмотрим кодовый замок с десятью кнопками цифр, который обычно используется для входа в подъезд. Чтобы открыть дверь, нужно нажать в определенной последовательности 3 цифры. Первой цифрой может быть любая из 10, второй — 9 оставшихся, третьей — 8. Рассчитаем количество различных комбинаций: 10 ⋅ 9 ⋅ 8 = 720.
Размещения без повторений: \( A^k_n = \frac
Частным случаем размещения без повторений, когда n = k, является перестановка: \(P_n = A^n_n = n! \)
Допустим в замке, пример которого мы приводили выше, нужно нажать все 10 цифр в определенной последовательности. В таком замке 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 3628800 комбинаций.
Для числа перестановок с повторениями справедлива формула: \( P_n (n_1, n_2, …, n_k) = \frac
Пусть в кодовом замке нужно набрать десять цифр, среди которых может быть использовано пять цифр 5, четыре цифры 4 и одна цифра 1. Тогда в таком замке количество комбинаций:
Если же в замке нужно нажать всего три цифры одновременно, то количество комбинаций можно вычислить по формуле сочетания: \( C^k_n = \frac
В таком замке \( \frac<10!> <7! ⋅ 3!>= \frac<10 ⋅ 9 ⋅ 8> <1 ⋅ 2 ⋅ 3>= \) 120 комбинаций.
Задача: Некоторый алфавит содержит 4 различных символа. Сколько трехбуквенных слов можно составить из символов этого алфавита, если символы в слове могут повторяться? Слова не обязательно должны быть осмысленными словами русского языка.
Решение: по формуле размещения с повторениями, при n = 4, k = 3: 4 3 = 64. Ответ: 64
Задача: Сколько слов длиной в 5 букв, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Решение: Первая буква должна быть одной из двух: Е и Э, остальные могут быть любой из трех. 2 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 = 162. Ответ: 162
Задача: Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Решение: Пусть буква С стоит в слове на первом месте. Тогда на каждое из оставшихся 4 мест можно поставить независимо одну из 3 букв. То есть всего 1 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 = 81 вариантов слова.
Таким образом букву С можно по очереди поставить на все 5 мест, в каждом случае получая 81 вариант, поэтому всего 81 ⋅ 5 = 405 таких слов. Ответ: 405
Задачи для самостоятельного решения
Некоторый алфавит содержит 3 различных символа. Сколько четырехбуквенных слов можно составить из символов этого алфавита, если символы в слове могут повторяться?
Сколько есть различных символьных последовательностей длины от одного до четырёх в трёхбуквенном алфавите, содержащем буквы А, B, C?
Сколько слов длины 6, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Сколько слов длины 5, начинающихся и заканчивающихся гласной буквой, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует пятибуквенные слова, в которых есть только буквы Е, Г, Э, причём буква Е появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Алексей?
Ольга составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Ольга использует 4-буквенные слова, в которых есть только буквы A, B, C, D, X, Y, Z. При этом первая буква кодового слова — это буква X, Y или Z, а далее в кодовом слове буквы X, Y и Z не встречаются. Сколько различных кодовых слов может использовать Ольга?
Николай составляет 5-буквенные коды из букв А, Б, В, Г, Д. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Д. Сколько различных кодов может составить Николай?
Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?
Сколько существует четырехзначных чисел, делящихся на 5, в которых каждая цифра может встречаться только один раз.
Сколько существует шестизначных чисел, делящихся на 5, в которых каждая цифра может встречаться только один раз, при этом никакие две чётные и две нечётные цифры не стоят рядом.
Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
- ААААА
- ААААО
- ААААУ
- АААОА
Запишите слово, которое стоит на 210-м месте от начала списка.
Петя составляет семибуквенные слова перестановкой букв слова ТРАТАТА. Сколько всего различных слов может составить Петя?
(Автор: А.Н. Носкин )
Женя составляет слова переставляя буквы З, А, П, И, С, Ь. Сколько слов может составить Женя, если известно, что Ь не может стоять на первом месте и после гласной?
Ипполит составляет 6-буквенные слова, в которых есть только буквы М, Е, Ч, Т, А, причём буква А используется в каждом слове хотя бы 3 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько различных слов может написать Ипполит?
Все 6-буквенные слова, составленные из букв А, О, И, Э, У, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
Под каким номером стоит последнее слово, начинающееся и заканчивающееся буквой О?
Сергей составляет 6-буквенные коды из букв К, А, Л, И, Й. Буква Й может использоваться в коде не более одного раза, при этом она не может стоять на первом месте, на последнем месте и рядом с буквой И. Все остальные буквы могут встречаться произвольное количество раз или не встречаться совсем. Сколько различных кодов может составить Сергей?
Задача №10. Измерение количества информации. Основы комбинаторики.
При работе с вычислительной техникой, информационным объемом сообщения называют количество двоичных символов, которое используют для кодирования этого сообщения.
Чтобы найти информационный объем сообщения I, нужно количество символов этого сообщения N умножить на количество бит, выделяемых для кодирования одного символа
K : I = N * K.
Количество символов в некотором алфавите называется мощностью алфавита.
Несложно понять, что количество слов длиной N, составленных из символов (букв) алфавита мощностью M равно M N .
При компьютерном кодировании мощность алфавита равна 2, значит количество слов длиной N равно 2 N .
Подсчет количества буквенных цепочек
Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
Запишите слово, которое стоит на 210-м месте от начала списка.
Заменим буквы А, О, У на 0, 1, 2 и выпишем начало списка:
Полученная запись есть числа, записанные в троичной системе счисления в порядке возрастания. Тогда на 210 месте будет стоять число 209 (т. к. первое число 0). Переведём число 209 в троичную систему: 20910 = 212023
Заменим обратно цифры на буквы и получим УОУАУ.
Сколько слов длины 6, начинающихся с согласной буквы, можно составить из букв Г, О, Д? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
На первом месте может стоять две буквы: Г или Д, на остальных — три буквы.
Слов, начинающихся на Г, 3 5 . Слов, начинающихся на Д, тоже 3 5 .Таким образом, можно составить 2 · 3 5 = 486 слов.
Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Пусть С стоит в слове на первом месте. Тогда на каждое из оставшихся 4 мест можно поставить независимо одну из 3 букв. То есть всего 3*3*3*3 = 81 вариант. Таким образом, С можно по очереди поставить на все 5 мест, в каждом случае получая 81 вариант. Итого получается 81 * 5 = 405 слов.
Количество информации при двоичном (компьютерном) кодировании
Объем сообщения – 7,5 Кбайт. Известно, что данное сообщение содержит 7680 символов. Какова мощность алфавита?
Объем сообщения I, написанного в исходном алфавите мощности M, содержащего N символов, равен: I = log2M * N
Log2M = (7,5 * 2 13 бит) / 7680 =(7,5 * 2 13) /(15 * 2 9 ) = 8
Количество информации при различных (не компьютерных) способах кодирования
Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?
Мы имеем алфавит из двух букв: точка и тире. Из двух букв можно составить 2 4 четырёхбуквенных слова и 2 5 пятибуквенных слов.
Значит, всего можно закодировать 16 + 32 = 48 различных символов.
Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?
Мощность алфавита M =3 («включено», «выключено» или «мигает»).
Количество различных сигналов 18 <= M N = 3 N . (Поскольку равенство не выполняется, N берем с избытком, иначе не сможем закодировать все сигналы). N = 3.
Ты нашел то, что искал? Поделись с друзьями!
Спасибо за то, что пользуйтесь нашими материалами. Информация на странице «Задача №10. Измерение количества информации. Основы комбинаторики.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам. Чтобы успешно сдать необходимые и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из разделов нашего сайта.