Задание 8 · Измерение количества информации
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — слова из Т, О, Р, К, А с нечётными номерами, ровно двумя О не подряд и не на А, — прошла через подтемы, и каждая добавляла к программе новое условие. Пролистай версии: точками отмечены строки, которых не было в предыдущей.
- Подтема 1, «Слова и перебор»: все слова — product. Точками отмечены новые строки.
- Подтема 2, «Сколько раз буква»: ровно две О, не с А.
- Подтема 3, «Соседние буквы»: нет двух О подряд.
- Подтема 5, «Нумерованный список»: номер слова — enumerate с 1. Ответ задачи темы — 168.
Каждое условие — отдельная проверка, и каждую можно сверить с рассуждением: 544 и 336 в подтемах 2 и 3 получены и умножением. Подтема 4 переносит те же приёмы на записи чисел, а дополнительный урок — на слова, которые перебором не перебрать.
Карта темы
Каждая подтема дала несколько приёмов, и любое решение собирается из них. Сверху — путь от условия к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Словаалфавит, длина, повторы
- Условиякаждая фраза — отдельная проверка
- Подсчётумножение или перебор product
1Слова и перебор
- mⁿслов длины n из m букв
- без повторов5 · 4 · 3…: каждый раз на букву меньше
product(…, repeat=n)все слова по очереди
2Сколько раз встречается буква
- ровно kвыбрать места, остальные — из других букв
- хотя бы однавсе слова минус слова без неё
word.count('О')по одной букве, не фрагментом
3Соседние буквы
- не рядомрасставить по промежуткам
- рядомсклеить в один блок
'ОО' not in wordнет двух О подряд
4Числа в системе счисления
- первая цифране ноль
range(q)цифры системы q числами- чётность числапри нечётном основании — по сумме цифр
5Нумерованный список
- номерзначение записи + 1
- алфавитбуквы по порядку, а не как в условии
enumerate(…, start=1)номер отдельно от счётчика
6Когда перебор не успеваетдополнительный урок
- оценкаmⁿ вариантов до запуска
- состоянияхранить количества, а не слова
Как решать
Любое задание 8 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- лишняя буква
- «ровно две О»: остальные места — из всех пяти букв → остальные — из четырёх, без О. Спроси себя: не появится ли на этих местах третья О?подтема 2
- count('АО')
word.count('АО')→word.count('А') + word.count('О'). Спроси себя: я считаю буквы или фрагмент подряд?подтема 2- in и соседство
- «А и Б рядом» проверили через наличие обеих → 'АБ' in word or 'БА' in word. Спроси себя: стоят ли буквы подряд и в каком порядке?подтема 3
- начальный ноль
- посчитали числа с нулём впереди → первая цифра — не ноль. Спроси себя: будет ли это n-значное число?подтема 4
- чётность числа
- чётность по последней цифре в системе 9 → при нечётном основании — по сумме цифр. Спроси себя: основание чётное или нечётное?подтема 4
- алфавит не по порядку
product('ТОРКА', repeat=5)→product('АКОРТ', repeat=5). Спроси себя: буквы стоят по алфавиту?подтема 5- номер с нуля
enumerate(…)→enumerate(…, start=1). Спроси себя: какой номер у первого слова?подтема 5- номер и счётчик
- номером считали счётчик подходящих слов → номер растёт на каждом слове списка. Спроси себя: это место в полном списке или число найденных?подтема 5
Итог
Тема пройдена: задача темы решена от перебора всех слов до ответа 168. Вот что взять с собой.
- ПорядокСлова, условия, подсчёт, номер, проверка.
- УсловияКаждая фраза — отдельная проверка в программе.
- РассуждениеМеста и промежутки — сверка с программой.
- НомерАлфавит по порядку, enumerate с единицы.
- Задача темы3125 → 544 → 336 → 168 с нечётными номерами.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Сколько четырёхбуквенных слов из букв А, Б, В, если буквы могут повторяться? А если не могут?
ОтветСкрыть ответ
3⁴ = 81. Без повторов четырёхбуквенных слов из трёх букв нет: на четвёртое место буквы не останется.
Сколько пятибуквенных слов из Т, О, Р, К, А содержат хотя бы одну О?
ОтветСкрыть ответ
5⁵ − 4⁵ = 3125 − 1024 = 2101: все слова минус слова без О.
Слова из А, К, О, Р, Т по алфавиту. Какой номер у слова ААААК?
ОтветСкрыть ответ
2: это запись 00001 в пятеричной системе, значение 1, номер на единицу больше.
Слова длины 20 из шести букв. Успеет ли перебор product?
ОтветСкрыть ответ
Нет: 6²⁰ ≈ 3,7 · 10¹⁵ слов. Нужно считать умножением или хранить количества по состояниям.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Коды Лены
Лена составляет 6-буквенные коды из букв Ф, И, Л, Ь, М. Каждую букву можно использовать любое количество раз, при этом код не может начинаться с буквы Ь, а буква Ф должна встретиться ровно один раз. Сколько различных кодов может составить Лена?
Введите число.
Подсказка
Разбери случаи по первой букве.
Решение
Если первая буква Ф, остальные пять мест — из четырёх других букв: 4⁵ = 1024. Если первая — И, Л или М, Ф стоит на одном из пяти мест, остальные четыре — из четырёх букв без Ф: 3 · 5 · 4⁴ = 3840. Всего 4864.
Решение программой
from itertools import product count = 0for letters in product('ФИЛЬМ', repeat=6): word = ''.join(letters) if word[0] != 'Ь' and word.count('Ф') == 1: count += 1print(count)Ответ: 4864
Чередование чётности, различные цифры
Сколько существует девятеричных пятизначных чисел, все цифры которых различны и никакие две чётные или две нечётные цифры не стоят рядом?
Введите число.
Подсказка
Две схемы чередования; ноль не на первом месте.
Решение
Чётных цифр пять (0, 2, 4, 6, 8), нечётных четыре. Схема «ч н ч н ч»: первая чётная не ноль — 4 варианта, дальше 4, 4, 3, 3: 4 · 4 · 4 · 3 · 3 = 576. Схема «н ч н ч н»: 4 · 5 · 3 · 4 · 2 = 480. Всего 1056.
Решение программой
from itertools import product count = 0for d in product(range(9), repeat=5): if ( d[0] != 0 and len(set(d)) == 5 and all(d[i] % 2 != d[i + 1] % 2 for i in range(4)) ): count += 1print(count)Ответ: 1056
Одна цифра A и не более двух малых
Сколько существует 11-ричных шестизначных чисел, в записи которых ровно одна цифра A и не более двух цифр с числовым значением меньше 3?
Введите число.
Подсказка
Цифра A — значение 10, «меньше 3» — d < 3.
Решение
Программа перебирает шестизначные 11-ричные числа: цифра A — значение 10, «меньше 3» — d < 3; подходит 469 567 чисел.
Решение программой
from itertools import product count = 0for d in product(range(11), repeat=6): if ( d[0] != 0 and d.count(10) == 1 and sum(x < 3 for x in d) <= 2 ): count += 1print(count)Ответ: 469567
Слово под номером 444
Все 5-буквенные слова, составленные из букв Ш, А, Р, Ф, записаны в алфавитном порядке и пронумерованы, начиная с 1. Какое слово стоит под номером 444?
Введите слово заглавными буквами.
Подсказка
Алфавит по порядку: А, Р, Ф, Ш.
Решение
По алфавиту буквы идут А, Р, Ф, Ш — цифры 0–3. 444 − 1 = 443 = 12323₄: цифры 1, 2, 3, 2, 3 — буквы Р, Ф, Ш, Ф, Ш.
Решение программой
alphabet = 'АРФШ'n = 444 - 1word = ''for _ in range(5): word = alphabet[n % 4] + word n //= 4print(word)Ответ: РФШФШ
Последнее слово с чётным номером
Все 6-буквенные слова, составленные из букв П, О, Л, Е, Т, записаны в алфавитном порядке и пронумерованы, начиная с 1. Под каким номером стоит последнее слово с чётным номером, которое не начинается с буквы О, содержит ровно две буквы Л и не содержит двух букв Е, стоящих рядом?
Введите число.
Подсказка
Номер и условия — раздельно.
Решение
Алфавит по порядку — Е, Л, О, П, Т. Программа запоминает последнее слово с чётным номером, которое не начинается с О, содержит ровно две Л и не содержит двух Е подряд, — ТТТПЛЛ с номером 15582.
Решение программой
from itertools import product last = Nonefor number, letters in enumerate( product('ЕЛОПТ', repeat=6), start=1): word = ''.join(letters) if ( number % 2 == 0 and word[0] != 'О' and word.count('Л') == 2 and 'ЕЕ' not in word ): last = numberprint(last)Ответ: 15582