Лекция. Введение. Алгоритм и язык Python
Лекция 1. Введение. Алгоритм и язык Python
Курс «Алгоритмы и структуры данных» (факультет искусственного интеллекта МГУ). Два рабочих критерия качества алгоритма:
- корректность — на всех допустимых входах ответ верный;
- эффективность — время и память растут приемлемо с размером входа.
Python 3 здесь — язык записи и реализации. Где задание требует свою реализацию, встроенными аналогами пользоваться нельзя.
Сегодня: как записать алгоритм и обработать поток чисел, не складывая вход в память.
План
- Алгоритм. Псевдокод, блок-схема, Python.
- Основы языка Python.
- Функции: капсула, чистая функция, контракт.
- Потоки чисел и память $O(1)$.
Алгоритм
Алгоритм — это
- последовательность команд
- на формальном языке исполнителя,
- приводящая к цели
- за конечное время.
Исполнитель действует формально: не «додумывает» шаг, если выбор не прописан в самом алгоритме. Это детерминированность. Конечность тоже обязательна: зацикливание без достижения цели — не алгоритм.
Языки описания
Один и тот же алгоритм можно записать псевдокодом, блок-схемой и на Python. Задача: по натуральному $n$ вычислить сумму $1 + 2 + \ldots + n$.
Псевдокод.
ввести n
s ← 0
для x от 1 до n:
s ← s + x
вывести s
Блок-схема.
Python. Исполнитель курса — интерпретатор Python: те же шаги, формальный синтаксис.
n = 5
s = 0
x = 1
while x <= n:
s = s + x
x = x + 1
print(s)
Основы языка Python
Напоминание конструкций, без которых алгоритм не записать. Списков на этой лекции нет.
Операции с целыми
| Операция | Действие |
|---|---|
A + B, A - B, A * B | сумма, разность, произведение |
A / B | частное (вещественное) |
A // B | частное нацело |
A % B | остаток |
A ** B | степень |
// и % разбирают число по разрядам: последняя цифра — n % 10, без последней — n // 10.
Имя можно заставить обозначать новый объект: s = s + x или короче s += x.
n = 179
print(n // 100, n // 10 % 10, n % 10)
print(n // 100 + n // 10 % 10 + n % 10)
1 - 3 - 7
1 / 2 / 2
(3 ** 3) ** 3 == 3 ** (3*3)
-1 // 10
-1 % 10
Строки: + и *
Сложение строк — конкатенация, умножение на целое — повтор.
a = "алго"
b = "ритм"
print(a + b)
a + b == b + a
print("-" * 8)
a * b
2 ** 10000
x = 2 ** 10000
print(x)
s = str(x)
s.count()
help(s.count)
s.count("2")
Индекс и срез
Символы нумеруются с нуля: s[i], последний — s[-1]. Срез s[a:b] берёт индексы $a, a+1, \ldots, b-1$ (правая граница не входит). У str нет отдельного типа «символ»: и s[i], и срез — снова строка. Присваивать в s[i] нельзя: строки неизменяемы.
s = "алгоритм"
print(s[0], s[2], s[-1])
print(s[0:4], s[4:])
Ветвления
Сравнения ==, !=, <, >, <=, >= дают True или False. Команды, сдвинутые на 4 пробела под if, выполняются только при истинном условии. Первая несдвинутая строка после блока идёт уже безусловно.
Вложенный if — проверка внутри другой проверки.
x = 2 ** 100
if isinstance(x, int) and x > 0:
s = str(x)
if s.count('2') > 0:
print("Двоек в числе", x, s.count('2'))
Каскад if / elif / else выбирает один из взаимоисключающих исходов. Год високосный, если кратен 4, но не кратен 100, либо кратен 400.
year = 2000
if year % 400 == 0:
print("YES")
elif year % 100 == 0:
print("NO")
elif year % 4 == 0:
print("YES")
else:
print("NO")
Циклы for и while
range(n) даёт $0, 1, \ldots, n-1$. Цикл for — когда число шагов известно. Цикл while повторяет тело, пока условие истинно; переменную условия нужно менять в теле, иначе цикл не остановится.
s = 0
for x in range(1, 6):
s += x
print(s)
x = 1
while x < 100:
print(x)
x *= 2
Функции
Повторяющийся фрагмент алгоритма выносят в функцию — капсулу: описали один раз, вызываем сколько нужно.
Заголовок — строка def имя(параметры):. Тело сдвинуто на 4 пробела. Имена в скобках — формальные параметры; при вызове им подставляют фактические значения. return возвращает значение и заканчивает выполнение тела.
def maximum(a, b):
if a >= b:
return a
return b
print(maximum(3, 8), maximum(10, 2))
Чистая функция
Если кроме вычисления значения функция ещё читает клавиатуру, печатает, меняет объекты снаружи — у неё есть побочные эффекты.
Чистая функция побочных эффектов не имеет: результат зависит только от значений параметров. Её можно вызывать в любом месте, где нужно значение, и подставлять результат в выражения.
def is_leap(year):
"""Високосный ли год year (натуральное число)."""
if year % 400 == 0:
return True
if year % 100 == 0:
return False
return year % 4 == 0
print(is_leap(2000), is_leap(1900), is_leap(2024))
help(is_leap)
Контракт и документ-строка
Вызов функции — контакт заказчика и поставщика. Заказчик обещает допустимый вход (здесь — натуральный номер года). Поставщик обещает результат, соответствующий условию (истинность «год високосный»). Нарушение договорённости на входе снимает ответственность за выход.
Минимум документации контракта — документ-строка: первая строка в теле, в тройных кавычках. Она описывает, что делает функция, что принимает и что возвращает. В примере выше это строка сразу под def.
Ввод и вывод на семинаре
В контесте программа — не чистая функция, а процедура: читает вход и печатает ответ. Так будут устроены задачи семинара. Это формат проверки, а не обычный стиль прикладного кода, где функция принимает аргументы и возвращает значение, а печать оставляют вызывающему коду.
year = int(input())
if is_leap(year):
print("YES")
else:
print("NO")
input() даёт строку до конца строки, int(...) делает из неё целое, print(...) пишет ответ.
Потоки чисел и память $O(1)$
Последовательность можно обработать, не запоминая её целиком: прочитали (или породили) очередное число, обновили несколько переменных, само число забыли. Число дополнительных ячеек не растёт с длиной входа — это и есть память $O(1)$ на этой лекции (без формального определения нотации).
Складывать члены в список нельзя: для суммы, произведения и максимума он не нужен.
Свёртка последовательности в одно число — редукция. Аккумулятор суммы инициализируют нулём, произведение — единицей (иначе всё занулится).
s = 0
p = 1
for x in range(1, 6):
s += x
p *= x
print(s, p)
Максимум: помним текущий лучший, сравниваем с очередным. Ниже поток — остатки (k * 7) % 10 при $k = 0, 1, \ldots, 7$; в памяти только k, x и m.
m = None
for k in range(8):
x = (k * 7) % 10
if m is None or x > m:
m = x
print(m)
Генерация прогрессий
Член печатают сразу, последовательность не собирают. Арифметическая: постоянная разность. Геометрическая: постоянный множитель.
x = 10
while x < 50:
print(x)
x += 5
x = 1
while x < 100:
print(x)
x *= 2
Фильтрация
Редукция только по членам, прошедшим условие: учёт очередного числа ставят под if. Список отобранных не нужен, если ответ — одно число (здесь — сколько чётных).
count = 0
for x in range(1, 11):
if x % 2 == 0:
count += 1
print(count)
Поэлементная обработка
Для каждого члена сразу печатают преобразование. Пример: квадраты, не превосходящие $n$.
n = 20
k = 1
while k * k <= n:
print(k * k)
k += 1
На семинаре те же приёмы: разряды через // и %, ветвления, циклы, поток без списка.
Модель вычислений и нотации роста времени и памяти — на следующей лекции.