Введение

В этом листке мы будем изучать асимптотику факториалов и чисел $C_n^k$, строить графики в библиотеке matplotlib, а также рисовать фракталы черепашкой.

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

Для установки библиотеки нужно запустить следующую программу:

import os, sys python = sys.executable user = '--user' if 'venv' not in python else '' cmd = '{} -m pip install matplotlib --upgrade {}'.format(python, user) print(cmd) os.system(cmd)

Если в результате её запуска вывод будет примерно такой как ниже, то у вас успех!

C:\some\path\Python38\python.exe -m pip install matplotlib --upgrade --user Collecting matplotlib ... что-то про downloading или Using cached ... что-то ещё collecting Installing collected packages: matplotlib, что-то ещё Successfully installed что-то matplotlib-3.3.1 что-то ещё

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

Замечания по вводу-выводу

Каждая программа должна начинаться со строк с импортированием matplotlib: 

import matplotlib.pyplot as plt

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

Первые простые графики

Вот типичный простой пример программы, которая строит простой график: 

import matplotlib.pyplot as plt
# Создаём картинку fig, а на ней создаём один холст (координатные оси) ax для графиков
fig, ax = plt.subplots()
xx = [0, 1, 2, 3, 4]  # Создаём массив x-координат
yy = [5, -3, 0, 1, 4]  # Создаём массив y-координат
ax.plot(xx, yy)  # Добавляем графики
plt.show()  # Выводим на экран

Разберём этот пример подробно.
import matplotlib.pyplot as plt — это де-факто общепринятый стандарт по импортированию этой библиотеки.
fig, ax = plt.subplots() — мы создаём картинку (figure) и на ней одну ось координат (axes). Теоретически мы можем одновременно работать с несколькими картинками, на каждой из которых будет по несколько разных осей координат. Обычно с переменной fig не требуется ничего делать, и всё рисование производится в ax.
xx = [0, 1, 2, 3, 4]; yy = [5, -3, 0, 1, 4] — здесь мы создаём списки $x$- и $y$-координат графика. Важно, что количество точек в этих списках должно быть одинаковым.
ax.plot(xx, yy) — здесь мы добавляем в координатную сетку ax график. Можно добавлять сразу несколько графиков, вызывая ax.plot несколько раз.
plt.show() — запуск окна, в котором отображается наша картина.

A: Арифметическая прогрессия

Напишите функцию linspace, принимающую на вход действительные числа $x$, $y$ и натуральное число $n$, и возвращающую список с арифметической прогрессией $a_1, a_2, \ldots, a_n$, в которой $a_1 = x$ и $a_n = y$.

Этой функций удобно пользоваться для построение графиков функций.

0 1 6
0.0 0.2 0.4 0.6 0.8 1.0
-3 2 11
-3.0 -2.5 -2.0 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0

Пример чуть посложнее

Предположим, что функцию linspace из первой задачи вы уже написали. Тогда рисовать графики можно так: 

import matplotlib.pyplot as plt
from math import sin, cos, sqrt

def linspace(x, y, n):
    ...
    return [... for i in range(n+1)]

fig, ax = plt.subplots()
xx = linspace(-5, 5, 101)
yy1 = [1/6 * x ** 2 - 2 for x in xx]
yy2 = [2*cos(x*2) + 1/4*cos(10*x) for x in xx]
yy3 = [sqrt(abs(x)) for x in xx]
ax.plot(xx, yy1)
ax.plot(xx, yy2)
ax.plot(xx, yy3)
plt.show()

B: Парабола

На вход даются числа $a, b, c$. На отрезке $[-5, 5]$ постройте четыре параболы по 101 точкам:
$y = ax^2 + bx + c$,
$y = (a+0.1)x^2 + bx + c$,
$y = ax^2 + (b+0.1)x + c$,
$y = ax^2 + bx + (c+0.1)$.
Не меняйте никаких автоматических параметров графика.

