Ответ
5058
Задание 8 ЕГЭ по информатике
Что проверяет: Комбинаторика и перебор слов
Задание 8 ЕГЭ по информатике проверяет тему «комбинаторика и перебор слов». Ниже вы найдёте 4 варианта с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.
Вася составляет пятибуквенные слова, в которых есть только буквы Д, О, М, И, К, причём буквы могут повторяться. Слово не может начинаться с гласной, и в нём не может быть двух гласных подряд. Гласными считаются О и И.
Сколько существует таких слов, которые может написать Вася?
Ответ
1215
Считаем по позициям, разделяя слова по последней букве. Пусть a — число слов, оканчивающихся согласной, b — гласной.
Первая буква только согласная: a = 3, b = 0. На каждом следующем шаге согласную можно поставить после любой буквы (a + b вариантов, умноженных на 3), а гласную — только после согласной (a · 2).
Получаем по шагам: (3; 0), (9; 6), (45; 18), (189; 90), (837; 378). Сумма на пятом шаге равна 1215. Ответ — 1215.
Вася составляет четырёхбуквенные слова из букв К, О, С, А, причём буквы могут повторяться. В каждом слове должна быть ровно одна гласная (гласными считаются О и А).
Сколько существует таких слов?
Ответ
64
Выбираем позицию для единственной гласной: 4 способа. На эту позицию ставим одну из двух гласных: 2 способа.
Остальные три позиции занимают согласные К и С: по 2 варианта на каждую, то есть 2³ = 8. Итого 4 · 2 · 8 = 64. Ответ — 64.
Вася составляет пятибуквенные слова из букв А, Б, В, Г, причём буквы могут повторяться. Слово должно начинаться и заканчиваться согласной, а буква А должна встречаться в нём ровно два раза.
Сколько существует таких слов?
Ответ
81
Первая и последняя буквы согласные, значит обе буквы А стоят среди трёх средних позиций. Выбрать две позиции из трёх можно 3 способами.
Оставшиеся три позиции (первая, последняя и одна средняя) занимают согласные Б, В, Г: по 3 варианта на каждую, то есть 3³ = 27. Итого 3 · 27 = 81. Ответ — 81.
Теория к заданию 8 ЕГЭ по информатике: комбинаторика и перебор слов
Нужно посчитать количество слов, удовлетворяющих условиям, или найти номер слова в упорядоченном списке.
Что нужно знать
- Число слов длины k из алфавита мощности n равно n в степени k.
- Алфавитный порядок слов соответствует записи чисел в системе счисления с основанием n, где буквам присвоены цифры по алфавиту.
- Номер слова в списке, начинающемся с единицы, равен значению этого числа плюс 1.
- Условия вида «ровно две буквы О» считают через сочетания: выбираем позиции для О, остальные заполняем оставшимися буквами.
- Условие чётности номера накладывает ограничение на последнюю букву.
Комбинаторика для задания 8
- Правило произведения: если первый символ выбирается n₁ способами, второй n₂ и так далее, всего вариантов n₁ · n₂ · ...
- Слова длины k из алфавита в n букв с повторениями: n^k.
- Без повторений: n · (n−1) · ... · (n−k+1).
- Перестановки n различных букв: n!. Если есть одинаковые буквы, делим на факториалы их количеств.
- Запреты («не начинается с гласной», «нет двух одинаковых подряд») удобнее считать через вычитание: всего минус запрещённые.
- Номер слова в алфавитном списке считается позиционно: сколько слов начинается с более ранних букв, затем то же для второй позиции и так далее.
- Нумерация в задании может начинаться с 1, поэтому сверьтесь с приведённым в условии примером.
- Если вариантов немного, надёжнее написать короткую программу перебора, чем считать вручную.
Как решать задание 8
- Присвойте буквам цифры в алфавитном порядке, начиная с нуля.
- Переведите условия задачи в ограничения на разряды числа.
- Найдите самое большое (или нужное) слово, удовлетворяющее ограничениям.
- Переведите его в десятичную систему и прибавьте единицу.
- Запишите номер.
Разбор примера
Сколько существует пятибуквенных слов из букв А, Б, В, Г, если слово не может начинаться с буквы А, а остальные буквы произвольны?
- Всего букв в алфавите 4, длина слова 5.
- Первая позиция: буква А запрещена, значит остаётся 3 варианта.
- Каждая из оставшихся четырёх позиций заполняется любой из 4 букв.
- По правилу произведения: 3 · 4 · 4 · 4 · 4 = 3 · 4⁴.
- Считаем: 4⁴ = 256, значит 3 · 256 = 768.
Ответ768
Частые ошибки
- Забывают, что нумерация начинается с единицы, и ошибаются ровно на 1.
- Присваивают буквам цифры не в алфавитном порядке.
Задание 8 входит в ЕГЭ по информатике. Это единственная страница сайта, где собраны все варианты этого номера: текст условия, картинка задания, правильный ответ, разбор решения и теория с алгоритмом. Остальные номера открываются в списке выше, а их перечень с темами есть в списке заданий ЕГЭ по информатике.