Модуль itertools для решения задания 8 ЕГЭ по информатике — Личный сайт Рогова Андрея: информатика, программирование и робототехника

Быстрый перевод из системы в систему

В Python есть интересные функции bin(), oct() и hex(). Работают данные функции очень просто:

bin(156) #Выводит '0b10011100'
oct(156) #Выводит '0o234'
hex(156) #Выводит '0x9c'

Как вы видите, выводится строка, где 0b — означает, что число далее в двоичной системе счисления, 0o — в восьмеричной, а 0x — в шестнадцатеричной. Но это стандартные системы, а есть и необычные…

Давайте посмотрим и на них:

n = int(input()) #Вводим целое число
b = '' #Формируем пустую строку
while n > 0: #Пока число не ноль b = str(n % 2) b #Остатот от деления нужной системы (в нашем сл записываем слева n = n // 2 #Целочисленное деление
print(b) #Вывод

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

n = int(input()) #Вводим целое число
b = '' #Формируем пустую строку
while n > 0: #Пока число не ноль	if (n % 21) > 9: #Если остаток от деления больше 9...	if n % 21 == 10: #... и равен 10...	b = 'A' b #... запишем слева A	elif n % 21 == 11:#... и равен 11...	b = 'B' b#... запишем слева B
'''
И так далее, пока не дойдём до системы счисления -1 (я переводил в 21-ную систему и шёл до 20)
'''	elif n % 21 == 11:	b = 'B' b	elif n % 21 == 12:	b = 'C' b	elif n % 21 == 13:	b = 'D' b	elif n % 21 == 14:	b = 'E' b	elif n % 21 == 15:	b = 'F' b	elif n % 21 == 16:	b = 'G' b	elif n % 21 == 17:	b = 'H' b	elif n % 21 == 18:	b = 'I' b	elif n % 21 == 19:	b = 'J' b	elif n % 21 == 20:	b = 'K' b	else: #Иначе (остаток меньше 10)	b = str(n % 21) b #Остатот от деления записываем слева	n = n // 21 #Целочисленное деление
print(b) #Вывод

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

def convert_base(num, to_base=10, from_base=10): # Перевод в десятичную систему if isinstance(num, str): # Если число - строка, то ... n = int(num, from_base) # ... переводим его в нужную систему счисления else: # Если же ввели число, то ... n = int(num) # ... просто воспринять его как число # Перевод десятичной в 'to_base' систему alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" # Берём алфавит if n < to_base: # Если число меньше системы счисления в которую переводить... return alphabet[n] # ... вернуть значения номера в алфавите (остаток от деления) else: # Иначе... return convert_base(n // to_base, to_base) alphabet[n % to_base] # ... рекурсивно обратиться к функии нахождения остатка

Вызвав функцию вывода print(convert_base(156, 16, 10)) мы переведём 156 из 10 в 16 систему счисления, а введя print(convert_base(’23’, 21, 4)) переведёт 23 из 4-ичной в 21-ичную систему (ответ: B).

Вероятность событий

✍ Решение:

Видеоразбор задания:

📹 Видеорешение на RuTube здесь (теоретическое решение)

Двоичное кодирование сообщений (равновероятностные события)

При вычислении количества информации в сообщении для равновероятностных событий, общее количество которых равно N, используется формула:

N = 2L

* следует иметь в виду, что также приняты следующие обозначения: Q = 2k

Решение:

Задача 12

В очередной раз, просто заменим слова на код:

a = '9' * 1000
while '999' in a or '888' in a:	if '888' in a:	a = a.replace('888', '9', 1)	else:	a = a.replace('999', '8', 1)
print(a)

Задача 14

Компьютер железный, он всё посчитает:

a = 4 ** 2020 2 ** 2022 - 15
k = 0
while a > 0: if a % 2 == 1:	k = 1 a = a // 2
print(k)

Задача 16

Опять же, просто дублируем программу в python:

