ЕГЭ информатика 8 задание разбор, теория, как решать.
Задание 8. Перебор слов и чисел (itertools)
В заданиях №8 нужно рассматривать все возможные слова или числа, составленные из заданных символов.
Чтобы не делать сотни вложенных циклов, в Python удобно использовать модуль itertools.
1. Когда использовать itertools.product
Используем, если символы (буквы или цифры) могут повторяться.
Пример:
|
1 2 3 4 5 |
from itertools import product for w in product('AKOPCT', repeat=5): print(''.join(w)) |
Эта программа создаёт все 5-буквенные слова из букв A, K, O, P, C, T в алфавитном порядке —
точно так, как в условии ЕГЭ.
Такая конструкция заменяет 5 вложенных циклов:
|
1 2 3 4 5 6 7 |
for a in 'AKOPCT': for b in 'AKOPCT': for c in 'AKOPCT': for d in 'AKOPCT': for e in 'AKOPCT': ... |
Каждый элемент — это кортеж, например ('A','A','O','K','T'), поэтому мы соединяем буквы: ''.join(w).
2. Когда использовать itertools.permutations
Используем, если все символы должны быть различными.
Пример:
|
1 2 3 4 5 |
from itertools import permutations for w in permutations('0123456789', r=4): print(''.join(w)) |
Этот код создаёт все четырёхзначные числа без повторяющихся цифр.
Если нельзя, чтобы число начиналось с нуля — добавляем условие if w[0] != '0'.
3. Типичные условия в задачах
- Начинается / не начинается с определённой буквы:
w[0] != 'A' - Заканчивается / не заканчивается на букву:
w[-1] != 'T' - Содержит ровно k символов X:
w.count('O') == k - Не содержит символ X:
'X' not in w - Все символы различны:
len(set(w)) == len(w) - Нет подряд одинаковых:
all(w[i] != w[i+1] for i in range(len(w)-1))
4. Пример: базовый шаблон для всех вариантов
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
from itertools import product alphabet = 'AKOPCT' n = 5 count = 0 for word in product(alphabet, repeat=n): count += 1 w = ''.join(word) if count % 2 == 0 and w.count('O') == 2 and w[0] not in 'ACT': last_num = count last_word = w print(last_num, last_word) |
5. Пример с системами счисления
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
from itertools import product k = 0 for s in product('0123456789ab', repeat=5): # 12-ричная система w = ''.join(s) if w[0] == '0': continue if w.count('7') != 1: continue if w.count('9') + w.count('a') + w.count('b') > 3: continue k += 1 print(k) |
6. Пример с перестановками (все цифры разные)
|
1 2 3 4 5 6 7 8 9 10 |
from itertools import permutations k = 0 for p in permutations('0123456789', r=4): if p[0] == '0': continue if all((int(p[i]) + int(p[i+1])) % 2 != 0 for i in range(3)): k += 1 print(k) |
Ответ: 720
7. Вывод
itertools.product— для слов с повторениями;itertools.permutations— для слов/чисел с разными символами;- все фильтры пишутся простыми
if-условиями; - порядок символов в
product()определяет алфавитный порядок слов.