Всем привет! Вот так незаметно подошли к итоговому 10 уроку и сегодня заканчиваем одну из самых проблемных тем в базовом разделе информатики. Вообще кодирование само по себе не сложно и довольно интересно, но что касается комбинаторики, то математическая тема подается слишком плотно для информатиков и как бы излишне, на мой взгляд, но если учесть, что информатики своего рода универсалы, то надо знать всё. "Нельзя объять необъятное" - говорят. Но для нас нет слова нельзя и мы сегодня сделаем акцент на те задания, которые вызвали у вас трудности на прошлых уроках ссылка https://dzen.ru/a/Z3qHp8t2VE84OGeK и рассмотрим разные придумки составителей ЕГЭ. Как-то мне, как информатику – программисту - электронщику в одном лице, пришлось вести вебинары среди учителей и экспертов ОГЭ и ЕГЭ. По грубой статистике всего 5% из них умело программировать на 3+ и знало компьютер не более чем на уровне пользователя, а остальные 95% знали хуже учеников. Если бы дать фипишникам решить их задания, то я думаю, что результат был бы похожим. Но не будем бороться со злом, а будем делать добро и продолжаем наш марафон.
Сначала совсем немного теории по комбинаторике, по кодированию мы уже всё довольно подробно разобрали на прошлых уроках. Хотя практически в прогах теория не понадобится, но есть некоторые задачи, которые можно решить по формулам комбинаторики, правда такой уровень редко встречается на ЕГЭ. Но если всё же вам интересно простое о непростом, поехали разбираться. Комбинаторика? Почему так называется раздел математики и что у него общего с кодированием? Кодирование в заданиях рассматривается на более широком уровне, чем в теории. Если в теории задача кодирования сводится к переводу информации к 0 и 1, то на практике рассматриваются варианты кодирования из разных символов и цифр для общего применения, например шифров замков, паролей, pin-кодов и т.п. Но и при таком кодировании так же работаем наше незаменимое показательное уравнение N=n^i, только вместо двух элементов кодирования в ПК (0 1) используется n – количество элементов кодирования в какой-нибудь системе кодирования. Например у вас есть две буквы А и В и вам нужно составить из них 3-буквенные слова. Сколько таких слов можно составить? Да, 8.
('A', 'A', 'A') ('A', 'A', 'B') ('A', 'B', 'A') ('A', 'B', 'B') ('B', 'A', 'A') ('B', 'A', 'B') ('B', 'B', 'A')('B', 'B', 'B').
Мы получили в программе восемь комбинаций путём перестановки на трёх позициях двух букв. Но посчитали мы их не методами комбинаторики, а универсальной схемой кодирования в ПК. Теперь давайте посмотрим как комбинаторика – наука о возможных комбинациях из определённого количества объектов – рассматривает это задание.
Есть три позиции _ _ _, на каждую из них можно поместить по два элемента А и B(2), т.е.
получаем 2 2 2 , 2*2*2=8. И существует так называемое правило умножения в размещении в комбинаторике: если элемент А можно выбрать n способами, а элемент B m способами, то пару элементов можно выбрать n*m способами. По сути то же самое 2 2 2 и 2^3. Но если усложнить задачу и добавить какие-то ограничения к условию на количество, например в том, что в коде должны быть только две буквы A; то в информатике всего один оператор – метод count() отсчитает количество и результат готов; а математикам не даны премудрости программирования и они придумали формулы как это посчитать. Смотрим ещё на одну формулу, учитывающую сочетание в комбинаторике: если у нас есть всего n элементов в коде и надо выбрать из них сочетание из m элементов, то количество комбинаций из n по m будет равно: n!/m!*(n-m)! Для нашего примера выше получаем: 3!/2!*(3-2)!=1*2*3/(1*2)*1=3 для двух букв А
('A', 'A', 'A') ('A', 'A', 'B') ('A', 'B', 'A') ('A', 'B', 'B') ('B', 'A', 'A') ('B', 'A', 'B') ('B', 'B', 'A')('B', 'B', 'B').
Кто не помнит о факториалах, напоминаю – геометрическая последовательность дискретного ряда: 4!=4*3*2*1=24.
Есть ещё у математиков в комбинаторике правило перестановок, о котором я рассказывала на практикуме №4 https://dzen.ru/a/Z3fLc3syb0QH-JwI , суть которого в том, что если в определенном коде из n позиций нужно посчитать количество возможных комбинаций при перестановке элементов, то при повторе элемента k раз, количество комбинаций будет равно n!/k! Например, слово ИНФОРМАТИКА 11 позиций И-2 раза повторяется, А-2 раза: 11!/2!*2!=1*2*3*4*5*6*7*8*9*10*11/1*2*1*2=9 979 200 перестановок.
Вот так, коротко в целом, можно обобщить основные составляющие комбинаторики. Как видите, преимущества в возможностях информатики налицо. Но каждому своё, а вы выбирайте тот метод, в котором уверены и который самый короткий по времени решения.
А теперь, как и обещала на прошлом 9 уроке, добьём оставшиеся типы задач 8 задания ЕГЭ и повторим новые методы Python. А дальше, через два урока, после 12 урока нас ждут великие дела – практическая информатика, где мы с вами будем раскрывать тайны Python на все случаи жизни. Некоторые уроки будут идти в видеоформате по подписке.
Задание 1: ЕГЭ 11 класс
· Георгий составляет коды их букв своего имени. Код должен состоять из 7 букв, и каждая буква в нём должна встречаться столько же раз, сколько в имени Георгий. Кроме того, одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Георгий?
Как не надо:
Как надо:
· Решение: самая типичная ошибка для подобного рода задач в том, что в параметрах функции product задают слово с повтором букв кодового алфавита. Для данного случая вместо “ ГЕОРИЙ” указывают “ГЕОРГИЙ”, включая букву Г два раза. Результат при этом получается неверный (больше, так как увеличиваются возможные комбинации из-за двух Г); возможно запутывает условие, в котором говорится, что каждая буква должна встречаться столько, сколько её содержится в самом слове “ГЕОРГИЙ”. Но не путайте кодовый алфавит и сам код.
· Первые четыре строки должны быть понятны, мы их подробно разбирали на предыдущих практикумах. Впрочем, четвертая тоже должна быть понятна. Очень часто при решении таких задач по каждой букве слова расписывают все count(), что в принципе является неграмотным подходом при решении задания. Если условие распространяется на все буквы, как в этом задании: ’каждая буква в нём должна встречаться столько же раз, сколько в имени Георгий”, то это не совсем удобный путь. Показываю две программы к этой задаче: как нерационально и как грамотно и экономно во времени написать программу. С функцией all мы подробно познакомились на прошлом практикуме https://dzen.ru/a/Z3qHp8t2VE84OGeK . В данном примере мы расширяем возможности функции all в виде составного логического выражения в параметрах, в котором одновременно проверяем количество букв в коде, сравнивая их с количеством букв в исходном слове и также делаем проверку на соседство двух одинаковых букв.
· Представьте, что у вас на ЕГЭ будет исходное слово из 25 букв и похожее задание, тогда all – единственный путь правильного быстрого решения. Вот такая простая задача, которая часто решается неверно и нерационально!
В следующем задании расширяем возможности all и учимся писать короткие лаконичные грамотные коды. Часто на своих курсах в IT-классе я задаю ребятам задания на самостоятельную проработку с помощью internet. Реакция практически одна и та же: коды либо непрозрачные, либо слишком длинные, т.е. чаще это опыт как не надо программировать, особенно на Python, который собственно и придумали для того, чтобы максимально упростить рутинные схемы программирования. Поэтому идём дальше, поэтапно постигая возможности Python, лучшего для ЕГЭ и не только для ЕГЭ языка программирования. Может быть, в дальнейшем подключим и другой язык к нашему курсу, например, Go, но пока реальность диктует питоновское программирование; а в год змеи это довольно символично и вдохновляет.
Задание 2: ЕГЭ 11 класс
· Светлана составляет коды из букв слова РОСОМАХА. Код должен состоять из 8 букв и каждая буква в нём должна встречаться столько же раз, сколько в заданном слове. Кроме того, в коде не должны стоять рядом две гласные и две согласные буквы. Сколько кодов может составить Светлана?
· Решение: первые четыре строки должны быть понятны; во второй строке программы мы в данном задании формируем две строки для гласных и согласных букв в исходном слове – росомаха. Для чего? Чтобы сделать проверку на наличие соседних гласных и согласных через in (принадлежность в их составе).
· Теперь формируем в строке 5 усложнённую all в условном операторе if. В составе параметров all проверяем (как и в предыдущей задаче) количество букв и в слове и в коде. Они должны быть равны.
· Внимание! В Python = и == разные операторы. = - оператор присвоения значения переменной, а == - оператор отношения – логического сравнения.
· Затем проверяем наличие соседних гласных и согласных букв попарно для каждой пары всей строки s, полученной из массива x в join методе. Не забываем о диапазоне цикла for при работе с парами; он должен быть (len(s)-1), так как рассматриваются i и i+1 элементы строки.
· Также обращаю внимание на сложную логическую конструкцию в all условии.
Вы уже знаете, что условие в функции all всегда указывается вначале. Смотрим на логику условия. Равенство букв – первое условие, оно обязательно. Следующее условие на гласные и согласные тоже обязательно, поэтому соединяем их логической операцией отношений и – and. Дальше смотрим варианты парных комбинаций гласных и согласных. Их может быть две: гласная и согласная или (or) согласная и гласная; поэтому оба условия объединяем логической операцией или; но внутри каждой комбинации обязательно выполнение условия на различие гласности (and – и). В результате получается вот такая составная структура логического параметра в условии функции all: (x1) and ( (x2 and x3) or (x3 and x2) ); внимательно со скобками – в логике они играют ключевую роль. Не забываем отделять логические группы скобками (выделены на примере).
Ну и напоследок давайте разберём домашние задания практикума 4 https://dzen.ru/a/Z3fLc3syb0QH-JwI и 5 https://dzen.ru/a/Z3qHp8t2VE84OGeK, которые, судя по неверным ответам, вызвали проблемы.
Домашнее задание. Практикум №4.
· Ученик составляет слова, переставляя буквы из слова “ ИДИЛЛИЯ”. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует различных слов, которые может написать ученик?
· Решение : решение с использованием формулы комбинаторики мы рассмотрели на практикуме, а самостоятельно вам надо было написать программное решение. Разбираем, почему неправильные ответы. Итак, во второй строке берётся не всё слово ИДИЛЛИЯ, а только кодовый алфавит (об этой ошибке я подробно рассказала выше). Теперь смотрим 4 строку. Вы её не указали, а именно она фиксирует исходное слово, в котором мы делаем перестановку. Т.е. на слова может быть два типа задач: по перестановке внутри слова и на кодирование на основе букв слова. При перестановках вам надо обязательно описать состав слова, т.е. представить подробно количество каждой буквы в исходном слове и тогда решение сойдётся с ручным.
Домашнее задание. Практикум №5.
· Определите количество шестизначных чисел в девятеричной системе счисления, в записи которых ровно одна цифра 4 и ровно две нечётные цифры.
· Решение: все строки кода на этом этапе курса уже должны быть понятны. Особенность задания в создании строки нечетных чисел и использовании генератора на проверку наличия двух нечётных чисел строки s в строке nc при помощи оператора условия в генераторе: if n in nc - если в строке s есть элемент строки nс, то мы его выбираем в текущий массив. В данном случае можно сократить код, не указывая имя массива, а сразу использовать функцию len() для подсчёта кол-ва полученных элементов. Это самое типичное задание на ЕГЭ по данной теме, поэтому не забывайте о генераторах и вспомогательных массивах.
На этом заканчиваем разбор ещё одной очень важной темы курса ликбеза по информатике и базовой составляющей ЕГЭ. Поскольку мы всё же информатики, то программирование наш главный инструмент и поэтому параллельно со всеми темами будем в дальнейшем осваивать алгоритмику и программирование. Но надо помнить, что приведённые программы не должны стать просто неким шаблоном для вас. Они эффективны и просты, но вы не научитесь программировать, если будете просто бездумно запоминать шаблоны и не практиковать собственные варианты. Пробуйте, ошибайтесь и ещё раз пробуйте и вскоре вы поймёте, что информатика – самый интересный, реальный (не абстрактный) и очень благодарный предмет!
Рада была встрече со всеми, кто дошёл до этого этапа и одолел все темы десяти первых уроков курса! Молодцы! На следующем уроке повторим пройденную теорию по Python и добавим ещё одну очень важную тему (самую нелюбимую всеми) – системы счисления. Мы УЖЕ знаем как кодируется в ПК ВСЁ (символы, звук, цвет), кроме ЧИСЕЛ. Вот ими и займёмся на следующем уроке после итогового обзора того, что выучили по Python. Обещаю, что и эта тема вам понравится. До встречи на 11 уроке!
Не забывайте об энергообмене. Этот канал - моя авторская работе на базе экспресс-курсов, которые я веду в своём центре «Информатика Севастополь». Подписывайтесь, комментируйте, выходите на диалог, заходите в нашу группу в контакте. https://vk.com/sev_informatika
Кто захочет пройти профкурс, звоните, приходите, пишите в личку. Скоро, с марта месяца начнётся набор десятиклассников в группу ЕГЭ 2026.