Библиотека питон для егэ - Помощь в подготовке к экзаменам и поступлению

Документация

Библиотека работает в Python 3.6+

Немного терминологии

Модуль — это файл с расширением .py, находящийся в библиотеке.

Например, модуль constants — это файл constants.py.

Модуль decorators

1. Декоратор cache

Для чего: мемоизация работы функции.

Пример использования:

from infEGE import cache

@cache
def fib(n):
    if n in {0,1}:
        return 1
    return fib(n - 1) + fib(n - 2)

fib(50)

Если убрать @cache, то вычисляться будет очень долго.

Модуль constants

Для чего: константы для использования в алгоритмах.

Содержимое:

E = 2.718281828459045
PI = 3.141592653589793
maxValue = float('inf')
minValue = float('-inf')

Модуль algebra_logic

1. Функция print_true_table

Синтаксис: print_true_table(variables: str, expretion: str, value: Union[int, bool, ‘all’] = ‘all’) -> None

Для чего:

Вывод таблицы истинности лог.функции expretion от переменных variables.

Если value='all', выводятся все строки таблицы;

Если value=1 или True, выводятся строки таблицы, где функция истинна;

Если value=0 или False, выводятся строки таблицы, где функция ложна.

В качестве лог.операций можно использовать обычные операции Python
или такие эквиваленты:
{"&": " and ", "|": " or ", "~": " not ", "->": "<="}.

Пример использования #1:

from infEGE import print_true_table

print_true_table("xy", "x->y", 1)

Вывод:

Внимание: в Python приоритет <= выше, чем and, or, not! Ставьте скобки!

Пример использования #2:

from infEGE import print_true_table

print_true_table("xy", "x&(y|x)|y", 0)

Вывод:

xy F
00 0

Пример использования #3:

from infEGE import print_true_table

print_true_table("xzy", "x or z and (y or not x)")

Вывод:

Модуль combinatorics

1. Функция permutation_with_repeat

Синтаксис: permutation_with_repeat(seq: Union[list, tuple, str], repeat: int = 1)

Для чего:

Возвращает перестановки элкементов итерируемого
обьекта seq с repeat повторениями.

Пример использования:

from infEGE import permutation_with_repeat

for el in permutation_with_repeat('123', 2):
    print(el)

Вывод:

('1', '1')
('1', '2')
('1', '3')
('2', '1')
('2', '2')
('2', '3')
('3', '1')
('3', '2')
('3', '3')

2. Функция permutations

Синтаксис: permutations(seq: Union[list, tuple, str]):

Для чего:

Возвращает перестановки элкементов итерируемого объекта seq.

Пример использования:

from infEGE import permutations

for el in permutations('abc'):
    print(el)

Вывод:

abc
acb
bac
bca
cab
cba

Модуль lists_and_other

1. Функция prod

Синтаксис: prod(seq: Union[list, tuple, set]) -> Union[int, float]

Для чего:

Возввращает произведение элементов итерируемого объекта seq.

Пример использования:

from infEGE import prod

print(prod([5, 8, 6, 100, 54]))

Вывод:

Модуль string

1. Функция replacing

Синтаксис: replacing(string: str, substring: str, new_string: str, mode: str = ‘обычно’, cnt: Union[int, str] = ‘all’) -> str

Для чего:

Возвращает строку string с заменённой подстрокой
substring на  подстроку new_string в количестве cnt.

Режим "обычно":
                замена стандартным replace

Режим "целиком":
                замена подстроки substring если она не
                является частью большей подстроки.

Пример использования #1:

from infEGE import replacing

print(replacing("Питон плохой тон", "тон", "нот"))

Вывод:

Пинот плохой нот

Пример использования #2:

from infEGE import replacing

print(replacing("Питон плохой тон", "тон", "нот", cnt=1))

Вывод:

Пинот плохой тон

Пример использования #3:

from infEGE import replacing

print(replacing("Питон плохой тон", "тон", "нот", "целиком"))

Вывод:

Питон плохой нот

2. Функция index_n

Синтаксис: index_n(string: str, substring: str, n: int = 1) -> int

Для чего:

Возвращает индекс n-го вхождения СЛЕВА подстроки
substring в строку string. Если такого вхождения
нет, возвращается -1000.

Пример использования #1:

from infEGE import index_n

print(index_n("01230123", "1"))

Вывод:

Пример использования #2:

from infEGE import index_n

print(index_n("01230123", "1", 2))

Вывод:

Пример использования #3:

from infEGE import index_n

print(index_n("01230123", "1", 3))

Вывод:

-1000

3. Функция is_number

Синтаксис: is_number(n: str) -> bool

Для чего:

Проверяет является ли строка n числом.
Если да возвращается True, иначе - False.

Пример использования #1:

from infEGE import is_number

print(is_number("23"))

Вывод:

True

Пример использования #2:

from infEGE import is_number

print(is_number("2n3"))

Вывод:

False

Модуль system_count

1. Функция to_base

Синтаксис: to_base(number: Union[int, str], old_base: int = 10, new_base: int = 10) -> Union[int, str]

Для чего:

Переводит число number с основанием old_base в число
с основанием new_base.

Пример использования #1:

from infEGE import to_base

print(to_base(5, new_base=2))

Вывод:

Пример использования #2:

from infEGE import to_base

print(to_base(15, new_base=16))

Вывод:

Пример использования #3:

from infEGE import to_base

print(to_base("FA32", old_base=17, new_base=10))

Вывод:

Пример использования #4:

from infEGE import to_base

