Задание 8
тема 2 из 2

Подсчёт слов и номер слова в списке

Число слов длины L из N букв равно NLN^L, а при условиях на буквы и места его считают по правилу умножения или перебором через itertools.product. Список всех слов в алфавитном порядке — это запись чисел в системе с основанием N, где буквы служат цифрами. Поэтому номер слова равен его значению плюс 1, а сложные условия проверяет программа, которая перебирает слова по порядку и считает номера.

Главная тема в задании8На карте навыков

Как считать слова и номера

Слово — любая цепочка букв заданного алфавита, не обязательно осмысленная. Длина слова LL, в алфавите NN букв.

  • Правило умножения: если первое место можно заполнить n1n_1 способами, второе — n2n_2 и так далее, всего слов n1⋅n2⋅…⋅nLn_1 \cdot n_2 \cdot \ldots \cdot n_L. Без ограничений — NLN^L.
  • Буква ровно один раз: L⋅(N−1)L−1L \cdot (N - 1)^{L - 1}. Ровно два раза: L(L−1)2⋅(N−1)L−2\dfrac{L(L - 1)}{2} \cdot (N - 1)^{L - 2}.
  • Число в системе с основанием PP не начинается с 0: на первое место P−1P - 1 цифр.
  • Алфавитный список: буквы в алфавитном порядке — цифры от 0 до N−1N - 1. Номер слова равен его значению в системе с основанием NN плюс 1.
  • Программа: for w in product(letters, repeat=L) перебирает все слова, условие проверяет if. Номер даёт enumerate(…, 1).

Правило умножения

Слово длины LL заполняют по местам. Если на первое место можно поставить n1n_1 букв, на второе — n2n_2 и выбор на одном месте не меняет числа вариантов на других, всего слов n1⋅n2⋅…⋅nLn_1 \cdot n_2 \cdot \ldots \cdot n_L. Это правило умножения. Когда на каждое место годится любая из NN букв, слов NLN^L.

В Python все слова перебирает функция product из модуля itertools: product('АБВ', repeat=4) выдаёт все четвёрки букв. Каждое слово — кортеж, условие на место проверяют по индексу: w[0] — первая буква.

Пример

Сколько существует четырёхбуквенных слов из букв А, Б, В, Г, Д, которые не начинаются с буквы А?

  1. 1.На первое место годятся 4 буквы: Б, В, Г, Д.
  2. 2.На каждое из трёх остальных мест — любая из 5 букв.
  3. 3.4⋅5⋅5⋅5=5004 \cdot 5 \cdot 5 \cdot 5 = 500. Программа перебирает все 54=6255^4 = 625 слов и печатает 500.

Ответ: 500500

Буква встречается ровно один или два раза

Если буква должна стоять в слове ровно один раз, сначала выберите её место: LL способов. Остальные L−1L - 1 мест заполняют другие N−1N - 1 букв. Всего L⋅(N−1)L−1L \cdot (N - 1)^{L - 1} слов.

Если буква стоит ровно два раза, два места из LL выбирают L(L−1)2\dfrac{L(L - 1)}{2} способами, остальные места дают (N−1)L−2(N - 1)^{L - 2}. В программе условие записывают как w.count('К') == 1.

Пример задания

Открытый банк ФИПИ

Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

Числа в системе счисления: первая цифра не 0

LL-значное число в системе с основанием PP записывают цифрами от 0 до P−1P - 1, но первая цифра не 0. Поэтому на первое место P−1P - 1 цифр, на остальные — по PP. Всего таких чисел (P−1)⋅PL−1(P - 1) \cdot P^{L - 1}. Об основании и цифрах — в блоке основание, цифры и развёрнутая запись.

Если на цифру есть условие, разберите случаи по месту этой цифры: первое место или другое. В программе перебирают все строки цифр и пропускают те, что начинаются с '0'.

Пример

Сколько существует пятизначных чисел в восьмеричной системе, в записи которых ровно одна цифра 7?

  1. 1.Цифра 7 на первом месте: остальные 4 места заполняют 7 цифр (0–6). 74=24017^4 = 2401.
  2. 2.Цифра 7 на одном из 4 других мест: 4 способа. Первая цифра — от 1 до 6, 6 способов. Три оставшихся места — по 7 цифр: 4⋅6⋅73=82324 \cdot 6 \cdot 7^3 = 8232.
  3. 3.2401+8232=106332401 + 8232 = 10633. Программа печатает то же число.

Ответ: 1063310633

Условия на соседние и разные цифры

Условия о соседях проще проверить программой. Кортеж склеивают в строку 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 для всех ii от 0 до L−2L - 2; две одинаковые цифры стоят рядом — s[i] == s[i + 1].

Пример