def F(n): if n > 0: F(n // 4) print(n) F (n - 1)
print(F(5))

Результат:

Задача 17

Задача с файлом. Самое сложное — достать данные из файла. Но где наша не пропадала?!

with open("17.txt", "r") as f: #Открыли файл 17.txt для чтения text = f.read() #В переменную text запихнули строку целиком
a = text.split("n") #Разбили строку энтерами (n - знак перехода на новую строку)
k = 0 #Стандартно обнуляем количество
m = -20001 #Так как у нас сумма 2-ух чисел и минимальное равно -10000, то минимум по условию равен -20000, поэтому...
for i in range(len(a)): #Обходим все элементы массива	if (int(a[i - 1]) % 3 == 0) or (int(a[i]) % 3 == 0): #Условное условие	k = 1 #Счётчик	if int(a[i - 1]) int(a[i]) > m: #Нахождение минимума	m = int(a[i - 1]) int(a[i])
print(k, m) #Вывод

Немного пояснений. Функция with() открывает файл считывает данные при помощи функции read() и закрывает файл. В остальном — задача стандартна.

Задача 19, 20 и 21

Все три задачи — задачи на рекурсию. Задачи идентичны, а вопросы разные. Итак, первая задача:

Пишем рекурсивную функцию и цикл перебора S:

def f(x, y, p): #Рекурсивная функция	if x y >= 69 or p > 3: #Условия завершения игры	return p == 3	return f(x 1, y, p 1) or f(x, y 1, p 1) or f(x * 2, y, p 1) or f(x, y * 3, p 1) #Варианты действий
for s in range (1, 58 1): #Перебор S	if f(10, s, 1): #Начали с 10 камней	print(s)	break

Немного пояснений. В рекурсивной функции существует 3 переменные x — число камней в первой куче, y — число камней во второй куче, p — позиция. Позиция рассчитывается по таблице:

Далее — всё по условию задачи.

Вторая задача на теорию игр:

Все отличия в рамке. Ну и код, соответственно, не сильно отличается:

def f(x, y, p): #Рекурсивная функция	if x y >= 69 or p > 4: #Условия завершения игры	return p == 4	if p % 2 != 0:	return f(x 1, y, p 1) or f(x, y 1, p 1) or f(x * 2, y, p 1) or f(x, y * 3, p 1) #Варианты действий	else:	return f(x 1, y, p 1) and f(x, y 1, p 1) and f(x * 2, y, p 1) and f(x, y * 3, p 1) #Варианты действий
for s in range (1, 58 1): #Перебор S	if f(10, s, 1): #Начали с 10 камней	print(s)

Отличия:

1. Выиграл Петя, соответственно, позиция 4

2. Так как Петя не может выиграть за один ход — он выигрывает за 2 хода (and, а не or на нечётных позициях (играх Пети))

3. Убрали break, так как нам нужны все S, а не единственный

Последняя вариация задачи:

Сразу код:

def f(x, y, p): #Рекурсивная функция	if x y >= 69 or p > 5: #Условия завершения игры	return p == 3 or p == 5	if p % 2 == 0:	return f(x 1, y, p 1) or f(x, y 1, p 1) or f(x * 2, y, p 1) or f(x, y * 3, p 1) #Варианты действий	else:	return f(x 1, y, p 1) and f(x, y 1, p 1) and f(x * 2, y, p 1) and f(x, y * 3, p 1) #Варианты действий
for s in range (1, 58 1): #Перебор S	if f(10, s, 1): #Начали с 10 камней	print(s)

Ну и всего лишь 2 отличия:

1. Позиции 3 или 5, а не 4, так как выиграл Ваня

2. На второй ход выигрывает Ваня и нам нужно or и and поменять. Я заменил только кратность 2.

Задача 2

Все задания беру из первого октябрьского варианта (он же вариант № 9325894) с сайта Решу.ЕГЭ.

Решение данной задачи совсем простое: банальный перебор.

print('y', 'x', 'z', 'F') #Напечатаем заголовки таблицы
for y in range(2): #Берём все переменные и меняем их в циклах '0' и '1'	for x in range(2):	for z in range(2):	for w in range(2):	F = ((not x or y) == (not z or w)) or (x and w) #Записываем функцию	print(x, y, z, F) #Выводим результат

Результат:

Нам вывелась вся таблица истинности (1 = True, 0 = False). Но это не очень удобно. Обратите внимание, что в задании, функция равно 0, так и давайте подправим код:

print('y', 'x', 'z', 'F') #Напечатаем заголовки таблицы
for y in range(2): #Берём все переменные и меняем их в циклах '0' и '1'	for x in range(2):	for z in range(2):	for w in range(2):	F = ((not x or y) == (not z or w)) or (x and w) #Записываем функцию	if not F:	print(x, y, z, F) #Выводим результат

Результат:

Далее — простой анализ.

Задача 22

Ctrl C, Ctrl V — наше всё! 🙂

for i in range(1, 100000):	x = i	L = 0	M = 0	while x > 0 :	L = L 1	if (x % 2) != 0:	M = M x % 8	x = x // 8	if L == 3 and M == 6:	print(i)

Задача 23

Итак, код:

def f(x, y):	if x > y: #Перегнали цель	return 0	if x == y: #Догнали цель	return 1	if x < y: #Догоняем цель тремя методами	return f(x 1, y) f(x 2, y) f(x * 2, y)
print(f(3, 10) * f(10, 12)) #Прошло через 10, значит догнали 10 и от де догоняем 12

Так как в условии задачи мы увеличиваем число, но будем числа «догонять». Три метода описаны, ну а пройти через 10 — значит дойти до него и идти от него.

Собственно, это и есть вся первая часть ЕГЭ по информатике решённая на Python.

Ссылка на репозиторий со всеми программами:

Надеюсь, что смог помочь в своей статье выпускникам и готовящимся 😉

Остался один вопрос — нужен ли разбор второй части ЕГЭ по информатике на Python? Оставлю этот вопрос на ваше голосование.

Всем удачи!

Задача 5

Данная задача легко решается простой последовательностью действий в интерпретационном режиме:

Задача 6

Перепечатали и получили ответ:

s = 0
k = 1
while s < 66: k = 3 s = k
print(k)

Измерение количества информации

Для вычисления количества информации применяются несколько различных формул в зависимости от ситуации:

Количество информации и неравновероятные события

При использовании неравновероятного события, вероятность которого равна p, для вычисления количества информации используется формула:

i = -[log2p]

*квадратные скобки означают ближайшее целое, меньшее или равное значению выражения в скобках

Формула Хартли:

Алфавитный подход:

Информационный объем сообщения длиной L:

Количество информации и равновероятные события

При определении количества информации для равновероятностных событий могут понадобиться две формулы:

x = log2(1/p)

p(A) = m / n

Количество различных сообщений в алфавите разной мощности

Рассмотрим вариант с 5 буквами (мощность алфавита = 5), которые надо разместить в сообщении длиной 2 символа:

Найдем формулу для нахождения количества различных сообщений в алфавите различной мощности:

Пример: Сколько существует всевозможных трехбуквенных слов в английском языке?

Решение:

N = n1 * n2 * … * nL

Количество сообщений при различном вхождении (встречаемости) букв

Иногда в заданиях 8 приходится использовать формулу комбинаторики для проверки полученных результатов перебора. Число сочетаний из n элементов по k элементов:

[ C{binom{k}{n}}= frac{n!}{k!(n-k)!} ]

Факториал числа n:

n! = 1 * 2 * 3 * … * n

Пример: Сколько существует всевозможных четырехбуквенных слов в алфавите из 4 букв: А, Б, В, Г, если известно, что буква А встречается ровно два раза?

Решение:

Модуль itertools для решения задания 8 егэ по информатике — личный сайт рогова андрея: информатика, программирование и робототехника

Задание номер 8 — задание базового уровня сложности, выполнение которого предполагает знание о методах измерения количества информации и не требует использования специального ПО.

Зачастую в номере 8 мы можем встретить задания связанные с комбинаторикой — перестановками, количеством вариантов выборки и т.д. Для решения заданий такого типа можно приспособить модуль itertools языка python.

Сразу оговорюсь, что я не рекомендую решать задание именно таким способом. Я советую проверять свой ответ, полученный ручным решением. Написанная программа не должна быть единственным вариантом решения.

Модуль itertools доступен в питоне «из коробки», т.е. его нет необходимости устанавливать дополнительно. А значит, он будет доступен на экзамене.

Ссылка на документацию по модулю https://docs.python.org/3/library/itertools.html

Использованные в данной статье методы и функции доступны как минимум с версии питона 3.6

Для импорта необходимых функции необходимо их импортировать из модуля

from itertools import product, permutations

1. product

Позволяет получить прямое, или декартово произведеение двух множеств — множество, элементами которого являются все возможные упорядоченные пары элементов исходных множеств.

Про ЕГЭ:  Появились ли результаты ЕГЭ по математике в 2021 году

a = ‘AB’

b = ‘CD’

print(*product(a, b))

(‘A’, ‘C’) (‘A’, ‘D’) (‘B’, ‘C’) (‘B’, ‘D’)

Получение произведения двух множеств не очень актуально в 8 задании, но мы можем использовать другую возможность функции product: получение всевозможных комбинаций определенной длины для одного множества.

a = ‘AB’

print(*product(a, repeat=3))

(‘A’, ‘A’, ‘A’) (‘A’, ‘A’, ‘B’) (‘A’, ‘B’, ‘A’) (‘A’, ‘B’, ‘B’) (‘B’, ‘A’, ‘A’) (‘B’, ‘A’, ‘B’) (‘B’, ‘B’, ‘A’) (‘B’, ‘B’, ‘B’)

Мы получили всевозможные комбинации длины 3 для набора из двух букв АВ. Причем результат работы функции — набор кортежей.

Параметр repeat отвечает за длину слова.

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

Длина слова здесь 3, а набор букв — ШКОЛА. Получим всевозможные комбинации:

a = ‘ШКОЛА’

comb = product(a, repeat=3))

