Калужский Александр: Добрый вечер! Над этим нужно думать отде..
19-03-2023
Читать статью
Figh: Добрый вечер, можете сказать, что необхо..
Дмитрий: Всё понятно!!! Спасибо!..
14-03-2023
Сегодня на повестке дня 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-буквенные слова, составленные из букв А, Р, У, К записаны в алфавитном порядке. Вот начало списка:
Закодируем буквы цифрами: А - 0, К - 1, Р - 2, У - 3. Здесь как раз буквы даны не в том порядке, как они идут в самом правом столбце. Но мы должны кодировать именно в том порядке, как буквы идут в самом правом столбце.
У нас получилось четыре цифры! Значит снова можно слова превратить в таблицу соответствия между десятичной системой и четверичной системой. Но десятичная система смещена на 1 позицию.
Выписываем данное нам слово и посмотрим, какое число в четверичной системе было бы, если бы у нас были в место слов числа в четверичной системе!
Получили число в четверичной системе 310204. Узнаем, какое число в десятичной системе соответствовало этому числу, если бы была обычная таблица соответствия. Для этого переведём число 310204 из четверичной системы в десятичную. Перевод делаем по аналогии перевода из двоичной системы в десятичную.
Но помним, что у нас нумерация идёт на 1 быстрее, нежели мы бы поставили десятичные числа, как в таблице соответствия, потому что нумерация начинается не с нуля, а с 1. Поэтому к числу 840 нужно прибавить 1, и в ответе будет 841
Все 4-буквенные слова, в составе которых могут быть буквы Н, О, Т, К, И, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.
Под каким номером в списке идёт первое слово, которое начинается с буквы О?
Закодируем буквы цифрами.
Получилось 5 цифр ( 0, 1, 2, 3, 4 ), значит, будем работать в пятеричной системе.
Нужно найти номер первого слова, которое начинается с буквы О. Если говорить на языке пятеричных чисел, то нужно найти номер числа 30005. Мы "забиваем нулями", чтобы число было четырёхразрядное, т.к. слова 4-х буквенные. Именно нулями, потому что нужно именно первое слово найти.
Теперь, как в предыдущей задаче, переведём число 30005 из пятеричной системы в десятичную.
Но опять же должны прибавить 1 к числу 375, т.к. нумерация отличается от десятичных чисел на 1 в большую сторону.
Вася составляет 5-буквенные слова, в которых есть только буквы В, О, Л, К, причём буква В используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Для начала решим вводную подзадачу.
Т.е буквы могут повторяться!
Например
Такая конструкция сильно напоминает перебор чисел, где вместо цифр используются буквы.
Рассмотрим перебор трёхразрядных чисел. Вместо 5 букв теперь можно использовать 10 цифр ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ). Цифры так же могут повторяться. Сколько получится вариантов ?
Выведем общую формулу для количества вариантов, когда символы могут повторяться!
Для трёхразрядных чисел от 000 до 999:
Вернёмся к пятибуквенным словам и нашей подзадаче. Здесь количество букв (разрядов) в слове равно 5, количество допустимых символов равно 4 ( В, О, Л, К ).
Вернёмся к изначальной задаче. Сначала найдём количество вариантов, когда буква В находится в самой левой ячейке!
Применим формулу! Здесь слово сократилось до четырёхразрядного. А количество букв для использования 3 (О, Л, К).
Но буква В так же может стоять во второй ячейке слева. Этот случай тоже даст 81 других комбинаций. Буква В может стоять в каждой из 5-ти ячеек, и везде будет получатся 81 комбинация.
Таким образом, окончательный ответ будет:
Разобравшись с этой задачей, больше половины тренировочных задач десятого задания из различных книг и сайтов по подготовке к ЕГЭ по информатике будут решаться, как по маслу!
Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите {У, Ч, Е, Н, И, К}. Сколько существует таких последовательностей, которые начинаются с буквы У и заканчиваются буквой К?
Применим главную формулу 8 задания из ЕГЭ по информатике
Здесь буквы могут изменяться на 3 ячейках! Значит, в формуле i=3. Количество допустимых символов, которые можно поставить в каждую ячейку равно 6. Значит, в формуле m=6.
В ответе будет 216.
Примечание: Здесь можно использовать все буквы в каждой ячейке, включая У и К. В некоторых задачах их уже использовать нельзя, т.е. сказано, что буквы У и К используются один раз в слове. Тогда в формуле m, будет на 2 единицы меньше. Нужно внимательно читать задачу!
Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А, причём в каждом слове есть ровно одна гласная буква и она встречается ровно 1 раз. Каждая из допустимых согласных букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Рассмотрим количество вариантов, когда гласная И стоит в первом месте!
Подсчитаем количество слов с помощью супер-формулы
Длина изменяющихся ячеек равна 4, а количество допустимых букв равно 2.
Но буква И может стоять не только на первом месте. Она так же может стоять и на 2, и на 3, и на 4, и на 5 месте. Каждый такое случай добавляет столько же новых слов.
Значит, при использовании только буквы И будет количество слов 16 * 5 = 80. Ещё столько же слов добавится, если в словах вместо буквы И будет использоваться буква А. Поэтому окончательный ответ будет 80 * 2 = 160
Отработаем главную формулу 8 задания из ЕГЭ по информатике.
Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Рассмотрим, какие варианты могут быть, если у нас на первом месте стоит согласная, а на последнем месте гласная
Получилось 4 разных случая. Подсчитаем, сколько слов можно составить при одном случае.
Длина изменяющихся ячеек равна 3, а количество возможных букв 4.
Но т.к. таких случая у нас четыре, то ответ будет 4 * 64 = 256
Рассмотрим важнейший "метод умножения" при решении 8 задания из ЕГЭ по информатике.
Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз , при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?
Эта задача отличается от уже разобранных тем, что каждую букву можно использовать один раз. В этой задаче удобнее воспользоваться немного другим методом решения! "Методом умножения"!
Решим вводную подзадачу (без дополнительных ограничений).
Сколькими способами можно составить 6-x буквенное слово из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз .
Чтобы найти возможные варианты, перемножаем для каждой ячейки количество букв из которых у нас есть выбор!
Вернёмся к изначальной задаче!
В начале подсчитаем "методом умножения" количество слов, не обращая внимание, на условие, в котором сказано, что слово не может содержать сочетание АЕ.
В формуле стоят почти все те же самые числа, как и в вводном примере, только первый множитель не 6, а 5. Это произошло из-за того, что у нас в задаче слово не может начинаться на букву Й. Значит, выбор на первую позицию будет не из 6 букв, а из 5.
Но в 600 комбинаций входят и те случаи, когда в слове присутствует сочетание АЕ. Теперь найдём сколько таких слов, где присутствует сочетание АЕ
Узнаем количество вариантов в каждом таком случае.
На первом месте мы не можем использовать букву Й, поэтому мы на первом месте выбираем из 3 букв.
Аналогично предыдущему случаю.
Всего слов с сочетанием АЕ будет
Примечание: Метод умножения можно было использовать и в задачах, которые мы рассмотрели ранее. Например, в задаче "Закрепление формулы" в первой свободной ячейке выбираем из 6 букв, во второй свободной ячейке тоже из 6 букв, и в третий свободной ячейке тоже можно использовать 6 букв. Значит, по методу умножения получается N = 6 * 6 * 6 = 63 = 216
Полина составляет 6-буквенные коды из букв П, О, Л, И, Н, А. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Полина?
Опять сказано, что каждая буква используется 1 раз, следовательно, нужно применять "метод умножения".
На первое место можно выбрать из 6 букв, предположим, мы выберем согласную. Тогда на второе место нужно выбирать из 3 гласных. Потом опять должна идти согласная, но их у нас осталось только 2. Далее, на следующее место выбираем из 2 гласных букв. И на предпоследнее место выбирается 1 согласная, а на последнее место остаётся 1 гласная.
Т.к. количество гласных букв и согласных одинаковое, и равно трём, то если мы бы начали делать "метод умножения" с гласной буквы, количество вариантов бы не поменялось.
Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее трёх и не более четырёх сигналов (точек и тире) ?
Зная формулу, без проблем решим данную примерную задачу из ЕГЭ по информатике.
У нас есть 2 символа, которые можно использовать: точка и тире. Фраза, что сообщение может иметь "не менее трёх и не более четырёх сигналов", означает, что сообщения могут быть длиною 3 символа и длиною 4 символа.
Подсчитаем общее количество вариантов.
Значит, для 24 различных символов (цифр, букв, знаков пунктуации и т.д.) мы найдём различные комбинации, чтобы их закодировать Ответ: 24
Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?
Нам нужно закодировать 300 различных вариантов! Имеются 4 различных лампочки! (Они имеют смысл, как количество допустимых символов!) На этот раз нужно узнать количество лампочек (количество разрядов, "длину слова"). Применяем формулу.
Не найдётся такое целое x, чтобы равенство стало верным. Поэтому берём целое минимальное x такое, чтобы 4x больше 300.
Пять лампочек на табло хватит, чтобы закодировать 300 сигналов, но, к сожалению, много комбинаций просто не пригодится!
Нужно выбрать в подарок 3 книги из 5. Сколькими способами можно выбрать ?
На рисунке показано две комбинации, как можно выбрать в подарок 3 книги из 5.
Данную задачку нужно решать используя формулу сочетаний из раздела комбинаторика.
n - количество книг, из которых мы выбираем подарок, m - количество книг, которое мы хотим выбрать, C - количество вариантов (способов).
Восклицательный знак - это факториал!
Факториалом числа "n" (условное обозначение n!- читается как "эн" - факториал) называется произведение чисел от 1 до "n"
Примечание: При использовании формулы сочетаний, не важен порядок, в котором мы выбираем одни и те же книги. Это будет один и тот же вариант.
Следующая задача часто встречается в книгах по подготовке к ЕГЭ по информатике.
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 5. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 встречается ровно три раза, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?
В начале нужно посчитать, сколькими способами на 5-ти ячейках можно расположить 3 единицы!
Обратите внимание, как будто мы выбираем 3 книги в подарок из 5 возможных! Значит, опять применяем формулу сочетаний из комбинаторики. Мы вычисляли уже её точно с такими же числами в прошлой задаче, количество вариантов равно 10.
Подсчитаем, сколько вариантов кодового замка можно составить при одном определённом расположении трёх единиц.
Применим формулу, есть две ячейки, в которых изменяются цифры, а в каждой ячейке может быть одна из 4 цифр.
Т.к. различных вариантов, как расположить единицы на 5 ячейках равно 10, то ответ будет 16 * 10 = 160
Ещё одна задача из примерных вариантов по подготовке к ЕГЭ по информатике.
Для записи результатов соревнований используется таблица, в которой для каждой из 20-ти команд по каждому из 10-ти видов состязаний записано 1, 2 или 3 (если команда заняла соответствующее место в этом состязании) или прочерк (если не заняла призовое место или не участвовала). Какое количество информации (бит) содержит таблица ?
Есть таблица с 20 командами и для каждой команды есть результат по 10-ти видам состязаний.
В каждой ячейке может быть 4 различных значения ( 1, 2, 3, - ). Нужно узнать, сколько бит занимает одна ячейка таблицы. Один бит может быть либо единицей, либо нулём.
Сделав рисунок, задача обрела привычные очертания.
Одна ячейка таблицы весит 2 бита. Найдём количество ячеек во всей таблице соревнований.
Тогда вся таблица будет весит:
В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?
Данную задачу нужно решать по формуле Шеннона
Найдём вероятность p того, что вытащили чёрный шарик.
Применим формулу Шеннона.