Сколько существует четырёхзначных чисел в шестеричной системе, в записи которых ровно одна цифра 5 и рядом с ней не стоит нечётная цифра?

  1. 1.Цифры 0–5, первая не 0. Цифра 5 одна, поэтому нечётные соседи — только 1 и 3.
  2. 2.Пропускаем строки с первым '0' и строки, где цифра 5 стоит не ровно один раз.
  3. 3.Запрещённые пары: 15, 51, 35, 53. Считаем строки без них.
  4. 4.Программа печатает 201.

Ответ: 201201

Цифры по убыванию

Если цифры трёхзначного числа идут слева направо строго по убыванию, число определяют три разные цифры: их можно поставить только в одном порядке. Число способов выбрать 3 цифры из PP равно P(P−1)(P−2)6\dfrac{P(P - 1)(P - 2)}{6}. Первая цифра — самая большая, поэтому она не 0.

Если цифры идут в невозрастающем порядке (равные цифры можно ставить рядом), считайте программой с условием a >= b >= c и первой цифрой не 0. Цифры-символы от '0' до '9' сравниваются так же, как числа.

Пример

Сколько существует трёхзначных чисел в шестеричной системе, цифры которых идут слева направо строго по убыванию?

  1. 1.Выбираем 3 разные цифры из шести (0–5) и ставим их по убыванию.
  2. 2.6⋅5⋅46=20\dfrac{6 \cdot 5 \cdot 4}{6} = 20.
  3. 3.Программа проверяет a > b > c и печатает 20. Первая цифра при этом условии не может быть 0.

Ответ: 2020

Номер слова в алфавитном списке

Запишите буквы алфавита в алфавитном порядке и дайте им цифры: первая буква — 0, вторая — 1, последняя — N−1N - 1. Тогда список всех слов длины LL в алфавитном порядке — это числа от 0 до NL−1N^L - 1 в системе с основанием NN, записанные LL цифрами. Слово номер 1 — число 0, поэтому номер слова равен его значению плюс 1.

Обратная задача: слово с номером KK — это число K−1K - 1, переведённое в систему с основанием NN и дополненное нулями слева до LL цифр. Так работает перевод из десятичной системы.

Пример задания

Открытый банк ФИПИ

Все 4-буквенные слова, в составе которых могут быть только буквы А, Т, О, М, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.
1. АААА
2. АААМ
3. АААО
4. АААТ
5. ААМА
6. ААММ
...

Под каким номером в списке идёт первое слово, которое начинается с буквы О?

Первое или последнее слово с условием

Если условие сложное, перебирайте список программой. Функция product выдаёт слова в алфавитном порядке, если буквы в строке записаны по алфавиту. Номер даёт enumerate(product(…), 1): счёт идёт с 1, как в списке.

Для первого подходящего слова печатайте номер и останавливайте цикл через break. Для последнего — запоминайте номер в переменной на каждом совпадении и печатайте её после цикла.

Пример

Все пятибуквенные слова из букв К, О, Т записаны в алфавитном порядке и пронумерованы с 1. Под каким номером стоит первое слово, в котором ровно две буквы Т и нет двух букв К рядом?

  1. 1.Буквы по алфавиту: 'КОТ'.
  2. 2.Условие: s.count('Т') == 2 и 'КК' not in s.
  3. 3.Программа печатает 36 КОКТТ.
  4. 4.Проверка: КОКТТ — это 010223=27+6+2=3501022_3 = 27 + 6 + 2 = 35, номер 35+1=3635 + 1 = 36.

Ответ: 3636

Слова с чётными или нечётными номерами

Если считают слова с нечётными номерами, в условие добавляют n % 2 == 1, с чётными — n % 2 == 0. Номер n берут из enumerate(…, 1), а не из значения слова: значение на 1 меньше номера, и чётность у них разная.

При чётном NN чётность номера видна по последней букве: номер нечётный, если цифра последней буквы чётная. Так ответ можно проверить вручную.

Пример

Все четырёхбуквенные слова из букв А, Л, Н, У записаны в алфавитном порядке и пронумерованы с 1. Сколько слов с нечётными номерами не начинаются с буквы У и содержат ровно одну букву Н?

  1. 1.Цифры: А — 0, Л — 1, Н — 2, У — 3. Нечётный номер — значит, последняя буква А или Н.
  2. 2.Н первая: последняя А, два средних места из А, Л, У — 3⋅3=93 \cdot 3 = 9.
  3. 3.Н последняя: первая А или Л, середина — 3⋅33 \cdot 3: 2⋅9=182 \cdot 9 = 18.
  4. 4.Н на одном из двух средних мест: первая А или Л, другое среднее — 3 буквы, последняя А: 2⋅2⋅3=122 \cdot 2 \cdot 3 = 12.
  5. 5.9+18+12=399 + 18 + 12 = 39. Программа печатает то же число.

Ответ: 3939

Проверьте себя

00

Потренируйте навык

Все задания на этот навык

Решать