Автор статьи: Андрей Рогов
Введение
Не очень просто ответить на вопрос, что представляет собой задание номер 8 ЕГЭ по информатике. Спецификация экзамена не отражает реальной картины, а сами задания довольно разнообразны. И каждый тип задания требует специфических знаний, своих способов решения.
Так или иначе, все типы 8-го задания устроены следующим образом: есть некоторое множество объектов (обычно слова или числа), из которого нужно выделить подмножество, обладающее определёнными признаками. Для всех задач можно выделить два способа решения: аналитический и с помощью программирования. Как это часто бывает, оба способа используют независимые подходы и не пересекаются между собой в идее решения.
В этой статье мы рассмотрим только аналитический способ решения.
Опишем основные типы задач.
- Пронумерованный список слов, записанных в алфавитном порядке. Требуется найти номер конкретного слова или слова с определёнными свойствами. В решении используются свойства систем счисления. Отдельно обозначим задачи, в которых требуется найти не конкретное слово, а количество слов
- Слова, записанные из ограниченного набора. Требуется найти количество слов, удовлетворяющих требованиям. Например, конкретная буква на первой позиции, точное количество гласных, в слове не встречается определённая буква и т. д. Для решения строится модель слова и рассматриваются отдельные ситуации
- Числа, имеющие определённое количество разрядов и алфавит. Есть ограничения на состав числа, например все цифры различны, две чётные не стоят рядом и т. д. Способ решения похож на способ для второго типа
Системы счисления
В двух типах задач из трёх точно понадобится знание систем счисления. Рассмотрим базовые сведения о них.
Алфавит системы счисления — это набор цифр, используемых для записи чисел. Количество цифр в алфавите называется основанием. Типичная фраза из задания «Сколько существует шестнадцатеричных четырёхзначных чисел» означает, что необходимо рассматривать алфавит шестнадцатеричной системы счисления, в который входит 16 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Напоминаем, что для записи цифр с числовым значением, превышающим 9, принято использовать заглавные буквы латинского алфавита.
Для перевода чисел в позиционных системах счисления мы будем использовать два алгоритма: перевод из десятичной системы счисления в любую другую и из любой системы счисления в десятичную.
Для перевода числа из десятичной системы счисления используется алгоритм деления: число и получаемые частные делятся на основание новой системы счисления, пока не будет получен ноль. Все остатки, записанные в обратном порядке, дадут нам новую запись числа.
Например, число 123 при переводе в шестнадцатеричную систему счисления будет выглядеть так: 7B₁₆.
Для перевода можно также использовать средства электронных таблиц или языка программирования (это обсуждалось в статье о задании номер 5). В электронных таблицах существует функция ОСНОВАНИЕ (ЧИСЛО; ОСНОВАНИЕ).
А в языке программирования Python есть встроенные функции для двоичной, восьмеричной и шестнадцатеричной систем счисления. Для остальных придётся писать алгоритм.
Для обратного перевода в десятичную систему счисления необходимо каждую цифру умножать на вес разряда, в котором она стоит, и суммировать полученные произведения.
Или, опять же, использовать средства компьютера. В электронных таблицах понадобится функция ДЕС (ЧИСЛО; ОСНОВАНИЕ), а в Python — функция int (число, основание).
int('7B', 16)
123
Задача 1
На первый взгляд в задании нет ничего связанного с системами счисления. Однако тот факт, что слова записаны в алфавитном порядке, позволяет заменить буквы цифрами. При этом важно сопоставить цифры с буквами, записанными в алфавитном порядке. Для этого условия получится такая таблица:
Таким образом, вопрос задания можно перефразировать следующим образом: под каким номером идёт первое число, начинающееся с цифры 2? Поскольку все слова четырёхбуквенные, а первое число будет минимальным, нам подойдёт число 2000. Используется набор из 5 букв, поэтому число записано в пятеричной системе счисления. Обратим внимание, что первое слово в списке — АААА. При замене цифрами оно будет выглядеть так: 0000. Получается, что номер слова на единицу больше, чем его значение. Для нахождения номера слова переведём число в десятичную систему счисления и прибавим к нему 1.
int('2000', 5) + 1
251
Ответ на задание: 251.
Комбинаторика
Теперь перейдём к правилам комбинаторики.
Первое необходимое нам правило — это правило умножения. Если действие A можно выполнить m способами, а действие B можно выполнить n способами, то упорядоченная пара действий (A и B) может быть составлена m × n способами.
Например: в меню столовой есть 4 закуски, 4 первых блюда, 6 вторых блюд. Сколько вариантов обеда из трёх блюд можно составить? Решение: 4 × 4 × 6 = 96 вариантов.
Второе — правило сложения. Если два действия A и B не имеют общих элементов, причём действие A можно выполнить m способами, а действие B можно выполнить n способами, то выполнить любое из этих действий (либо A, либо B) можно m + n способами. Если существует пересечение между способами выполнения действий A и B, то формула принимает вид N = m + n − k, где k — число совпадающих способов.
Пример применения: в корзине лежит 7 яблок и 11 груш. Сколько существует способов выбрать один фрукт? Решение: 7 + 11 = 18 способов.
Задача 2
В этом задании необходимо использовать правила комбинаторики. Предположим, что буква Б стоит на первом месте. Рассмотрим каждую позицию в слове. В первой строке таблицы запишем, какие буквы могут стоять в этой позиции, а во второй строке — количество таких букв.
Применим правило умножения. Общее количество слов равно 1 × 4 × 4 × 4 = 64. Если буква Б стоит на втором месте, картина будет следующей:
Количество таких слов тоже равно 4 × 1 × 4 × 4 = 64. Чтобы найти общее количество слов, в которых буква Б стоит на первом или втором месте, применяем правило сложения, поскольку варианты не пересекаются: 64 + 64 = 128.
Для ситуаций, когда буква Б стоит на третьем и четвёртом месте, мы получим ещё 128 слов. Общее количество слов равно 256.
Задача 3
Это задание представляет собой комбинацию первых двух. У нас есть и упорядоченный список, и ограничения на позиции.
Для начала сопоставим буквы и цифры, аналогично первой задаче.
На этот раз в вопросе спрашивается не номер слова, а количество слов. Разберём, как определить, что у слова чётный номер.
В первой задаче мы выяснили, что номер слова — это десятичный эквивалент слова, записанного в определённой системе счисления. Букв в задании восемь, поэтому речь идёт о восьмеричной системе счисления. Основание системы счисления чётно, поэтому чётность числа определяется его последней цифрой. Если последняя цифра числа чётна, то и число чётно. Также вспомним, что номер слова на единицу больше десятичного эквивалента слова.
Таким образом, чётный номер будет у слов, оканчивающихся на букву, соответствующую нечётной цифре.
Сформулируем ограничения на буквы слова. В начале могут стоять только несогласные, т. е. Е, О и Ь — мягкий знак не является ни гласной, ни согласной буквой. В конце могут стоять буквы Е, О, Т и Ь. При этом в записи числа должно быть не меньше двух букв О.
Поскольку в словах по 6 букв, допустимое количество букв О — 2, 3, 4, 5 и 6. Довольно много комбинаций. Удобнее посчитать все комбинации без учёта количества букв О, затем посчитать комбинации, где букв О нет и где она одна, и найти разность между общим количеством и комбинациями, не подходящими по количеству букв О (0 или 1). Таким образом, вместо 5 ситуаций достаточно рассмотреть 3.
Учтём ограничения на первую и последнюю букву и подсчитаем общее количество комбинаций. На первом месте может быть одна из трёх букв. На местах со второго по пятое — одна из восьми. На последнем — одна из четырёх. Общее количество подсчитаем с помощью правила умножения: 3 × 8 × 8 × 8 × 8 × 4 = 49 152.
Подсчитаем количество комбинаций без буквы О. Теперь на каждой позиции может быть на одну букву меньше: 2 × 7 × 7 × 7 × 7 × 3 = 14 406. Чтобы посчитать количество комбинаций с одной буквой О, необходимо рассмотреть 6 ситуаций: буква О на первой позиции, буква О на второй позиции и т. д. Общее количество комбинаций с одной буквой О будет равно сумме этих шести ситуаций (правило сложения).
Буква О на первом месте: О × 7 × 7 × 7 × 7 × 3 = 7203.\
Буква О на втором месте: 2 × О × 7 × 7 × 7 × 3 = 2058.\
Ситуации, когда буква О на третьем, четвёртом и пятом месте, аналогичны. Это ещё 2058 × 3 = 6174 комбинаций.\
Буква О на шестом месте: 2 × 7 × 7 × 7 × 7 × О = 4802.\
Итого: 7203 + 2058 + 6174 + 4802 = 20 237 комбинаций с одной буквой О.
Чтобы найти комбинации, где букв О не меньше двух, вычтем из общего количества комбинаций те, в которых буквы О нет или она одна.
49 152 − 14 406 − 20 237 = 14 509.
Задача 4
В условии десятичные числа. Значит, рассматриваем алфавит из десяти цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Раз числа четырёхзначные, на первой позиции числа не может стоять ноль. Учесть, что все цифры различны, можно следующим образом.
Для первой позиции в числе доступны цифры от 1 до 9, всего 9 вариантов. Для второй позиции в числе доступны цифры от 0 до 9, всего 10 вариантов. Но какая-то цифра уже стоит на первом месте, и её использовать нельзя, иначе цифры будут повторяться. Поэтому для второй позиции количество вариантов меньше на один.
Для третьей позиции в числе количество вариантов меньше на два, поскольку одна цифра уже стоит на первом месте и ещё одна — на втором. А для четвёртой позиции количество вариантов меньше на три.
Поскольку нельзя, чтобы шли подряд одинаковые по чётности числа, чётность должна чередоваться. Если на первом месте чётная цифра, на втором может быть только нечётная, на третьем — чётная и на четвёртом — нечётная. И наоборот. Если обозначить чётные цифры как Ч и нечётные как Н, то числа будут иметь вид ЧНЧН и НЧНЧ.
Рассмотрим первый случай: ЧНЧН. На первом месте могут стоять цифры 2, 4, 6 и 8, всего четыре варианта. На втором месте — 1, 3, 5, 7 и 9, всего пять вариантов. Поскольку цифры первой и второй позиции не пересекаются между собой, мы не вычитаем из пяти один. На третьем месте могут стоять цифры 0, 2, 4, 6 и 8. Но одна чётная цифра уже стоит на первом месте, поэтому всего четыре варианта. На четвёртом месте стоит нечётная цифра, но одна нечётная уже стоит на втором месте, поэтому здесь также может быть четыре варианта цифр. Общее количество вариантов равно 4 × 5 × 4 × 4 = 320.
Теперь второй случай: НЧНЧ. На первом месте пять вариантов цифр: 1, 3, 5, 7, 9. На втором тоже пять: 0, 2, 4, 6 и 8. На третьем — опять нечётная, поэтому на один вариант меньше, четыре. Аналогично последняя позиция — четыре варианта. Общее количество 5 × 5 × 4 × 4 = 400.
Общее количество вариантов найдём по правилу сложения: 320 + 400 = 720.
Заключение
Мы рассмотрели методы аналитического решения задания номер 8 ЕГЭ по информатике. В статье систематизированы типы задач, встречающихся в этом задании, раскрыты теоретические основы решения задач с использованием систем счисления, продемонстрировано применение правил комбинаторики, представлены алгоритмы аналитического решения различных типов задач.
Рекомендуем начинать решение с анализа типа задачи и обязательно проверять корректность промежуточных результатов. Особое внимание следует уделить практическому применению рассмотренных методов и регулярному решению задач для закрепления полученных навыков.
Предлагаем решить подборку задач.