Разбиение на подзадачи и библиотеки

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

Два урока плана за одну пару: «Разбиение задачи на подзадачи» и «Использование стандартной библиотеки языка программирования. Подключение библиотек подпрограмм сторонних производителей». Тема одна: большая задача собирается из маленьких, и не все из них надо писать самому.

Задача, которую не видно целиком

Дано число N до миллиарда. Сколько у него делителей и чему равна их сумма?

Писать такую программу «с начала и до конца» неудобно: непонятно, с чего начать, а когда она наконец напечатает неверное число, будет неясно, какая именно часть соврала.

Подзадача — это вход и выход

ЭтапЧто на входеЧто на выходе
1. граница перебораNцелая часть корня из N
2. перебор делителейN и границасчётчик и сумма
3. выводсчётчик и суммадве строки на экране

Порядок этапов задают данные

n = 48
s = n * 2
t = s + 3
print(t)

s нужен n, t нужен s, печати нужен t. Переставить нельзя.

Этапы проверяются по одному

gr = isqrt(N)
print("граница:", gr)     # временно: посмотрели и убрали

Написал этап — убедись, что он даёт то, что обещал, и только потом пиши следующий. Иначе ошибку придётся искать во всей программе сразу.

Часть подзадач уже решена

Цикл, который мы бы написалиГотовый вызовЧто это
вычитаем меньшее из большего, пока не сравняютсяgcd(a, b)НОД — наибольший общий делитель
ищем наибольшее d, у которого d · d ≤ nisqrt(n)целый квадратный корень
умножаем все числа от 2 до nfactorial(n)факториал n! = 1 · 2 · … · n
если число отрицательное — меняем знакabs(x)модуль числа |x|
сравниваем два числа и берём большееmax(a, b)наибольшее из чисел

Три способа подключить библиотеку

import math                # пришло одно имя: math
print(math.sqrt(16))       # звать через точку

from math import sqrt, gcd # пришли два имени, а math — нет
print(sqrt(16))            # звать без приставки

from random import *       # пришли все имена библиотеки
print(randint(1, 6))

Что лежит в стандартной библиотеке

МодульЧто берём сегодня
mathsqrt, isqrt, floor, ceil, gcd, factorial, hypot, pi
randomrandint, randrange, random, seed
timetime() — сколько секунд считалась программа

«Стандартная» — значит, она уже внутри установленного Python: достаточно import, скачивать нечего.

Что делает каждая функция — на следующих трёх слайдах.

Справочник: math

ВызовЧто делаетПример → результат
sqrt(x)квадратный корень (square root); ответ всегда дробныйsqrt(16) → 4.0   sqrt(2) → 1.414…
isqrt(n)целый квадратный корень (integer sqrt): наибольшее целое d, у которого d · d ≤ n isqrt(16) → 4   isqrt(17) → 4
floor(x)округление вниз, «пол» (floor) — к меньшему целомуfloor(3.7) → 3   floor(-3.2) → -4
ceil(x)округление вверх, «потолок» (ceiling) — к большему целому ceil(3.2) → 4   ceil(-3.7) → -3
gcd(a, b)НОД — наибольший общий делитель (greatest common divisor) gcd(12, 18) → 6   gcd(0, 7) → 7
factorial(n)факториал: n! = 1 · 2 · 3 · … · n factorial(5) → 120
hypot(a, b)гипотенуза (hypotenuse) по катетам a и b: √(a² + b²)hypot(3, 4) → 5.0
piне функция, а число π — пишется без скобокpi → 3.141592653589793

Справочник: random и time

ВызовЧто делаетПример → результат
randint(a, b)случайное целое от a до b, обе границы входят (random integer) randint(1, 6) → одно из 1, 2, 3, 4, 5, 6
randrange(a, b)случайное целое от a до b − 1: правая граница не входит, как в range randrange(1, 6) → одно из 1 … 5
random()случайное дробное от 0 до 1 (единица не выпадает); скобки пустые, но обязательны random() → например 0.639…
seed(x)посев: задаёт, с какого места пойдёт последовательность. Один посев — одни и те же числа у всех seed(42) → ничего не печатает
time()
из модуля time
сколько секунд прошло с 1 января 1970 года. Само по себе число бесполезное — полезна разность двух замеров t0 = time()
…программа…
print(time() - t0) → 0.84…

Справочник: встроенные функции

Эти работают без import — они есть в Python всегда.

