В этом листке мы будем изучать асимптотику факториалов и чисел $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$ возводится?
Что значит "как изменяется график с ростом $x$"?
Если график - прямая линия, то с ростом $x$ он всегда меняется одинаково: на сколько увеличилось $x$, на столько изменилось значение на графике. Но может быть и по-другому: при больших $x$ значения на графике могут меняться медленнее или быстрее, чем при маленьких. Вот про этот характер роста вам и надо дать ответ.
Похожи ли друг на друга графики с разным показателем степени? Как можно превратить один в другой?
Если вы что-нибудь слышали про логарифм, то обратите внимание, что вы экспериментально получили одно из свойств этой функции.
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$ и с ростом основания степени?
Сравните показательные и степенные функции. Охарактеризуйте их рост.
Как охарактеризовать рост функции?
Если график - прямая линия, то с ростом $x$ он всегда меняется одинаково: на сколько увеличилось $x$, на столько изменилось значение на графике. Но может быть и по-другому: при больших $x$ значения на графике могут меняться медленнее или быстрее, чем при маленьких. Вот про этот характер роста вам и надо дать ответ.
А если график - какая-то непонятная ломаная? Тогда возьмём какую-нибудь "понятную" функцию $f(x)$ и найдём два числа А и В, такие что при больших значениях $x$ "наша" функция будет больше, чем $f(x)\cdot A$ и меньше, чем $f(x)\cdot B$. Тогда говорят, что "наша" функция растёт также, как и $f(x)$.
Сравните с результатами предыдущей задачи.
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.legend().
На вход даётся число $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.$$
Добейтесь, чтобы разница между $\alpha$ и $\beta$ была хотя бы 0.3 (а лучше - 0.2 или даже 0.1)
Проведите серию экспериментов.
В комментариях ответьте на вопрос: какое из чисел $C_n^k$ при фиксированном $n$ самое большое. Почему?
Как выглядят графики при достаточно больших $n$?
При вычислении последовательностей не надо использовать функцию factorial. Используйте рекуррентную формулу - вычисляйте в цикле следующее значение последовательности на основе известного предыдущего.
Будьте внимательны: в вычислениях используйте целочисленные операции! Если в промежуточных вычислениях будут появляться действительные числа, это может привести к неверным результатам при больших $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$.