Используйте функцию linspace из предыдущей задачи.

Проведите серию экспериментов. В комментариях ответьте на вопрос: при каких условиях изменение одного из коэффициентов на 0.1 значительно влияют на график параболы и её корни.

0.1 .5 -1

C: Экспоненциальный мотиватор

На вход даётся число $n$. Постройте графики функций $1.01^x$ и $0.99^x$ на отрезке $[0, n]$ по 101 точкам.
Не меняйте никаких автоматических параметров графика.

Используйте функцию linspace из задачи A.

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

30

D: Число двоичных цифр в степенной функции

На вход даётся число $n$. Постройте графики количества двоичных цифр в числах:
$1^2, 2^2, \ldots, n^2$;
$1^3, 2^3, \ldots, n^3$;
$1^4, 2^4, \ldots, n^4$; Количество двоичных цифр можно получить при помощи метода .bit_length().
Не меняйте никаких автоматических параметров графика.

В этой задаче все значения $x$ целые, поэтому функция linspace не требуется. Используйте просто подходящий range.

Проведите серию экспериментов. В комментариях ответьте на вопрос: как число двоичных цифр изменяется с ростом $n$ и с ростом показателя степени, в которую $n$ возводится?

10

E: Число двоичных цифр в показательной функции

На вход даётся число $n$. Постройте графики количества двоичных цифр в числах:
$2^1, 2^2, \ldots, 2^n$;
$3^1, 3^2, \ldots, 3^n$;
$4^1, 4^2, \ldots, 4^n$;

В этой задаче все значения $x$ целые, поэтому функция linspace не требуется. Используйте просто подходящий range.

Проведите серию экспериментов. В комментариях ответьте на вопрос: как число двоичных цифр изменяется с ростом $n$ и с ростом основания степени? Сравните показательные и степенные функции. Охарактеризуйте их рост.

10

F: Число двоичных цифр в факториале

На вход даётся число $n$. Постройте графики количества двоичных цифр в числах:
$1^2, 2^2, \ldots, n^2$;
$2^1, 2^2, \ldots, 2^n$;
$1!, 2!, \ldots, n!$;
$1^1, 2^2, \ldots, n^n$;
Для вычисления факториала используйте функцию factorial из модуля math.