ВызовЧто делаетПример → результат
abs(x)модуль числа |x| (absolute): отбрасывает минусabs(-5) → 5
max(a, b, …)
min(a, b, …)
наибольшее / наименьшее из перечисленных чисел max(3, 8, 5) → 8
min(3, 8, 5) → 3
int(x)целое число: у дробного отбрасывает дробную часть, то есть округляет к нулю int(3.9) → 3
int(-3.9) → -3
round(x)округление до ближайшего целого; ровная половина — к чётному round(2.7) → 3
round(2.5) → 2
help(f)печатает справку о функции f: что принимает и что возвращаетhelp(round)

Целое или дробное — смотри, что возвращает функция

print(sqrt(16))    # 4.0  — дробное, хоть и ровное
print(isqrt(16))   # 4    — целое
print(hypot(3, 4)) # 5.0  — дробное
print(gcd(12, 18)) # 6    — целое

Три ловушки чужих функций

print(int(-7 / 2))   # -3
print(-7 // 2)       # -4
print(round(2.5))    # 2
print(round(3.5))    # 4

int округляет к нулю, // и floor — вниз. round округляет ровную половину к чётному.

Разбор: делители через целый корень

N = 36. Делители парами: 1 и 36, 2 и 18, 3 и 12, 4 и 9, 6 и 6.

Всего 9 делителей, сумма 91.

Перебирать до 36 незачем: после корня пойдут те же пары наоборот.

gr = isqrt(N)
d = 1
while d <= gr:
    if N % d == 0:
        k = k + 2
        s = s + d + N // d
        if d * d == N:
            k = k - 1
            s = s - d
    d = d + 1

Разбор: НОД цепочки

g = 0
for i in range(1, K + 1):
    x = int(input())
    g = gcd(g, x)
print(g)

Почему старт — ноль: gcd(0, x) = x, и первое же число попадает в накопитель целиком.

Старт с единицы всё ломает: gcd(1, x) всегда 1.

Случайное, которое можно проверить

from random import *
seed(42)
print(randint(1, 6))
print(randint(1, 6))

seed(start) — посев: он задаёт, с какого места генератор начнёт последовательность.

С одним и тем же посевом у всех выпадет одно и то же — поэтому такую программу вообще можно проверить.

Чужая документация: help()

>>> help(round)
round(number, ndigits=None)
    Round a number to a given precision in decimal digits.

Это та же шапка «что на входе, что на выходе», которую мы писали сами в прошлой паре, только написали её авторы Python. Наберите в IDLE help(isqrt) — и не придётся гадать.

Сторонние библиотеки

Стандартная приходит вместе с Python. Сторонние пишут другие люди — их сотни тысяч, и на компьютере их нет, пока не поставишь.

БиблиотекаЗачем
pygameигры: окно, картинки, звук
pillowобработка изображений
requestsзапросы в сеть
numpyбыстрые вычисления над таблицами чисел

Как ставят: pip по шагам

  1. Открыть командную строку Windows: Win + R, набрать cmd, Enter. Не IDLE!
  2. Набрать команду и нажать Enter:
C:\Users\ученик> pip install pygame
Collecting pygame
  Downloading pygame-2.6.1-cp313-cp313-win_amd64.whl (10.6 MB)
Successfully installed pygame-2.6.1
  1. Последняя строка Successfully installed — готово. Теперь в программе обычный import pygame.

pip: где спотыкаются

Забыли поставить. import pygame → ModuleNotFoundError: No module named 'pygame'. Программа ни при чём: на этом компьютере такой библиотеки просто нет.

Набрали не там

Командная строка начинается с C:\…>, IDLE — с >>>. pip install в IDLE даёт SyntaxError: это команда Windows, а не строчка Python.

pip «не найден»

"pip" не является внутренней или внешней командой — то же самое через Python:
py -m pip install pygame

Что делаем сегодня

  1. Тренажёр — шесть задач: этапы программы, каким вызовом заменить кусок, деление с округлением, целое или дробное, какая строка упадёт при таком подключении, порядок этапов.
  2. Три программы, в каждой один этап берётся готовым: делители через isqrt, НОД цепочки через gcd, броски кубика через seed и randint.
  3. Проверка оболочкой — Проверка.bat из общей папки: девять наборов данных на каждое задание.

Отметка: три задания — «5», два — «4», одно — «3». Попыток сколько угодно.

За работу

Сначала тренажёр, потом три программы.

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

Материалы подготовлены с использованием технологий искусственного интеллекта. Пробел раскрыть и дальше · ← → слайды