Статья Автор: Деникина Н.В., Деникин А.В.

Когда условие сужает клетку

Дальше в заданиях появляются оговорки: «начинается с согласной», «первая и последняя буквы совпадают», «две одинаковые буквы не стоят рядом».

Правило произведения от этого не ломается. Меняется одно: на какой-то клетке становится меньше доступных букв. Вся работа — понять, на какой именно и насколько меньше.


Пример. Соседи не совпадают

Сколько слов длиной 5 и составленных из букв слова КОНУС, в которых нет рядом стоящих одинаковых букв.

Первую букву берёшь любую — ограничений на неё нет. А дальше на каждое место нельзя поставить ту букву, что стоит слева. Ровно один вариант вычёркивается.

Соседи не совпадают: слова длины 5 из букв слова КОНУС5любая×4≠ 1-й×4≠ 2-й×4≠ 3-й×4≠ 4-й5 × 4 × 4 × 4 × 4 = 1280запрещена одна буква — та, что слева; значит остаётся на одну меньше

Условие на конкретную клетку

«Начинается с согласной», «первая буква — гласная», «первая совпадает с последней». Здесь ограничение бьёт по одной клетке, а остальные остаются полными — их трогать не надо.

Пример. Первая буква — согласная (в слове КОНУС это К, Н, С)3соглас.×5любая×5любая×5любая×5любая3 × 5 × 5 × 5 × 5 = 1875меняем число только на первой клетке, остальные четыре полные

Программное решение

Считать аналитически легко, если есть опыт решения комбинаторных задач. Но куда проще написать программу, которая переберёт слова и проверить их на соответствие требованиям. 

Код ниже решает следующую задачу: перебрать все слова длины 5 из букв слова КОНУС, оставить те, где нет одинаковых соседей.

Внутренний цикл сравнивает соседние буквы: w[i] и w[i+1]. Если хоть одна пара совпала, слово бракуется — флаг ok становится False, и в счётчик оно не попадёт. Это прямой перевод фразы из условия в код: изобретать ничего не нужно, читаешь условие и записываешь его же через if.

Почему это эффективно: все 3125 слов компьютер проходит за доли секунды, а формулу такой проверкой ты подтверждаешь раз и навсегда. И запомни сам приём сравнения соседей — в самых сложных заданиях 8 он станет частью решения.



Результат работы программы
1280

Совпало с формулой 5 × 44. Значит, рассуждение «запрещена ровно одна буква» верное — можно пользоваться им дальше без опаски.


Это же решение можно написать короче, используя функцию all().


Как это работает

  • all() — принимает итерируемый объект (в нашем случае генератор) и возвращает True, если все элементы в нём истинны.

  • w[i] != w[i+1] for i in range(len(w)-1) — генератор, который проверяет каждую соседнюю пару букв на неравенство.

  • Если все пары не равны (т.е. нигде нет двух одинаковых соседних букв), то all() возвращает True, и мы увеличиваем счётчик.


Проверь себя


Посчитайте: сколько слов длины 4 из букв слова ГРОМ, в которых никакие две одинаковые буквы не стоят рядом? Введите число.


Сколько слов длины 4 из букв слова МОСТ, у которых первая и последняя буквы одинаковые?


Посчитайте: сколько слов длины 6 из букв слова КОТ, в которых нет двух одинаковых букв подряд? Введите число.
Печать