Задание 8

Как решать задание 8 из ЕГЭ по информатике?

Зачастую задание 8 требует от ученика не просто проследить выполнение алгоритма для конкретного ввода, но и понять, что делает алгоритм в общем случае, предсказать его результат для произвольных входных данных или даже модифицировать его. Чтобы успешно выполнить это задание, важно уметь абстрагироваться от конкретных чисел и увидеть общую логику работы алгоритма.

Теория

Задачи под номером восемь можно решать тремя способами:

• руками
• обычной программой через строки
• используя модуль itertools в Python

Комбинаторика

Если слово состоит из L букв, причем есть n₁ вариантов выбора первой буквы, n₂ вариантов выбора второй и т.д., то число возможных слов вычисляется как произведение N = n₁ · n₂ · … · n_L.

Пример: количество трёхзначных чисел в пятеричной системе счисления будет равно 4*5*5 = 100

Если слово состоит из L букв, причем каждая может быть выбрана n способами, то число возможных слов вычисляется как N = n_L.

Пример: из букв А, Б и В, если буквы могут повторяться, можно составить 3*3*3*3 = 81 четырехбуквенное слово.

Число сочетаний из n по k — количество наборов из k элементов, выбранных из данных n элементов (порядок элементов в наборах не важен).

Пример: на полке стоит n = 10 книг, из них мы берем k = 3 книги. Считается по формуле:

Число размещений из n по k — количество способов расположить некоторые k из n различных объектов на пронумерованных местах, при условии, что каждое место занято в точности одним объектом (здесь порядок важен). Считается по формуле:

Полезное

1. Когда решаем руками, иногда проще пользоваться методом «от противного», то есть сначала посчитать слова, которые нам не подходят, а потом вычесть их из количества всех слов.
2. Нельзя путать понятия «ровно k раз», «хотя бы k раз» = «не менее k раз», «не более k раз» и т.д. (хотя бы k — раз ровно k раз и более; не более k раз — от 0 до k раз включительно).
3. Когда мы работаем с цифрами вместо букв, не забываем, что 0 не может стоять на первой позиции.
4. При ПЕРЕСТАНОВКЕ букв представляем карточки с буковками.
5. Решаем программой, только когда это удобно.

Разбор

Задача 1.

Вася составляет 6-буквенные слова, в которых есть только буквы К, Р, О, Т, причём О используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Задача 2.

Иван составляет 5-буквенные слова из букв А, Б, В, Г, Д, Э, Ю, Я. Первой и последней буквами этого слова могут быть только буквы Э, Ю или Я, на остальных позициях эти буквы не встречаются. Сколько различных кодовых слов может составить Иван?

3 * 5 * 5 * 5 * 3 = 125 * 9 = 1125.

Одна задача – три решения

Как мы уже выяснили, решить одну и ту же задачу можно разными способами: выбирайте тот, который вам больше нравится или тот, который считаете наиболее подходящим для определенной задачи.

Способ 1 – ручками, через системы счисления

Сопоставим имеющиеся буквы семеричным цифрам:

А — 0, Г — 1, М — 2, H — 3, С — 4, Т — 5, У — 6.

Аналитически составим нужное нам слово. Стараемся поставить буквы с максимальными численными значениями (нам нужно последнее слово, а значит, наибольшее по значению). Это будет слово ТУУУММ.

Переведем его в семеричное число, получим 566622. Переведем в десятичную сс, получим 100809. Заметим, что номер на 1 больше, чем число, стоящее под ним (под номером один стоит число 000000, под номером 2 – 000001 и т. д).

Прибавим 1 и получим ответ: 100810

Способ 2 – программой через вложенные форы

Способ 3 – программой через модуль itertools

Бонус

Решаем суперсложное авторское задание с нашего курса по подготовке к ЕГЭ по информатике:

Перебираются все одиннадцатиричные числа, запись которых содержит ровно 6 цифр. Найдите количество таких чисел, которые являются палиндромами или имеют сумму нечетных цифр, равную сумме четных цифр, а затем количество чисел, где оба условия выполняются одновременно, и запишите два значения через пробел.

Разбор:

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

Начнем с того, что создадим две переменные k1 и k2 и обнулим их, они будут нашими ответами.

Импортируем itertools для удобства и создадим все последовательности из одиннадцатеричного алфавита длиной 6 с помощью product().

Затем пройдемся по ним циклом и для удобства объединим каждый кортеж в строку методом join().

Очень важно не забыть проверить, что первый символ не 0 (причем строковый!), иначе условие про 6 разрядов не будет соблюдено. Проверяем, является ли строка палиндромом с помощью переворачивания строки срезом. А дальше самое интересное – как подсчитать суммы одиннадцатеричных цифр разной четности?

Мы решили оформить подсчет в отдельные функции (S1 и S2). Удобнее всего это сделать через функцию sum() и генераторное выражение внутри нее. Прохожусь по одиннадцатеричной строковой записи, беру каждый символ и перевожу его в 10СС (это обязательно, потому что у нас есть символ «а»), причем цифры беру только нужной четности, а затем их суммирую.

Возвращаемся в наш цикл и проверяем оставшиеся условия. Получаем ответ 34495 45

Вот так будет выглядеть программа в Python: