Python Handout · ⁨Раздаточный материал Python⁩

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

Функция print() выводит текст на экран. Это называется выводом. Текст внутри кавычек является строкой.

print("Hello, world!")
print("I am learning Python")

• Каждый print() начинает новую строку.
• Кавычки могут быть "double" или 'single' — оба варианта создают строку.
• Программа ничего не делает, пока вы её не запустите.

Комментарий начинается с ⟨⟩. Python игнорирует все после ⟨⟩ на этой строке. Комментарии объясняют ваш код людям; они не изменяют поведение кода.

Комментарий начинается со знака #. Python игнорирует всё после символа # в этой строке. Комментарии объясняют ваш код людям; они не изменяют поведение кода.

# This line is a note for humans
print("Hi")        # you can also comment at the end of a line

Хороший стиль делает код легким для чтения:

• Используйте понятные имена, которые указывают на смысл значения.
• Размещайте каждое утверждение на отдельной строке.
• Не добавляйте пробелы в начале обычной строки. В Python отступы (отступы) имеют специальное значение, поэтому неверный пробел вызывает ошибку.

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

Функция input() считывает текст, который вводит пользователь. Она всегда возвращает строку.

name = input("What is your name? ")
print("Hello, " + name)

• input() ожидает, пока пользователь введет данные и нажмет Enter.
• Сохраните введенный текст в переменной, чтобы использовать его позже.
• Поскольку input() возвращает строку, преобразуйте ее с помощью int(...) перед использованием, если вам нужно число.

Распространенные ошибки

• Забытые кавычки: print(Hello) ищет переменную с именем Hello и вызывает NameError. Текст требует кавычек: print("Hello").
• Случайный пробел в начале строки: Python читает отступы как структуру, поэтому вызывает IndentationError.
• Предположение, что input() возвращает число. Она всегда возвращает строку, поэтому оберните её в int(...) перед выполнением любых математических операций.

Переменная — это имя для значения. Создайте её с помощью =, которое называется присваиванием. Имя ставится слева; значение — справа.

age = 17
name = "Mei"
price = 9.99
print(age, name, price)

Теперь age хранит 17. Используйте имя везде, где требуется значение, и измените его позже:

age = 17
age = age + 1   # age is now 18
print(age)

• Знак = не означает «равно». Он означает «сохранить правую часть под левым именем».
• Чтобы проверить равенство двух значений, используйте == (см. ниже).

В Python два основных типа чисел. Целое число (int) — это целое число, например 17. Число с плавающей точкой (float) имеет десятичную точку, например 9.99.

Эти операторы работают с числами:

• / всегда возвращает float, поэтому 4 / 2 является 2.0.
• // и % идут вместе: 17 // 5 является 3, а 17 % 5 является 2.

Выражение — это всё, что имеет значение, например 3 + 4 * 2. Python использует стандартный порядок действий математики (* и / выполняются до + и -); добавьте скобки, чтобы упорядочить действия.

input() возвращает строку, поэтому преобразуйте её перед выполнением математики. Изменение значения из одного типа в другой называется преобразованием типов:

age = int("17")        # text "17" -> number 17
price = float("9.99")  # text -> 9.99
label = str(17)        # number -> text "17"
print(age, price, label)

• int("abc") вызывает ошибку, поэтому преобразовывайте только текст, похожий на число.
• Смешивание типов также вызывает ошибку: "age: " + 17 — это ошибка; напишите "age: " + str(17).

Булево значение — это одно из двух значений: True или False. Сравнение возвращает булево значение.

print(7 > 2)        # True
print(3 == 3.0)     # True
age = 20
print(age >= 18)    # True

Объединяйте сравнения с помощью and, or, not:

age = 20
print(age >= 13 and age <= 19)   # True only for a teenager

Распространенные ошибки

• / всегда возвращает float, даже если 4 / 2 является 2.0. Используйте //, когда вам нужно целое число.
• Использование = вместо ==: = присваивает значение, а == проверяет, равны ли два значения.
• Объединение строки и числа: "age: " + 5 вызывает TypeError. Сначала преобразуйте с помощью str(5).
• Floats неточны, поэтому 0.1 + 0.2 не является точно 0.3 — избегайте использования == на результатах float.

Строка — это текст в кавычках. Каждый символ имеет позицию, называемую индексом. Первый индекс равен 0, а не 1.

Прочитайте один символ с помощью квадратных скобок:

word = "Python"
print(word[0])    # P  (the first character)
print(word[2])    # t
print(len(word))  # 6  (how many characters)

• Нумерация начинается с 0, поэтому последний индекс равен len(word) - 1.
• Отрицательный индекс считает с конца: word[-1] — это последний символ.

word = "Python"
print(word[-1])   # n
print(word[-2])   # o

• Индекс, который слишком велик, вызывает ошибку (ошибка IndexError).

Срез берет часть строки. Напишите word[start:end]. Срез включает start, но останавливается перед end.

word = "Python"
print(word[0:3])   # Pyt   (positions 0, 1, 2)
print(word[2:5])   # tho

• Пропустите start, чтобы начать с 0; пропустите end, чтобы дойти до конца.

word = "Python"
print(word[:3])    # Pyt
print(word[3:])    # hon

• Третье число — это шаг. word[::-1] разворачивает строку.

print("Python"[::-1])   # nohtyP

Метод — это функция, принадлежащая значению. Вы вызываете его с помощью точки:

name = "mei chen"
print(name.upper())     # MEI CHEN
print(name.title())     # Mei Chen
print(len(name))        # 8

Строки неизменяемы: метод возвращает новую строку и никогда не изменяет исходную.

name = "mei"
print(name.upper())     # MEI  (the returned value)
print(name)             # mei  (the original is unchanged)

Распространенные методы (каждый возвращает новое значение):

Объединяйте строки с помощью +. Это называется конкатенацией:

first = "Mei"
last = "Chen"
print(first + " " + last)   # Mei Chen

f-строка构建文本从值。放f前引号，然后写{...}围绕一个值。

name = "Mei"
age = 17
print(f"{name} is {age} years old")   # Mei is 17 years old

• Любое выражение может находиться внутри фигурных скобок.
• {value:.2f} округляет до 2 знаков после запятой.

price = 9.5
print(f"Two cost {price * 2}")        # Two cost 19.0
print(f"Pi is about {3.14159:.2f}")   # Pi is about 3.14

Распространенные ошибки

• Строки нельзя изменить на месте: s[0] = "x" вызывает ошибку. Вместо этого создайте новую строку.
• Индексация начинается с 0; последний символ — s[-1], а s[len(s)] выходит за пределы диапазона.
• Срез s[a:b] включает a, но останавливается перед b.
• Методы строк возвращают НОВУЮ строку: s.upper() ничего не делает, если вы не сохраните результат.

Программа выбирает, что делать с if. Она выполняет отступленный блок только тогда, когда условие истинно. Строка if заканчивается двоеточием.

score = 72
if score >= 60:
    print("pass")
# pass

Добавьте elif (else-if) для дополнительных случаев и else для «всего остального». Python выполняет только первый истинный блок, а затем пропускает остальные.

score = 72
if score >= 80:
    print("A")
elif score >= 60:
    print("B")
else:
    print("fail")
# B

• Сравнивайте значения с помощью == (равно), != (не равно), <, >, <=, >=.
• Результат сравнения — логическое значение: либо True, либо False.

Объединяйте условия с помощью and, or, not. Оператор and требует истинности обеих сторон; оператор or требует истинности хотя бы одной стороны; оператор not инвертирует логическое значение.

age = 16
has_ticket = True
if age >= 18 and has_ticket:
    print("entry allowed")
else:
    print("entry refused")
# entry refused

• Используйте скобки для ясности порядка: (a or b) and c.

temp = 30
if temp > 25 and not temp > 35:
    print("warm but ok")
# warm but ok

Распространенные ошибки

• Пишите elif, а не else if.
• Каждая строка if / elif / else заканчивается двоеточием :, а её тело должно быть отступлено.
• if x = 5: вызывает ошибку — используйте == для сравнения.
• else не принимает условие; только if и elif это делают.

Цикл повторяет код. Цикл for выполняется по одному разу для каждого элемента последовательности. range(n) выдает числа от 0 до n - 1.

for i in range(5):
    print(i)
# 0, then 1, 2, 3, 4 (each on its own line)

• range(a, b) идет от a до (не включая) b.
• range(a, b, step) добавляет шаг на каждой итерации.

for n in range(2, 11, 2):
    print(n)        # 2 4 6 8 10

Чтобы накапливать результат в цикле, создайте переменную до цикла, а затем обновляйте её на каждом шаге. Это паттерн аккумуляторa.

total = 0
for n in range(1, 6):
    total = total + n
print(total)        # 15

• Та же идея используется для подсчета количества элементов, соответствующих условию.

count = 0
for letter in "banana":
    if letter == "a":
        count = count + 1
print(count)        # 3

Цикл while повторяется пока условие остается истинным. Измените что-то внутри, иначе он никогда не остановится — бесконечный цикл.

n = 1
while n <= 3:
    print(n)
    n = n + 1
# 1 2 3

• break немедленно выходит из цикла.

total = 0
while True:
    total = total + 10
    if total >= 30:
        break
print(total)        # 30

Цикл внутри другого цикла — это вложенный цикл. Внутренний цикл полностью выполняется для каждой итерации внешнего цикла.

for row in range(3):
    line = ""
    for col in range(3):
        line = line + "*"
    print(line)
# ***
# ***
# ***

Распространенные ошибки

• Диапазон range(n) идет от 0 до n - 1, а не от 1 до n — это классическая ошибка смещения на единицу (off-by-one error).
• Изменение списка во время обхода пропускает элементы; обходите копию, если необходимо удалять вещи.
• Забыв изменить переменную цикла в while приведет к бесконечному выполнению.
• Отступы определяют, что находится внутри цикла; неправильно отступленная строка выполнится только один раз после цикла.

Список хранит множество значений в порядке, внутри []. Каждый элемент имеет индекс (от 0).

scores = [88, 71, 95]
print(scores[0])      # 88
print(len(scores))    # 3
scores.append(60)     # add to the end
print(scores)         # [88, 71, 95, 60]

• Измените элемент по его индексу: scores[1] = 100.
• Список может расти и уменьшаться; строка — нет.

Обычные инструменты списков:

Обход списка означает посещение каждого элемента. Цикл for делает это без необходимости в индексе.

scores = [88, 71, 95]
total = 0
for s in scores:
    total = total + s
print(total)          # 254

• Используйте enumerate, когда также нужен индекс.

for i, name in enumerate(["a", "b"]):
    print(i, name)    # 0 a  /  1 b

Список 2 — это список списков, то есть сетка из строк и столбцов. Используйте два индекса: grid[row][col].

grid = [[1, 2, 3],
        [4, 5, 6]]
print(grid[0][2])     # 3
print(grid[1][0])     # 4

• Вложенный цикл посещает каждую ячейку.

grid = [[1, 2], [3, 4]]
for row in grid:
    for value in row:
        print(value, end=" ")
print()               # 1 2 3 4

Генератор списка создает новый список в одну строку: [expression for item in sequence].

squares = [x * x for x in range(5)]
print(squares)        # [0, 1, 4, 9, 16]

• Добавьте if, чтобы оставить только некоторые элементы.

evens = [n for n in range(10) if n % 2 == 0]
print(evens)          # [0, 2, 4, 6, 8]

Кортеж — это фиксированная последовательность в круглых скобках. Его нельзя изменить после создания — используйте его для связанных значений и распакуйте в имена.

point = (3, 4)
x, y = point            # unpacking
print(x, y)             # 3 4

Функция, которая должна вернуть два результата, возвращает кортеж:

def min_max(nums):
    return min(nums), max(nums)

lo, hi = min_max([5, 2, 9])
print(lo, hi)           # 2 9

Множество хранит каждое значение один раз, без порядка. Оно идеально подходит для удаления дубликатов и быстрых проверок принадлежности.

votes = ["red", "blue", "red", "green", "red"]
colours = set(votes)
print(len(colours))         # 3  (duplicates removed)
print("blue" in colours)    # True

Распространенные ошибки

• b = a не копирует список: оба имени указывают на один и тот же список, поэтому изменение одного меняет и другое. Используйте a.copy() или a[:].
• Последний элемент — это a[-1]; a[len(a)] выходит за пределы диапазона.
• append добавляет ОДИН элемент; используйте extend или +, чтобы присоединить другой список.
• Создание сетки с помощью [[0]*3]*3 создает три копии одной и той же строки. Создавайте строки в цикле вместо этого.
• Кортеж с одним элементом требует запятой: (5,), а не (5).
• Множество не имеет порядка и дубликатов, поэтому вы не можете обратиться к нему по индексу с помощью s[0].

Словарь (dict) хранит пары ключ → значение. Вы ищете значение по его ключу, а не по числовому индексу.

student = {"name": "Mei", "score": 88}
print(student["name"])     # Mei
print(student["score"])    # 88

Добавление и обновление

Присвойте значение ключу, чтобы добавить его или изменить существующий.

student = {"name": "Mei"}
student["score"] = 88      # add a new key
student["score"] = 90      # update the value
print(student)             # {'name': 'Mei', 'score': 90}

Проверка и обход

Используйте in для проверки наличия ключа. Обходите ключи или .items(), чтобы получить и ключ, и значение.

student = {"name": "Mei", "score": 90}
print("score" in student)  # True
for key, value in student.items():
    print(key, "=", value)
# name = Mei
# score = 90

• .get(key, default) возвращает значение по умолчанию, если ключ отсутствует — без ошибки.

student = {"name": "Mei"}
print(student.get("age", 0))   # 0

Классический экзаменационный паттерн — подсчет частоты появления каждого значения:

word = "banana"
counts = {}
for letter in word:
    counts[letter] = counts.get(letter, 0) + 1
print(counts)   # {'b': 1, 'a': 3, 'n': 2}

• .get(letter, 0) предоставляет ⟨0⟩ при первом виде ключа, поэтому нет KeyError.

Распространенные ошибки

• Чтение отсутствующего ключа через d[key] вызывает KeyError; используйте d.get(key) или сначала проверьте if key in d.
• Повторное присвоение ⟨d[key]⟩ перезаписывает старое значение — ключи уникальны.
• Ключи должны быть неизменяемыми, например строкой или числом — список не может быть ключом.

Функция — это именованный блок кода, который можно переиспользовать. Определите её с помощью def, затем вызовите по имени.

def greet():
    print("Hello!")

greet()        # Hello!
greet()        # Hello!

• Код внутри выполняется только при вызове функции.

Функция может вернуть значение с помощью return. После этого вызов функции заменяется этим значением.

def square(n):
    return n * n

print(square(5))          # 25
print(square(3) + 1)      # 10

• return немедленно завершает выполнение функции. Функция без return возвращает None.

Параметр — это имя в def. Аргумент — это значение, которое вы передаёте.

def power(base, exp):         # base, exp are parameters
    return base ** exp

print(power(2, 3))            # 8  (2 and 3 are arguments)

Переменная, созданная внутри функции, является локальной — она существует только там. Эта область называется областью видимости.

def f():
    x = 10            # local to f
    return x

print(f())            # 10
# print(x) here would be an error: x is not defined outside f

У параметра может быть значение по умолчанию, используемое, когда вызывающий код его не указывает:

def greet(name, greeting="Hello"):
    return greeting + ", " + name

print(greet("Mei"))              # Hello, Mei
print(greet("Sam", "Welcome"))   # Welcome, Sam

Процедурная абстракция означает сокрытие деталей за именем. Вы используете функцию по её имени и назначению, а не по тому, как она работает.

def area_of_rectangle(w, h):
    return w * h

print(area_of_rectangle(4, 5))   # 20

• Хорошая функция выполняет одну задачу, имеет понятное имя и избегает дублирования кода.

Модуль — это файл с готовыми функциями. Подключите один с помощью import.

import random
random.seed(0)               # makes the result repeatable
print(random.randint(1, 6))  # a dice roll

import math
print(math.sqrt(16))         # 4.0

Распространенные ошибки

• Функция возвращает None, если вы не указали return. Печать (print) — это не то же самое, что возврат (return).
• Никогда не используйте изменяемый аргумент по умолчанию, например def f(x=[]) — та же самая ссылка на список будет общей для всех вызовов.
• Переменная, созданная внутри функции, является локальной и не видна снаружи.
• Запустите функцию с помощью f(); запись f сама по себе лишь создаёт ссылку на неё.

Код может сломаться тремя способами. Синтаксическая ошибка нарушает правила Python, поэтому код никогда не выполняется. Ошибка времени выполнения происходит во время работы, например деление на ноль. Логическая ошибка выполняется, но даёт неверный результат.

# A runtime error, caught so this block still finishes:
try:
    print(10 / 0)
except ZeroDivisionError:
    print("cannot divide by zero")
# cannot divide by zero

• Python печатает трассировку стека (traceback), показывающую, где произошла ошибка. Читайте её снизу вверх.

Оберните рискованный код в try. Если он выдаст ошибку, except перехватит исключение и обработает его, вместо того чтобы вызвать краш.

def to_int(text):
    try:
        return int(text)
    except ValueError:
        return 0

print(to_int("42"))    # 42
print(to_int("abc"))   # 0

• Перехватывайте конкретные типы ошибок (ValueError, ZeroDivisionError, …).
• raise намеренно вызывает вашу собственную ошибку.

def set_age(age):
    if age < 0:
        raise ValueError("age cannot be negative")
    return age

try:
    set_age(-1)
except ValueError as err:
    print("error:", err)
# error: age cannot be negative

Тест проверяет, что код даёт правильный ответ. Проверяйте обычные случаи и граничные случаи — пустой ввод, ноль, очень большие значения.

def average(nums):
    if len(nums) == 0:        # edge case: empty list
        return 0
    return sum(nums) / len(nums)

print(average([2, 4, 6]))     # 4.0
print(average([]))            # 0

• Надёжный код не падает при странных входных данных; он обрабатывает их корректно.

Распространенные ошибки

• Не используйте голый except: — перехватывайте конкретную ошибку, например except ValueError:.
• Синтаксическая ошибка останавливает программу до запуска, поэтому исправляйте их в первую очередь.
• Тестируйте граничные случаи (пустой ввод, ноль, максимальное значение), а не только простой случай.

Текстовый файл хранит текст на диске. Откройте его с помощью open(name, mode), где режим указывает на чтение или запись. Всегда используйте with, который закроет файл за вас.

Запись

Режим "w" создаёт новый файл и стирает любой старый.

with open("notes.txt", "w") as f:
    f.write("first line\n")
    f.write("second line\n")
print("saved")            # saved

Чтение

Режим "r" (по умолчанию) читает. .read() возвращает весь файл как одну строку.

with open("notes.txt", "w") as f:
    f.write("hello\nworld\n")
with open("notes.txt") as f:
    print(f.read().strip())   # hello / world

Построчно

Цикл по файлу получает по одной строке. .strip() удаляет символ переноса в конце.

with open("data.txt", "w") as f:
    f.write("Mei,88\nSam,71\n")
with open("data.txt") as f:
    for line in f:
        name, score = line.strip().split(",")
        print(name, "scored", score)
# Mei scored 88
# Sam scored 71

Добавление (append)

Режим "a" добавляет данные — он дописывает в конец, не стирая содержимое.

with open("log.txt", "w") as f:
    f.write("line 1\n")
with open("log.txt", "a") as f:
    f.write("line 2\n")
with open("log.txt") as f:
    print(f.read().strip())   # line 1 / line 2

Распространенные ошибки

• Всегда закрывайте файл или используйте with open(...) as f:, который закроет его автоматически.
• read() возвращает весь файл как одну строку, и каждая строка всё ещё заканчивается \n.
• Открытие режима "w" сначала стирает файл; используйте "a", чтобы добавить данные в конец.

Алгоритм — это чёткий набор шагов, решающих задачу. Декомпозиция означает разделение большой задачи на меньшие части, которые можно решать по очереди.