Проведите серию экспериментов. В комментариях упорядочьте функции $n^2$, $2^n$, $n!$ и $n^n$ по возрастанию и охарактеризуйте разницу в их росте. Рост каких функций «похож» друг на друга при очень больших $n$ (порядка 2000)? Во сколько раз примерно отличается количество двоичных цифр в $1000!$ и в $2^{2000}$?
Попробуйте заменить число 2 в показателе и основании степени на другие: 0.5, 0.9, 1.001, 2, 3. Как меняются функции? Для сравнения нарисуйте их все вместе, подписывая графики. Для этого нужно добавлять параметр label (ax.plot(..., label='2**n'), а перед выводом графика добавить команду ax.legend().

10

G: Асимптотика факториала

На вход даётся число $n$. Постройте графики количества двоичных цифр в числах:
$\left(\frac13\right)^1, \left(\frac23\right)^2, \ldots, \left(\frac n3\right)^n$;
$1!, 2!, \ldots, n!$;
$\left(\frac12\right)^1, \left(\frac22\right)^2, \ldots, \left(\frac n2\right)^n$;
Используйте целочисленное деление.

Проведите серию экспериментов. Попробуйте подобрать такие числа $\alpha$ и $\beta$ так, чтобы «зазор» между графиками функций был как можно меньше и при больших $n$ выполнялось неравенство: $$\left(\displaystyle\frac{n}{\alpha}\right)^n < n! < \left(\displaystyle\frac{n}{\beta}\right)^n.$$

10

H: График $C_n^k$

На вход даётся число $n$. Постройте графики следущих последовательностей:
$C_{n-1}^0, C_{n-1}^1, \ldots, C_{n-1}^{n-1}$;
$C_{n}^0, C_{n}^1, \ldots, C_{n}^{n}$;
$C_{n+1}^0, C_{n+1}^1, \ldots, C_{n+1}^{n+1}$;

Проведите серию экспериментов. В комментариях ответьте на вопрос: какое из чисел $C_n^k$ при фиксированном $n$ самое большое. Почему? Как выглядят графики при достаточно больших $n$?

5

I: Число двоичных цифр в $C_n^k$

На вход даётся число $n$. Постройте графики количества двоичных цифр в следущих последовательностях:
$C_{n-1}^0, C_{n-1}^1, \ldots, C_{n-1}^{n-1}$;
$C_{n}^0, C_{n}^1, \ldots, C_{n}^{n}$;
$C_{n+1}^0, C_{n+1}^1, \ldots, C_{n+1}^{n+1}$;

Проведите серию экспериментов. В комментариях ответьте на вопрос: что напоминают графики при больших $n$? Насколько они отличаются друг от друга?

5

J: Асимптотика $C_n^{[n/2]}$

На вход даётся число $n$. Постройте графики количества двоичных цифр в следущих последовательностях:
$C_{1}^{[1/4]}, C_{2}^{[2/4]}, \ldots, C_{n}^{[n/4]}$;
$C_{1}^{[1/3]}, C_{2}^{[2/3]}, \ldots, C_{n}^{[n/3]}$;
$C_{1}^{[1/2]}, C_{2}^{[2/2]}, \ldots, C_{n}^{[n/2]}$;
Какой функцией можно неплохо приблизить $C_n^{[n/2]}$ при достаточно большом $n$?

Проведите серию экспериментов. В комментариях ответьте на вопрос: как устроен рост чисел $C_n^{[\alpha n]}$ с ростом $n$ при фиксированном $\alpha$? Попробуйте как можно точнее определить асимптотику $C_{n}^{[n/2]}$.

5

K★: Подписи к графику

Нарисуйте график, как можно более похожий на ответ в примере.

Ключевые слова: label, set_title, set_xlabel, set_ylabel, legend, TeX, frac. В формулах в формате $\LaTeX$ не добавляйте пробелы.

10

L★★: Асимптотика факториала — 2

В этой задаче мы попытаемся точно установить асимптотику факториала. Мы уже видели, как устроен рост степенной и показательной функций, факториала и функции $n^n$. Попробуем собрать факториал из этих «кирпичиков». А именно представим $n!$ так: $$ n! \approx C \cdot n^\gamma \cdot \alpha^n \cdot n^n. $$ То есть в виде произведения константы, степенной функции, показательной функции и $n^n$. Для определения констант $C, \gamma, \alpha$ нам пригодится функция, которая вычисляет отношение факториала к нашей функции.

Напишите функцию f_ratio(n, C, ga, al), которая вычисляет число $$ \displaystyle\frac{n!}{C \cdot n^\gamma \cdot \alpha^n \cdot n^n}. $$ Ответ будет проверяться с относительной точностью $10^{-8}$.
Эта задача содержит в себе пачку нюансов, поэтому после неудачных экспериментов используйте подсказку.

10 1.0 0.0 0.5
0.37158912
10 1.0 0.0 0.333
21.643161384219646
10 1.0 1.0 0.333
2.1643161384219645
1000 1.0 1.0 0.333
1.4468073814356045e+42
3000 1.0 1.0 0.333
2.7822435344132216e+128
Подсказка
Всё ноль да ноль...

В произведении очень много и маленьких, и больших множителей. Если сначала слишком долго перемножать маленькие множители, то получится 0, и вся информация потеряется. Поэтому распишем ответ в виде $$ \displaystyle\frac{1}{C \cdot n^\gamma} \cdot \displaystyle\frac{1}{\alpha n} \cdot \displaystyle\frac{2}{\alpha n} \cdot \ldots \cdot \displaystyle\frac{n-1}{\alpha n} \cdot \displaystyle\frac{n}{\alpha n}. $$ Распределим множители в два списка: список чисел, больших 1, и список чисел, меньших 1. Дальше пока оба списка не пусты, будем брать множитель, больший 1, если текущее произведение меньше 1, и наоборот.

Проведите серию экспериментов. Сначала подберите такие числа $\alpha_1$ и $\alpha_2$, что $|\alpha_1-\alpha_2|\le 0.01$, и $$0 < f\_ratio(1000, 1, 0, \alpha_1) \le 1 \le f\_ratio(1000, 1, 0, \alpha_2).$$ (При $n=1000$ константа и степенная функция представляют из себя практически «незначительный множитель»).
Затем подберите такое число $\gamma$, что $1/2 < f\_ratio(100, 1, \gamma, \alpha_1) \le 1 \le f\_ratio(100, 1, \gamma, \alpha_2)$
Теперь в качестве $C$ возьмите $(f\_ratio(10, 1, \gamma, \alpha_1) + f\_ratio(10, 1, \gamma, \alpha_2))/2$.
Первое приближение готово. Дальше нужно виртуозно повторять этот цикл, увеличивая $n$ и уточняя полученные константы.
Когда константы будут получены с хорошей точностью, нужно попробовать угадать их точные значения. Для каждой константы $x$ полезно посмотреть на $x, 1/x, 2x, x/2, 1/(2x), 2/x, x^2, 2x^2, x^2/2$ и т.п., среди подобных чисел должны встретиться знакомые.
Если константы правильные, то число $f\_ratio(10^7, C, \gamma, \alpha)$ будет отличаться от 1 не больше, чем на $10^{-8}$. Не так плохо, учитывая, что $10\,000\,000! \approx 1.2024234\cdot 10^{65657059}$.

M: Случайные блуждания

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

Итак, стартуем из точки $(0, 0)$ и делаем $n$ шагов: либо $(1, 1)$, либо $(1, -1)$, причём направление выбираем случайным образом. Получившаяся кривая и есть случайное блуждание.

На вход даются числа $n$ и $k$. Постройте график $k$ случайных блужданий с $n$ шагами.

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

import random  # Разные функции для генерации псевдослучайных последовательностей
random.seed(179)
# random.seed — специальная команда для того,
# чтобы последовательность «случайных» чисел была одной и той же
# при разных запусках
direction = random.choice((1, -1))

Проведите серию экспериментов. Попробуйте понять, какая кривая «ограничивает» множество точек всех графиков, когда $n=k=100, 200$.
Опишите, как «ведут» себя кривые при $n=10000$ и $k=10$.

10 1
10 2
10 3

Черепа-а-а-ашка!

Библиотека turtle — это модуль для языка Питон, позволяющей рисовать на экране рисунки. Представьте себе, что по экрану компьютера ползает маленькая черепашка (turtle). Вы можете управлять движением черепашки, отдавая ей различные команды вида "Проползти вперед на 10 пикселей", "Поверни направо на 10 градусов". После того, как вы отдадите ей команду "Начать рисовать", черепашка будет оставлять за собой след, пока не получит команду "Закончить рисовать". Управлять черепашкой можно при помощи инструкций Питона. Вот так, например, выглядит программа, рисующая квадрат: 

import turtle           # Подключаем модуль turtle
T = turtle.Turtle()     # T — это наша черепашка. Можно создавать много черепашек
T.pendown()             # Опускаем перо (начало рисования)
T.forward(50)           # Проползти 50 пикселей вперед
T.left(90)              # Поворот влево на 90 градусов
T.forward(50)           # Рисуем вторую сторону квадрата
T.left(90)              # Поворот влево на 90 градусов
T.forward(50)           # Рисуем третью сторону квадрата
T.left(90)              # Поворот влево на 90 градусов
T.forward(50)           # Рисуем четвертую сторону квадрата
T.penup()               # Поднять перо (закончить рисовать)
T.forward(100)          # Отвести черепашку от рисунка в сторону
T.hideturtle()          # Спрятать черепашку
turtle.mainloop()       # Задержать окно на экране

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

Находится на странице https://docs.python.org/3/library/turtle.html.

Основные команды для управления черепашкой

Самое основное

T.forward(distance)
Проползти вперёд на distance пикселей;
T.right(angle)
Повернуться направо на angle градусов;
T.left(angle)
Повернуться налево на angle градусов;
T.pendown()
Начать рисовать;
T.penup()
Закончить рисовать;
T.goto(x, y)
Переместить черепашку в точку с координатами (x,y);

Ползаем

T.backward(distance)
Проползти назад на distance пикселей;
T.setx(x)
Установить x координату черепашки;
T.sety(y)
Установить y координату черепашки;
T.setheading(to_angle)
Повернуть черепашку под углом to_angle к вертикали (0 — наверх, 90 — направо);
T.home()
Вернуть черепашку домой — в точку, с координатами (0,0);
T.circle(radius)
Нарисовать окружность радиуса |r|, центр которой находится слева от черепашки, если r>0 и справа, если r<1;
T.dot(size, color)
Нарисовать точку диаметра size цвета color. Параметр color необязателен;
T.undo()
Откатить предыдущее действие черепашки;

Рисуем

T.pensize(width)
Установить диаметр пера в width;
T.pencolor(colorstring)
Установить цвет линии, которая рисует черепашка (например, 'brown' или '#32c18f');
T.fillcolor(colorstring)
Установить цвет заполнения;
T.begin_fill()
Начать следить за черепашкой для заполнения области;
T.end_fill()
Заполнить цветом fillcolor область, пройденную черепашкой начиная с begin_fill();
T.showturtle()
Показать черепашку;
T.hideturtle()
Спрятать черепашку;
T.write(text)
Вывести текст text;

Ускоряем рисование

T.speed(speed)
Установить скорость черепашки. speed должно быть от 1 (медленно) до 10 (быстро), или 0 (мгновенно);
T.getscreen().tracer(n)
Отрисовывать лишь каждый n-й кадр. Почти в n раз ускоряет отрисовку.

Узнать про черепашку

T.position()
Получить текущие координаты черепашки;
T.towards(x, y)
Получить угол между текущим направление черепашки и прямой от черепашки к точке (x,y);
T.xcor()
Получить x координату черепашки;
T.ycor()
Получить y координату черепашки;
T.heading()
Получить текущий угол к вертикали;
T.distance(x, y)
Получить расстояние до точки (x,y);
T.isdown()
Узнать, рисует ли сейчас черепашка;
T.isvisible()
Узнать, видима ли сейчас черепашка;

Интерактив

turtle.onkey(function, key)
Выполнить функцию function (принимающей два аргумента, x и y — координаты черепашки) после нажатия кнопки key (например, 'a', 'Up', 'space');
turtle.listen()
Начать следить на нажатиями клавиш и кликами мыши;
turtle.ontimer(function, time)
Выполнить функцию function через time миллисекунд;
turtle.textinput(title, prompt)
Вывести окно с заголовком title и текстом prompt, вернуть введённое значение;

Контроль над окном

turtle.setworldcoordinates(llx, lly, urx, ury)
Сделать окно от (llx, lly) до (urx, ury);
T.getscreen().window_width()
Ширина окна
T.getscreen().window_height()
Высота окна
turtle.turtles()
Список всех черепашек

N: Многоугольники

На вход даётся натуральное число $n>1$. Нарисуйте все $k$-угольники для $k$ от 2 до $n$ так, чтобы у них была общая сторона.

Картинки с примерами
9

O: Кривая Коха

Кривая Коха — фрактальная кривая, описанная в 1904 году шведским математиком Хельге фон Кохом. Кривая Коха является типичным геометрическим фракталом. Процесс её построения выглядит следующим образом: берём единичный отрезок, разделяем на три равные части и заменяем средний интервал равносторонним треугольником без этого сегмента. В результате образуется ломаная, состоящая из четырёх звеньев длины 1/3. На следующем шаге повторяем операцию для каждого из четырёх получившихся звеньев и т. д… Предельная кривая и есть кривая Коха.

Строить фрактальные кривые очень удобно при помощи рекурсивных процедур, получающих на вход глубину рекурсии и линейный размер кривой (или какой-то её конкретной части).

На вход даётся неотрицательное число $n$. Постройте кривую «степени» $n$.

Картинки с примерами
0
1
2
3
7

P: Снежинка Коха

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

На вход даётся неотрицательное число $n$. Постройте кривую «степени» $n$.

Картинки с примерами
0
1
5

Q: Треугольник Серпинского

Треугольник Серпинского — фрактал, один из двумерных аналогов множества Кантора, предложенный польским математиком Вацлавом Серпинским в 1915 году. Также известен как «решётка» или «салфетка» Серпинского.

На вход даётся неотрицательное число $n$. Постройте границу салфетки Серпинского «степени» $n$.

Картинки с примерами
0
1
2
5
9

R: Кривая Минковского

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

На вход даётся неотрицательное число $n$. Постройте кривую «степени» $n$.

Картинки с примерами
0
1
2
3

S: Сторона ледяного фрактала

В ледяном фрактале всё начинается с отрезка. На каждом шаге в центре каждого отрезка «отрастают» два «уса» под углом 60 градусов длиной одна четверть от исходного отрезка.

На вход даётся неотрицательное число $n$. Постройте кривую «степени» $n$.

Картинки с примерами
0
1
2
3
4

T: Ледяной треугольный фрактал

Из 6 кусков соберите ледяной треугольный фрактал.

На вход даётся неотрицательное число $n$. Постройте кривую «степени» $n$.

Картинки с примерами
0
1
2
5

U: Кривая дракона

Считается, что такое название фрактал получил за сходство с традиционными китайскими драконами. По крайней мере, так показалось ученым, которые впервые его исследовали. Каждая ломаная-дракон является лишь приближением к дракону-фракталу и состоит из отрезков. Ломаная с номером n будет состоять из $2^n$ отрезков.

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

На вход даётся неотрицательное число $n$. Постройте кривую «степени» $n$.
Ориентация кривой важна, первый поворот — налево.

Картинки с примерами
0
1
2
3
4
5
10
18

V: Оголённое Пифагорово дерево

В этой задаче мы будем строить то, что называют «обнаженное обдуваемое ветром дерево Пифагора». Классическое дерево Пифагора состоит из множества квадратов (см. раз, два).

На вход даётся неотрицательное число $n$, и два угла $\alpha$ и $\beta$. Необходимо построить дерево «степени» $n$. Для этого нужно построить отрезок, клонировать черепашку командой T.clone(). Первую черепашку нужно повернуть на угол $\alpha$ налево, а вторую — на угол $\beta$ направо. После чего приказать каждой черепашке построить по такому же дереву Пифагору на единицу меньшей степени.

Длина каждого следующего отрезка в глубь должна быть в $\sqrt2$ раза меньше предыдущего.

PS. Вероятно, саму черепашку, которая будет рисовать дерево, нужно передавать внутрь рекурсивной функции.

Картинки с примерами
0 45 45
1 45 45
2 45 45
3 45 45
4 60 20
9 60 20
12 60 20

Ещё нетривиальные примеры черепашки

Рисуем простую фигуру

Знак радиоактивности

Оптическая иллюзия

Гравитация — комета-черепашка вокруг солнца

Управляем космическим кораблём

Пример от разработчкиков turtle