В этом листке мы будем изучать асимптотику факториалов и чисел $C_n^k$, строя при этом графики в библиотеке matplotlib.
Библиотека matplotlib предназначена для построения практически сколь угодно сложных графиков и диаграмм.
Про неё шутят, что простые вещи в ней делать просто, а сложные — ... теоретически возможно.
Для установки библиотеки нужно запустить следующую программу:
Если в результате её запуска вывод будет примерно такой как ниже, то у вас успех!
C:\some\path\Python312\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$.
Этой функций удобно пользоваться для построение графиков функций.
Нужно сдать только тело функции. В конец программы будет добавлено:
x, y, n = input().split()
print(*linspace(float(x), float(y), int(n)))
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 точкам.
Не меняйте никаких автоматических параметров графика.
Проведите серию экспериментов.
В комментариях ответьте на вопрос: как будет устроен прогресс двух людей за год,
один из которых каждый день прогрессирует на 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.$$
Проведите серию экспериментов.
В комментариях ответьте на вопрос: какое из чисел $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
Подсказка
Ничего не понятно...
Код должен выглядеть приблизительно так:
import matplotlib.pyplot as plt
from math import sin
n = 179
fig, ax = plt.subplots()
for shift in range(5):
xx = [x/42 for x in range(1, n+1)] # Создаём массив x-координат
yy = [sin(x+shift) for x in xx] # Создаём массив y-координат
ax.plot(xx, yy, label=rf'$\sin(x+{shift})$')
# r-строка, чтобы не ругалось на "\", а latex-формула в $$
ax.set_xlabel("Времена")
ax.set_ylabel("Процент сильных людей")
ax.legend()
plt.show()
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$.
