🎯 До ЕГЭ по информатике:
--дней
:
--часов
:
--минут
:
--секунд
1

Графы и таблицы

Сопоставь буквы графа с номерами в таблице. Используй permutations для автоматического подбора.

from itertools import *

# Тут пишем связи из таблицы (построчно)
a = '478 38 256 15 34 37 168 127'.split()
# Тут пишем связи из графа (в любом порядке)
s = 'DE DG GC GA BC FB FE FH BH AH'.split()
print('1 2 3 4 5 6 7 8'
...
2

Таблицы истинности

Два способа: через itertools.product или вложенные циклы. Подбираем пропуски в таблице.

# Способ 1 — itertools
from itertools import *

def f(x, y, z, w):
    # тут пишем логическое условие из задачи
    return ((y and (x == (not z))) <= w) and (z <= y)

for x1, x2, x3, x4, x5 in product([0, 1], repeat=5):

...
4

Кодирование (дерево Фано)

Условие Фано: ни одно слово не начало другого. Строим дерево и находим код.

5

Системы счисления

Перевод между системами, операции с цифрами. Функция перевода в любую СС до 36.

# Функция перевода в любую СС (вместо X — основание)
def tro(n):
    s = ''
    while n > 0:
        s = str(n%X) + s
        n = n // X
    return s

# Питоновские функции перевода
x = bin(n)[2:]    # в 2-ю
x = oct(n)[2
...
6

Черепашка (Turtle)

Рисуем алгоритм, считаем точки и площадь. Помним про объединение и пересечение.

from turtle import *
tracer(0)          # отключаем анимацию
m = 15             # масштаб
screensize(2000, 2000)

# Переписываем алгоритм из задачи
for i in range(4):
    fd(3 * m)
    lt(270)
    fd(5 * m)
    rt(90)

#
...
7

Звук и изображения

Формулы: I = d × k × t × i. Часто округление в меньшую сторону для изображений.

# ===== ЗВУК =====
# I = d * k * t * i
# d = частота дискретизации, В ГЕРЦАХ
# i = разрешение (бит)
# k = каналы (2-стерео, 1-моно, 4-квадро)
# t = время в СЕКУНДАХ

I = 967 * 1024 * 1024 * 8  # объём в битах
t = I / (4 
...
8

Комбинаторика

Product — с повторениями, permutations — без. Проверки на условия.

from itertools import *
# С повторениями
for i in product('123', repeat=3):
    x = ''.join(i)
# БЕЗ повторений
for i in permutations('123', r=3):
    x = ''.join(i)

# Проверки
if x[0] != '0':           # не начинается 
...
9

Электронные таблицы (CSV)

Открываем файл, парсим строки. Ищем повторяющиеся и уникальные элементы.

f = open('9.txt')
for s in f:
    a = [int(x) for x in s.split()]  # или split(';')
    
    # Частые проверки
    povt = [x for x in a if a.count(x) == 2]
    razl = [x for x in a if a.count(x) == 1]
    kr5 = [x for x 
...
10

Поиск информации

Поиск в текстовых файлах, подсчёт вхождений слов.

import os
k = 0
for f in os.listdir('.'):
    if f.endswith('.txt'):
        with open(f) as fh:
            for line in fh:
                k += line.lower().count('слово')
print(k)
11

Кодирование информации

I = i × k, N = 2^i. Округление в большую или меньшую сторону.

from math import *
for n in range(1, 2158 + 1):
    i = ceil(log2(n))
    ves = ceil((i * 377) / 8)
    if 23155 * ves > 5536 * 1024:
        print(n)
        break
13

IP-адреса и маски

Адрес сети = IP & Маска. Библиотека ipaddress. 5 типов задач.

from ipaddress import *
# Создание сети
net = ip_network('1.2.3.4/255.255.255.192', 0)
net = ip_network('1.2.3.4/26', 0)  # или с префиксом
print(net)                # сеть / кол-во единиц
print(net[0])             # адр
...
14

Системы счисления (сложные)

Перевод в любую СС, уравнения с неизвестными цифрами.

alphabet = sorted('0123456789QWERTYUIOPASDFGHJKLZXCVBNM')
def my_convert(number, system):
    result = ''
    while number > 0:
        result += alphabet[number % system]
        number //= system
    return result[::-1
...
15

Логические выражения

Проверка условий для всех x. Поразрядная конъюнкция. Отрезки.

# Базовый
for a in range(1, 1500):
    if all(((x > 56) or (y >= x) or (3*x - y < a))
           for x in range(10000) for y in range(10000)):
        print(a)
        break

# Поразрядная конъюнкция
for a in range(1, 10
...
16

Рекурсия

Три способа: рекурсия, кэширование (lru_cache), мемоизация через список.

# Способ 1 — рекурсия (на слабых компах не потянет)
from sys import *
setrecursionlimit(1000000)
def f(n):
    if n < 5: return n
    return 2 * n * f(n - 4)
print((f(13766) - 9*f(13762)) // f(13758))

# Способ 2 — кэшир
...
17

Числовые последовательности

Обработка файла, пары и тройки чисел. Поиск минимумов и максимумов.

f = open('17.txt')
a = [int(x) for x in f]

# пары (a[i], a[i+1])
for i in range(len(a) - 1):
    pass
# тройки (a[i], a[i+1], a[i+2])
for i in range(len(a) - 2):
    pass

# число из 5 цифр:
if len(str(abs(a[i]))) == 5

...
19

Теория игр — №19

1 куча, 2 кучи, отрезки. Минимальное s для победы за 2 хода.

# 1 куча
def f(s, m):
    if s >= 132: return m % 2 == 0
    if m == 0: return 0
    h = [f(s+3, m-1), f(s+6, m-1), f(s*3, m-1)]
    return any(h) if m % 2 != 0 else all(h)
print('#19', min(s for s in range(1,132) if f(s
...
20

Теория игр — №20

Список начальных позиций, при которых 1-й не выигрывает за 1 ход, но выигрывает за 3.

from functools import lru_cache

@lru_cache(None)
def f(s, m):
    if s >= 132: return m % 2 == 0
    if m == 0: return False
    h = [f(s+3, m-1), f(s+6, m-1), f(s*3, m-1)]
    return any(h) if m % 2 != 0 else all(h)

#
...
21

Теория игр — №21

Минимальное начальное число, при котором 2-й побеждает за 2 хода, но 1-й выигрывает за 4.

from functools import lru_cache

@lru_cache(None)
def f(s, m):
    if s >= 132: return m % 2 == 0
    if m == 0: return False
    h = [f(s+3, m-1), f(s+6, m-1), f(s*3, m-1)]
    return any(h) if m % 2 != 0 else all(h)

#
...
23

Количество программ

Рекурсивный подсчёт путей. Промежуточные, ограничения, последняя команда.

# Базовый
def f(x, y):
    if x > y: return 0
    if x == y: return 1
    return f(x+1, y) + f(x*2, y)

# Промежуточные числа — перемножаем
print(f(4,8) * f(8,10) * f(10,15))

# С ограничением (запрет числа)
def f(x, y):
...
24

Обработка строк

3 способа: счётчик, регулярки, двойной цикл Кабанова.

f = open('24.txt')
s = f.readline()

# Способ 1 — счётчик
k = m = 0
for i in range(len(s)-1):
    if s[i] in 'ABC' and s[i+1] not in 'ABC':
        k += 1
        m = max(k, m)
    else:
        k = 0
print(m)

# Способ 
...
25

Делимость и делители

Простые, делители, простые делители. Маски fnmatch.

# Простое число
def prost(n):
    return n > 1 and all(n%d != 0 for d in range(2, int(n**0.5)+1))

# Все делители
def delit(n):
    a = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            a.add
...
27

Кластеризация

Разбиение на кластеры, поиск центра тяжести. Евклидово расстояние.

from math import dist
cl1 = []; cl2 = []
for i in open('27'):
    x, y = [float(x) for x in i.split()]
    if y < 5: cl1.append([x,y])
    if y > 5: cl2.append([x,y])

def center(cl):
    mn = []
    for p1 in cl:
      
...