# Algorithm: find the largest number in a list
def largest(nums):
    best = nums[0]
    for n in nums:
        if n > best:
            best = n
    return best

print(largest([3, 9, 2, 7]))   # 9

• Абстракция означает игнорирование деталей: вы используете largest(...), не перечитывая, как она работает.

Псевдокод — это структурированный plain English для алгоритма, написанный до реального кода. Он не выполняется.

SET best TO first number
FOR Each number n
    IF n > best
      THEN
        SET best TO n
        OUTPUT best

Блок-схема рисует тот же план: прямоугольник для каждого шага, ромб для каждого решения и стрелки для порядка.

Рекурсия — это когда функция вызывает саму себя. Ей нужен базовый случай (простой входной параметр, дающий мгновенный возврат) и рекурсивный случай (вызов себя с меньшим входным параметром).

def fact(n):
    return 1 if n <= 1 else n * fact(n - 1)

print(fact(5))     # 120

• Каждый приостановленный вызов находится в стеке вызовов до тех пор, пока вызов над ним не вернётся.

Распространенные ошибки

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

Абстрактный тип данных (ADT) описывает данные и операции над ними отдельно от способа их реализации. Вы используете его через операции, а не через внутреннее хранение.

# A stack ADT, built on a list
s = []
s.append(1)        # add
s.append(2)
print(s.pop())     # 2  (remove the most recent)

Стек — это LIFO (последним пришёл — первым ушёл). Вы кладёте элементы на верх (push) и извлекаете с вершины (pop).

stack = []
stack.append("a")
stack.append("b")
print(stack.pop())   # b
print(stack.pop())   # a

Очередь — это FIFO (первым пришёл — первым ушёл). Вы добавляете элемент в конец (enqueue) и извлекаете спереди (dequeue).

queue = []
queue.append("a")     # enqueue
queue.append("b")
print(queue.pop(0))   # a  (dequeue the front)
print(queue.pop(0))   # b

Связный список — это цепочка узлов. Каждый узел хранит данные и указатель на следующий узел; последний указывает на None.

n3 = {"data": 3, "next": None}
n2 = {"data": 2, "next": n3}
n1 = {"data": 1, "next": n2}
node = n1
while node is not None:      # traverse to the end
    print(node["data"])
    node = node["next"]
# 1 2 3

Хэш-таблица отображает ключ в ячейку с помощью хэш-функции. Два ключа могут попасть в одну ячейку — коллизия. Словари Python dict являются хэш-таблицами, поэтому поиск быстрый.

table = {}
table["Mei"] = 88
table["Sam"] = 71
print(table["Mei"])   # 88  (fast lookup by key)

Двоичное дерево поиска (BST) сохраняет порядок: каждый левый потомок меньше своего узла, каждый правый — больше. Поиск остаётся быстрым.

def insert(root, val):
    if root is None:
        return {"val": val, "left": None, "right": None}
    if val < root["val"]:
        root["left"] = insert(root["left"], val)
    else:
        root["right"] = insert(root["right"], val)
    return root

def inorder(root):
    if root is None:
        return []
    return inorder(root["left"]) + [root["val"]] + inorder(root["right"])

tree = None
for v in [5, 3, 8, 1, 4]:
    tree = insert(tree, v)
print(inorder(tree))   # [1, 3, 4, 5, 8]

Граф — это множество вершин, соединённых рёбрами. Список смежности — словарь списков соседей — является распространённым способом хранения графа.

graph = {"A": ["B", "D"], "B": ["A", "C"], "C": ["B", "D"], "D": ["A", "C"]}
for vertex in graph:
    print(vertex, "->", graph[vertex])
# A -> ['B', 'D']  (and so on for B, C, D)

Распространенные ошибки

• Стек работает по принципу LIFO (последним пришёл — первым ушёл); очередь — по FIFO (первым пришёл — первым ушёл). Не перепутайте их.
• Проверяйте, пуста ли структура, перед тем как выполнить pop или dequeue.
• В связном списке потеря указателя head приводит к потере всего списка.

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

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1     # not found

print(linear_search([4, 8, 2, 9], 2))   # 2

Бинарный поиск намного быстрее, но требует отсортированного списка. На каждом шаге он уменьшает диапазон вдвое.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9], 7))   # 3

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

def bubble_sort(a):
    a = a[:]                          # work on a copy
    for i in range(len(a)):
        for j in range(len(a) - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

print(bubble_sort([5, 2, 4, 1]))      # [1, 2, 4, 5]

Сортировка вставками формирует отсортированную часть по одному элементу за раз, сдвигая каждый новый элемент на нужное место:

def insertion_sort(a):
    a = a[:]                           # work on a copy
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:   # shift bigger values right
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key                 # drop key into the gap
    return a

print(insertion_sort([5, 2, 4, 1]))   # [1, 2, 4, 5]

• В реальном коде используйте встроенную функцию Python sorted():

print(sorted([5, 2, 4, 1]))           # [1, 2, 4, 5]

Эффективность показывает, как растёт объём работы при увеличении входных данных. Мы описываем её с помощью Big-OO.

def steps(n):           # how many steps a linear scan takes
    count = 0
    for i in range(n):
        count = count + 1
    return count

print(steps(100))       # 100  -> O(n)

Модуль random генерирует случайные числа. Используйте seed (семя), чтобы результаты были воспроизводимы. Моделирование выполняет множество случайных испытаний для оценки ответа.

import random
random.seed(0)
rolls = [random.randint(1, 6) for _ in range(1000)]
print(rolls.count(6))   # about 1/6 of 1000

Распространенные ошибки

• Бинарный поиск работает только с отсортированным списком.
• Big-O показывает, как время РАСТЁТ, а не точное время; метод O(n²) может быть быстрее O(n) лишь на очень малых входах.
• Пузырьковая сортировка имеет сложность O(n²) — подходит для обучения, но медленна на больших списках.

Класс — это чертеж. Объект — это конкретный экземпляр, созданный по нему. __init__ — конструктор, который настраивает каждый объект; self — сам объект.

class Dog:
    def __init__(self, name):
        self.name = name            # an attribute
    def speak(self):
        return self.name + " says woof"

d = Dog("Rex")
print(d.speak())     # Rex says woof

• name — атрибут (данные объекта); speak — метод (действие).

Добавьте __str__ для управления тем, что отображает print(obj):

class Dog:
    def __init__(self, name):
        self.name = name
    def __str__(self):
        return f"Dog named {self.name}"

print(Dog("Rex"))    # Dog named Rex

Наследование позволяет подклассу переиспользовать код суперкласса. Используйте super() для вызова родителя; переопределите метод, чтобы изменить его поведение.

class Animal:
    def speak(self):
        return "some sound"

class Cat(Animal):
    def speak(self):                # override
        return "meow"

print(Cat().speak())   # meow

Инкапсуляция скрывает данные за методами; ведущее подчеркивание обозначает приватность.

class Account:
    def __init__(self):
        self._balance = 0           # private
    def deposit(self, n):
        self._balance += n
    def balance(self):
        return self._balance

a = Account()
a.deposit(50)
print(a.balance())     # 50

Полиморфизм означает одно имя — множество поведений; правильный speak выполняется для каждого объекта.

class Cat:
    def speak(self):
        return "meow"

class Cow:
    def speak(self):
        return "moo"

for animal in [Cat(), Cow()]:
    print(animal.speak())   # meow, then moo

Парадигма — это стиль написания программ. Процедурный код — это последовательность шагов и функций. Объектно-ориентированный код группирует данные и методы в объекты. Декларативный код говорит что вы хотите получить, а не как (списковое включение или SQL).

def total(nums):           # procedural
    t = 0
    for n in nums:
        t += n
    return t
print(total([1, 2, 3]))    # 6

print(sum([1, 2, 3]))      # 6  (declarative: same result)

Распространенные ошибки

• Каждый метод должен иметь self в качестве первого параметра.
• __init__ настраивает новый объект и запускается автоматически при его создании.
• Два объекта одного класса имеют отдельные атрибуты; изменение одного не влияет на другой.

Бит — это единичный 0 или 1. Двоичная система счисления с основанием 2: каждое разрядное значение вдвое больше значения справа (1, 2, 4, 8, …). Десятеричная система (основание 10) — это наши обычные числа.

print(bin(13))         # 0b1101
print(int("1101", 2))  # 13

• 8 бит образуют байт. Фиксированная ширина может вызвать переполнение (переход через границу) при слишком большом числе.

x = 250
x = (x + 10) % 256     # one byte wraps at 256
print(x)               # 4

Шестнадцатеричная система (основание 16) — компактный способ записи двоичных чисел: одна шестнадцатеричная цифра соответствует ровно четырем битам. Python записывает шестнадцатеричные числа с помощью 0x:

print(hex(255))        # 0xff
print(0xFF)            # 255
print(int("ff", 16))   # 255

Сжатие делает данные меньше. Безпотерянное сжатие сохраняет каждый бит, позволяя точно восстановить исходные данные. Потерянное сжатие отбрасывает детали — результат меньше, но не точен — и используется для фотографий и музыки.

Длиннокодовая кодировка (RLE) — простой метод безпотерянного сжатия: серия повторов хранится как счётчик плюс значение.

def rle(text):
    out = ""
    i = 0
    while i < len(text):
        run = 1
        while i + run < len(text) and text[i + run] == text[i]:
            run += 1
        out += str(run) + text[i]
        i += run
    return out

print(rle("AAAABBBCCD"))   # 4A3B2C1D

Распространенные ошибки

• n битов кодируют 2**n различных значений, от 0 до 2**n - 1.
• Потерянное сжатие отбрасывает детали и необратимо; безпотерянное можно вернуть в исходное состояние точно.

Информатика — это решение задач с помощью компьютеров: ввод, обработка, вывод. Качественное ПО создаётся в цикле проектирования — планирование, написание, тестирование, улучшение — который повторяется многократно.

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

Интернет — это сеть сетей. Данные разбиваются на пакеты, которые передаются отдельно и собираются обратно на другом конце. Общие правила, называемые протоколами (например, TCP/IP), обеспечивают эту работу. Если один путь выходит из строя, пакеты идут другим маршрутом — это избыточность, обеспечивающая отказоустойчивость.

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

• Не всё можно выполнить параллельно: некоторые действия должны ждать получения предыдущего результата.

Вычисления несут как преимущества, так и недостатки. Цифровое неравенство означает, что не все имеют равный доступ к технологиям. Программное обеспечение может переносить предвзятость из данных, на которых оно обучается. Уважайте интеллектуальную собственность (лицензии) и защищайте персональные данные и конфиденциальность людей.

Распространенные ошибки

• Интернет и Всемирная паутина (World Wide Web) — это не одно и то же: Web — это сервис, работающий поверх Интернета.
• Больше ядер процессора помогает только тогда, когда задачу можно разделить на части, выполняемые одновременно.

Мини-проект объединяет ранее изученные идеи: данные в списке, функция с выбором внутри цикла и вывод на экран. Это также структура задания AP Create Performance Task.

Проект: средняя оценка

def average(marks):
    if len(marks) == 0:
        return 0
    return round(sum(marks) / len(marks), 1)

print(average([88, 71, 95, 60]))   # 78.5

Проект: подсчёт сдач

def count_passes(marks, pass_mark=60):
    passes = 0
    for m in marks:                 # iteration
        if m >= pass_mark:          # selection
            passes += 1
    return passes

print(count_passes([88, 50, 95, 60]))   # 3

Проект: фильтрация в новый список

def merit(marks):
    return [m for m in marks if m >= 80]

print(merit([88, 71, 95, 60]))     # [88, 95]

Задание AP Create требует список, параметризованную процедуру, использующую выбор и итерацию, а также ввод/вывод. Каждый из проектов выше имеет именно такую структуру — создавайте небольшие компоненты, затем объединяйте их.

Распространенные ошибки

• Разбивайте создание кода на мелкие шаги и тестируйте каждую часть перед переходом к следующей — не пишите весь код сразу.
• Сначала прочитайте задание целиком, затем спланируйте входные данные → обработку → выходные данные перед написанием кода.