print(to_base("FA32", old_base=17, new_base=6))

Вывод:

Модуль mathematics

1. Функция is_prime

Синтаксис: is_prime(n: int) -> bool

Для чего:

Если n - простое, то возващается True, иначе - False.

Пример использования #1:

from infEGE import is_prime

print(is_prime(5))

Вывод:

True

Пример использования #2:

from infEGE import is_prime

print(is_prime(25))

Вывод:

False

Пример использования #3:

from infEGE import is_prime

print(is_prime(1))

Вывод:

False

2. Функция is_even

Синтаксис: is_even(n: int) -> bool

Для чего:

Если n - чётно, то возващается True, иначе - False.

Пример использования #1:

from infEGE import is_even

print(is_even(12))

Вывод:

True

Пример использования #2:

from infEGE import is_even

print(is_even(25))

Вывод:

False

3. Функция is_odd

Синтаксис: is_odd(n: int) -> bool

Для чего:

Если n - нечётно, то возващается True, иначе - False.

Пример использования #1:

from infEGE import is_odd

print(is_odd(12))

Вывод:

False

Пример использования #2:

from infEGE import is_odd

print(is_odd(25))

Вывод:

True

4. Функция divided

Синтаксис: divided(n: int, d: int) -> bool

Для чего:

Если n нацело делится на d, то возвращается True, иначе - False.

Пример использования #1:

from infEGE import divided

print(divided(12, 5))

Вывод:

False

Пример использования #2:

from infEGE import divided

print(divided(121, 11))

Вывод:

True

5. Функция not_divisible

Синтаксис: not_divisible(n: int, d: int) -> bool

Для чего:

Если n не делится нацело на d, то возвращается True, иначе - False.

Пример использования #1:

from infEGE import not_divisible

print(not_divisible(12, 5))

Вывод:

True

Пример использования #2:

from infEGE import not_divisible

print(not_divisible(121, 11))

Вывод:

False

6. Функция factorial

Синтаксис: factorial(n: int) -> int

Для чего:

Возвращает n! (0! = 1)

Пример использования:

from infEGE import factorial

print(factorial(6))

Вывод:

7. Функция factorize

Синтаксис: factorize(number: int) -> list

Для чего:

Возвращает разложение числа number на простые множители в list.

Пример использования #1:

from infEGE import factorize

print(factorize(1))

Вывод:

[]

Пример использования #2:

from infEGE import factorize

print(factorize(11))

Вывод:

[11]

Пример использования #3:

from infEGE import factorize

print(factorize(55))

Вывод:

[5, 11]

8. Функция divisors

Синтаксис: divisors(n: int) -> list

Для чего:

Возвращает все натуральные делители числа n на интервале (1; n).

Пример использования #1:

from infEGE import divisors

print(divisors(1))

Вывод:

[]

Пример использования #2:

from infEGE import divisors

print(divisors(720))

Вывод:

[2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360]

9. Функция fib

Синтаксис: fib(n: int) -> int

Для чего:

Возвращает n-ый член последовательности Фибоначчи. Нумерация с 0.

Пример использования #1:

from infEGE import fib

print(fib(0))

Вывод:

Пример использования #2:

from infEGE import fib

print(fib(1))

Вывод:

Пример использования #3:

from infEGE import fib

print(fib(2))

Вывод:

Пример использования #4:

from infEGE import fib

print(fib(3))

Вывод:

Пример использования #5:

from infEGE import fib

print(fib(2001))

Вывод:

6835702259575806647045396549170580107055408029365524565407553367798082454408054014954534318953113802726603726769523447478238192192714526677939943338306101405105414819705664090901813637296453767095528104868264704914433529355579148731044685634135487735897954629842516947101494253575869699893400976539545740214819819151952085089538422954565146720383752121972115725761141759114990448978941370030912401573418221496592822626

Примечание: Данный алгоритм работает быстрее рекурсивного! Асимптоматика: O(N)

Источник

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

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

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

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

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

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

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

from itertools import product, permutations

product

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

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. Написание кода не займет много времени, зато будет уверенность в ручном решении.

Источник

Доброго времени суток каждому жителю Хабрвилля! Давненько я не писал статей! Пора это исправить!

В сегодняшней статье поговорим о насущной для многих выпускников школ теме — ЕГЭ. Да-да-да! Я знаю, что Хабр — это сообщество разработчиков, а не начинающих айтишников, но сейчас ребятам как никогда нужна поддержка именно сообщества. Ребят опять посадили на дистант. Пока не ясно на какой период, но уже сейчас можно сказать, что ЕГЭ по информатике будет на компьютерах и его можно зарешать при помощи языка Python.

Вот я и подумал, чтобы не получилось как в песне, стоит этим заняться. Я расскажу про все задачи первой части и их решения на примере демо варианта ЕГЭ за октябрь.

Всех желающих — приглашаю ниже!

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

В 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).

Задача 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) #Выводим результат

Результат:

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

Задача 5

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

Задача 6

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

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

Задача 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 ** 2017 - 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 — позиция. Позиция рассчитывается по таблице:

	Игра	Петя	Ваня	Петя	Ваня	Петя
p	1	2	3	4	5	6

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

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

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

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)

Отличия:

Выиграл Петя, соответственно, позиция 4
Так как Петя не может выиграть за один ход — он выигрывает за 2 хода (and, а не or на нечётных позициях (играх Пети))
Убрали 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 отличия:

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

Задача 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? Оставлю этот вопрос на ваше голосование.

Всем удачи!

Источник