Осталось выбрать те, где буква К встречается ровно 1 раз.

Поскольку подсчет количества вхождений в кортеж организовать сложнее, чем в строке, здесь элементы кортежа «склеиваются» по пустой строке, образуя тем самым не кортеж, а строку. Метод count подсчитывает количество вхождений подстроки ‘K’.

Этот же код можно оформить в одну строку через списочное выражение

print(len([item for item in product(‘ШКОЛА’, repeat=3) if ”.join(item).count(‘К’) == 1]))

2. permutations

Позволяет получить всевозможные перестановки.

print(*permutations(‘ABC’))

(‘A’, ‘B’, ‘C’) (‘A’, ‘C’, ‘B’) (‘B’, ‘A’, ‘C’) (‘B’, ‘C’, ‘A’) (‘C’, ‘A’, ‘B’) (‘C’, ‘B’, ‘A’)

Это опять набор кортежей.

Рассмотрим такое задание с сайта kpolyakov.spb.ru

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

a = ‘КАПКАН’

comb = permutations(a)

И отбираем нужные варианты

Поскольку в слове КАПКАН есть повторяющиеся буквы А и К, мы должны поделить итоговое количество на 4 (дважды поделить на 2), поскольку с нашей точки зрения эти комбинации неотличимы друг от друга.

Другой способ убрать повторяющиеся комбинации — превратить набор перестановок в множество, которое в питоне исключает повторы

Так-же можно написать решение в одну строку

print(len([i for i in set(permutations(‘КАПКАН’)) if all(i[j] != i[j 1] for j in range(5))]))

Подведем итог. Задачи на составление слов путем выбора букв из набора или путем перестановки букв в слове можно решить с использованием модуля itertools. Написание кода не займет много времени, зато будет уверенность в ручном решении.

Объяснение темы

Рассмотрим кратко необходимые для решения 8 задания ЕГЭ понятия и формулы.

Сколько вариантов шифра или кодовых слов

✍ Решение:

Детальный теоретический разбор задания 8 ЕГЭ по информатике предлагаем посмотреть в видеоуроке:

📹 Видеорешение на RuTube здесь (теоретическое решение)

Сколько существует n-значных чисел, записанных в m-ной системе счисления

✍ Решение:

Список в алфавитном порядке

✍ Решение:

… (241,[У,У,У,У,А]) (242,[У,У,У,У,О]) (243,[У,У,У,У,У])