Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

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


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


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



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

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


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

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



Решение:

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


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


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

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


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

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


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


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


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

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


Ответы: ООЕО

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


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

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

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

Решение:

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


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

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


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

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


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

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



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


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


Ответ: 841


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

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


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

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


Решение:

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


ЕГЭ по информатике - задание 10 (кодируем буквы цифрами от 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-буквенных слов ?

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


Например


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

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


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


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

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


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

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


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


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


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


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


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

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


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


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


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


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


Ответ: 405


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


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

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


Решение:

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

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


N = mi = 63 = 216

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


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


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


Ответ: 216


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

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


Решение:

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



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

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


N = mi = 24 = 16

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


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


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


Ответ: 160

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


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

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



Решение:

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




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


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


N = mi = 43 = 64

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


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



Ответ: 256

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


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

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


Решение:

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


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


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



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

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


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

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


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


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


N = 5 * 5 * 4 * 3 * 2 * 1 = 600

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


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


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


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

N1 = 4 * 3 * 2 * 1 = 24

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

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

N2 = 3 * 3 * 2 * 1 = 18

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

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

N3 = 3 * 3 * 2 * 1 = 18

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

N4 = 3 * 3 * 2 * 1 = 18

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


N5 = 3 * 3 * 2 * 1 = 18

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

24 + 18 + 18 + 18 + 18 + 18 = 96

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

N = 600 - 96 = 504


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


Ответ: 504


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

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



Решение:

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

Опять сказано, что каждая буква используется 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.


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

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


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

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


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


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


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


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

Ответ: 10

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


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

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


Решение:

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


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


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


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


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

Применим формулу, есть две ячейки, в которых изменяются цифры, а в каждой ячейке может быть одна из 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, - ). Нужно узнать, сколько бит занимает одна ячейка таблицы. Один бит может быть либо единицей, либо нулём.

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

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

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


N = mi = 2i = 4

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

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


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

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


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

Ответ: 400

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


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

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



Решение:

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

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

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


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

p = 1 / 4

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


x = log2(4)

2x = 4

x = 2 бита

Ответ: 2




16-06-2020 в 16:07:41





Похожая статья:

ЕГЭ по информатике - Задание 6 (Алгоритмы, Автоматы)

Привет! Сегодня исследуем интересное задание 6 из ЕГЭ по информатике....

Категория: ЕГЭ  Подкатегория: -
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



ЕГЭ по информатике - Задание 14
ЕГЭ по информатике - Задание 13





Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy