Подсчёт слов и номер слова в списке
Число слов длины L из N букв равно , а при условиях на буквы и места его считают по правилу умножения или перебором через itertools.product. Список всех слов в алфавитном порядке — это запись чисел в системе с основанием N, где буквы служат цифрами. Поэтому номер слова равен его значению плюс 1, а сложные условия проверяет программа, которая перебирает слова по порядку и считает номера.
Как считать слова и номера
Слово — любая цепочка букв заданного алфавита, не обязательно осмысленная. Длина слова , в алфавите букв.
- Правило умножения: если первое место можно заполнить способами, второе — и так далее, всего слов . Без ограничений — .
- Буква ровно один раз: . Ровно два раза: .
- Число в системе с основанием не начинается с 0: на первое место цифр.
- Алфавитный список: буквы в алфавитном порядке — цифры от 0 до . Номер слова равен его значению в системе с основанием плюс 1.
- Программа:
for w in product(letters, repeat=L)перебирает все слова, условие проверяетif. Номер даётenumerate(…, 1).
Правило умножения
Слово длины заполняют по местам. Если на первое место можно поставить букв, на второе — и выбор на одном месте не меняет числа вариантов на других, всего слов . Это правило умножения. Когда на каждое место годится любая из букв, слов .
В Python все слова перебирает функция product из модуля itertools: product('АБВ', repeat=4) выдаёт все четвёрки букв. Каждое слово — кортеж, условие на место проверяют по индексу: w[0] — первая буква.
Пример
Сколько существует четырёхбуквенных слов из букв А, Б, В, Г, Д, которые не начинаются с буквы А?
- 1.На первое место годятся 4 буквы: Б, В, Г, Д.
- 2.На каждое из трёх остальных мест — любая из 5 букв.
- 3.. Программа перебирает все слов и печатает 500.
Ответ:
Буква встречается ровно один или два раза
Если буква должна стоять в слове ровно один раз, сначала выберите её место: способов. Остальные мест заполняют другие букв. Всего слов.
Если буква стоит ровно два раза, два места из выбирают способами, остальные места дают . В программе условие записывают как w.count('К') == 1.
Пример задания
Открытый банк ФИПИ
Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?
Числа в системе счисления: первая цифра не 0
-значное число в системе с основанием записывают цифрами от 0 до , но первая цифра не 0. Поэтому на первое место цифр, на остальные — по . Всего таких чисел . Об основании и цифрах — в блоке основание, цифры и развёрнутая запись.
Если на цифру есть условие, разберите случаи по месту этой цифры: первое место или другое. В программе перебирают все строки цифр и пропускают те, что начинаются с '0'.
Пример
Сколько существует пятизначных чисел в восьмеричной системе, в записи которых ровно одна цифра 7?
- 1.Цифра 7 на первом месте: остальные 4 места заполняют 7 цифр (0–6). .
- 2.Цифра 7 на одном из 4 других мест: 4 способа. Первая цифра — от 1 до 6, 6 способов. Три оставшихся места — по 7 цифр: .
- 3.. Программа печатает то же число.
Ответ:
Условия на соседние и разные цифры
Условия о соседях проще проверить программой. Кортеж склеивают в строку s = ''.join(w), тогда соседние цифры — подстрока из двух символов. «Цифра 5 не стоит рядом с 1 и 3»: ни одной из подстрок '15', '51', '35', '53' нет в s. Это проверяет any(p in s for p in (…)).
Другие частые условия: все цифры разные — len(set(s)) == len(s); соседние цифры разной чётности — int(s[i]) % 2 != int(s[i + 1]) % 2 для всех от 0 до ; две одинаковые цифры стоят рядом — s[i] == s[i + 1].
Пример
Сколько существует четырёхзначных чисел в шестеричной системе, в записи которых ровно одна цифра 5 и рядом с ней не стоит нечётная цифра?
- 1.Цифры 0–5, первая не 0. Цифра 5 одна, поэтому нечётные соседи — только 1 и 3.
- 2.Пропускаем строки с первым
'0'и строки, где цифра 5 стоит не ровно один раз. - 3.Запрещённые пары: 15, 51, 35, 53. Считаем строки без них.
- 4.Программа печатает 201.
Ответ:
Цифры по убыванию
Если цифры трёхзначного числа идут слева направо строго по убыванию, число определяют три разные цифры: их можно поставить только в одном порядке. Число способов выбрать 3 цифры из равно . Первая цифра — самая большая, поэтому она не 0.
Если цифры идут в невозрастающем порядке (равные цифры можно ставить рядом), считайте программой с условием a >= b >= c и первой цифрой не 0. Цифры-символы от '0' до '9' сравниваются так же, как числа.
Пример
Сколько существует трёхзначных чисел в шестеричной системе, цифры которых идут слева направо строго по убыванию?
- 1.Выбираем 3 разные цифры из шести (0–5) и ставим их по убыванию.
- 2..
- 3.Программа проверяет
a > b > cи печатает 20. Первая цифра при этом условии не может быть 0.
Ответ:
Номер слова в алфавитном списке
Запишите буквы алфавита в алфавитном порядке и дайте им цифры: первая буква — 0, вторая — 1, последняя — . Тогда список всех слов длины в алфавитном порядке — это числа от 0 до в системе с основанием , записанные цифрами. Слово номер 1 — число 0, поэтому номер слова равен его значению плюс 1.
Обратная задача: слово с номером — это число , переведённое в систему с основанием и дополненное нулями слева до цифр. Так работает перевод из десятичной системы.
Пример задания
Открытый банк ФИПИ
Все 4-буквенные слова, в составе которых могут быть только буквы А, Т, О, М, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.
1. АААА
2. АААМ
3. АААО
4. АААТ
5. ААМА
6. ААММ
...
Под каким номером в списке идёт первое слово, которое начинается с буквы О?
Первое или последнее слово с условием
Если условие сложное, перебирайте список программой. Функция product выдаёт слова в алфавитном порядке, если буквы в строке записаны по алфавиту. Номер даёт enumerate(product(…), 1): счёт идёт с 1, как в списке.
Для первого подходящего слова печатайте номер и останавливайте цикл через break. Для последнего — запоминайте номер в переменной на каждом совпадении и печатайте её после цикла.
Пример
Все пятибуквенные слова из букв К, О, Т записаны в алфавитном порядке и пронумерованы с 1. Под каким номером стоит первое слово, в котором ровно две буквы Т и нет двух букв К рядом?
- 1.Буквы по алфавиту:
'КОТ'. - 2.Условие:
s.count('Т') == 2и'КК' not in s. - 3.Программа печатает 36 КОКТТ.
- 4.Проверка: КОКТТ — это , номер .
Ответ:
Слова с чётными или нечётными номерами
Если считают слова с нечётными номерами, в условие добавляют n % 2 == 1, с чётными — n % 2 == 0. Номер n берут из enumerate(…, 1), а не из значения слова: значение на 1 меньше номера, и чётность у них разная.
При чётном чётность номера видна по последней букве: номер нечётный, если цифра последней буквы чётная. Так ответ можно проверить вручную.
Пример
Все четырёхбуквенные слова из букв А, Л, Н, У записаны в алфавитном порядке и пронумерованы с 1. Сколько слов с нечётными номерами не начинаются с буквы У и содержат ровно одну букву Н?
- 1.Цифры: А — 0, Л — 1, Н — 2, У — 3. Нечётный номер — значит, последняя буква А или Н.
- 2.Н первая: последняя А, два средних места из А, Л, У — .
- 3.Н последняя: первая А или Л, середина — : .
- 4.Н на одном из двух средних мест: первая А или Л, другое среднее — 3 буквы, последняя А: .
- 5.. Программа печатает то же число.
Ответ:
Проверьте себя
00