В этом листке мы будем изучать асимптотику факториалов и чисел Cnk, строить графики в библиотеке matplotlib, а также рисовать фракталы черепашкой.
Библиотека matplotlib предназначена для построения практически сколь угодно сложных графиков и диаграмм.
Про неё шутят, что простые вещи в ней делать просто, а сложные — ... теоретически возможно.
Для установки библиотеки нужно запустить следующую программу:
Если в результате её запуска вывод будет примерно такой как ниже, то у вас успех!
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 что-то ещё
Вот типичный простой пример программы, которая строит простой график:
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() — запуск окна, в котором отображается наша картина.
Напишите функцию linspace,
принимающую на вход действительные числа x, y и натуральное число n,
и возвращающую список с арифметической прогрессией a1,a2,…,an, в которой a1=x и an=y.
Этой функций удобно пользоваться для построение графиков функций.
Предположим, что функцию linspace из первой задачи вы уже написали.
Тогда рисовать графики можно так:
import matplotlib.pyplot as plt
from math import sin, cos, sqrt
deflinspace(x, y, n):
...
return [... for i inrange(n+1)]
fig, ax = plt.subplots()
xx = linspace(-5, 5, 101)
yy1 = [1/6 * x ** 2 - 2for 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()
На вход даются числа a,b,c.
На отрезке [−5,5] постройте четыре параболы по 101 точкам:
y=ax2+bx+c,
y=(a+0.1)x2+bx+c,
y=ax2+(b+0.1)x+c,
y=ax2+bx+(c+0.1).
Не меняйте никаких автоматических параметров графика.
Используйте функцию linspace из предыдущей задачи.
Проведите серию экспериментов.
В комментариях ответьте на вопрос: при каких условиях изменение одного из коэффициентов на 0.1 значительно влияют на график параболы и её корни.
Проведите серию экспериментов.
В комментариях ответьте на вопрос: как будет устроен прогресс двух людей за год,
один из которых каждый прогрессирует на 1%, а другой — регрессирует на 1%.
На вход даётся число n.
Постройте графики количества двоичных цифр в числах:
12,22,…,n2;
13,23,…,n3;
14,24,…,n4;
Количество двоичных цифр можно получить при помощи метода .bit_length().
Не меняйте никаких автоматических параметров графика.
В этой задаче все значения x целые, поэтому функция linspace не требуется.
Используйте просто подходящий range.
Проведите серию экспериментов.
В комментариях ответьте на вопрос: как число двоичных цифр изменяется с ростом n и с ростом показателя степени, в которую n возводится?
На вход даётся число n.
Постройте графики количества двоичных цифр в числах:
21,22,…,2n;
31,32,…,3n;
41,42,…,4n;
В этой задаче все значения x целые, поэтому функция linspace не требуется.
Используйте просто подходящий range.
Проведите серию экспериментов.
В комментариях ответьте на вопрос: как число двоичных цифр изменяется с ростом n и с ростом основания степени?
Сравните показательные и степенные функции. Охарактеризуйте их рост.
На вход даётся число n.
Постройте графики количества двоичных цифр в числах:
12,22,…,n2;
21,22,…,2n;
1!,2!,…,n!;
11,22,…,nn;
Для вычисления факториала используйте функцию factorial из модуля math.
Проведите серию экспериментов.
В комментариях упорядочьте функции n2, 2n, n! и nn по возрастанию и охарактеризуйте разницу в их росте.
Рост каких функций «похож» друг на друга при очень больших n (порядка 2000)?
Во сколько раз примерно отличается количество двоичных цифр в 1000! и в 22000?
Попробуйте заменить число 2 в показателе и основании степени на другие: 0.5, 0.9, 1.001, 2, 3. Как меняются функции?
Для сравнения нарисуйте их все вместе, подписывая графики. Для этого нужно добавлять параметр label (ax.plot(..., label='2**n'),
а перед выводом графика добавить команду ax.legend().
На вход даётся число n.
Постройте графики количества двоичных цифр в числах:
(31)1,(32)2,…,(3n)n;
1!,2!,…,n!;
(21)1,(22)2,…,(2n)n;
Используйте целочисленное деление.
Проведите серию экспериментов.
Попробуйте подобрать такие числа α и β так, чтобы «зазор» между графиками функций был как можно меньше и при больших n выполнялось неравенство:
(αn)n<n!<(βn)n.
На вход даётся число n.
Постройте графики следущих последовательностей:
Cn−10,Cn−11,…,Cn−1n−1;
Cn0,Cn1,…,Cnn;
Cn+10,Cn+11,…,Cn+1n+1;
Проведите серию экспериментов.
В комментариях ответьте на вопрос: какое из чисел Cnk при фиксированном n самое большое. Почему?
Как выглядят графики при достаточно больших n?
На вход даётся число n.
Постройте графики количества двоичных цифр в следущих последовательностях:
Cn−10,Cn−11,…,Cn−1n−1;
Cn0,Cn1,…,Cnn;
Cn+10,Cn+11,…,Cn+1n+1;
Проведите серию экспериментов.
В комментариях ответьте на вопрос: что напоминают графики при больших n?
Насколько они отличаются друг от друга?
На вход даётся число n.
Постройте графики количества двоичных цифр в следущих последовательностях:
C1[1/4],C2[2/4],…,Cn[n/4];
C1[1/3],C2[2/3],…,Cn[n/3];
C1[1/2],C2[2/2],…,Cn[n/2];
Какой функцией можно неплохо приблизить Cn[n/2] при достаточно большом n?
Проведите серию экспериментов.
В комментариях ответьте на вопрос: как устроен рост чисел Cn[αn] с ростом n при фиксированном α?
Попробуйте как можно точнее определить асимптотику Cn[n/2].
В этой задаче мы попытаемся точно установить асимптотику факториала.
Мы уже видели, как устроен рост степенной и показательной функций, факториала и функции nn.
Попробуем собрать факториал из этих «кирпичиков».
А именно представим n! так:
n!≈C⋅nγ⋅αn⋅nn.
То есть в виде произведения константы, степенной функции, показательной функции и nn.
Для определения констант C,γ,α нам пригодится функция,
которая вычисляет отношение факториала к нашей функции.
Напишите функцию f_ratio(n, C, ga, al), которая вычисляет число
C⋅nγ⋅αn⋅nnn!.
Ответ будет проверяться с относительной точностью 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, и вся информация потеряется.
Поэтому распишем ответ в виде
C⋅nγ1⋅αn1⋅αn2⋅…⋅αnn−1⋅αnn.
Распределим множители в два списка: список чисел, больших 1, и список чисел, меньших 1.
Дальше пока оба списка не пусты, будем брать множитель, больший 1, если текущее произведение меньше 1, и наоборот.
Проведите серию экспериментов.
Сначала подберите такие числа α1 и α2, что ∣α1−α2∣≤0.01, и
0<f_ratio(1000,1,0,α1)≤1≤f_ratio(1000,1,0,α2).
(При n=1000 константа и степенная функция представляют из себя практически «незначительный множитель»).
Затем подберите такое число γ, что 1/2<f_ratio(100,1,γ,α1)≤1≤f_ratio(100,1,γ,α2)
Теперь в качестве C возьмите (f_ratio(10,1,γ,α1)+f_ratio(10,1,γ,α2))/2.
Первое приближение готово. Дальше нужно виртуозно повторять этот цикл, увеличивая n и уточняя полученные константы.
Когда константы будут получены с хорошей точностью, нужно попробовать угадать их точные значения.
Для каждой константы x полезно посмотреть на x,1/x,2x,x/2,1/(2x),2/x,x2,2x2,x2/2 и т.п., среди подобных чисел должны встретиться знакомые.
Если константы правильные, то число f_ratio(107,C,γ,α) будет отличаться от 1 не больше, чем на 10−8.
Не так плохо, учитывая, что 10000000!≈1.2024234⋅1065657059.
В этой задаче мы будем исследовать случайные блуждания.
Случайное блуждание — математическая модель процесса случайных изменений — шагов в дискретные моменты времени.
Будем рассматривать самый простейший случай: в каждый момент времени делается шаг либо «налево», либо «направо».
Итак, стартуем из точки (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.
Библиотека 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() # Задержать окно на экране
Кривая Коха — фрактальная кривая, описанная в 1904 году шведским математиком Хельге фон Кохом.
Кривая Коха является типичным геометрическим фракталом. Процесс её построения выглядит следующим образом: берём единичный отрезок, разделяем на три равные части и заменяем средний интервал равносторонним треугольником без этого сегмента. В результате образуется ломаная, состоящая из четырёх звеньев длины 1/3. На следующем шаге повторяем операцию для каждого из четырёх получившихся звеньев и т. д… Предельная кривая и есть кривая Коха.
Строить фрактальные кривые очень удобно при помощи рекурсивных процедур, получающих на вход глубину рекурсии и линейный размер кривой (или какой-то её конкретной части).
На вход даётся неотрицательное число n.
Постройте кривую «степени» n.
Треугольник Серпинского — фрактал, один из двумерных аналогов множества Кантора, предложенный польским математиком Вацлавом Серпинским в 1915 году. Также известен как «решётка» или «салфетка» Серпинского.
На вход даётся неотрицательное число n.
Постройте границу салфетки Серпинского «степени» n.
Кривая Минковского — классический геометрический фрактал, предложенный Минковским. Инициатором является отрезок, а генератором является ломаная из восьми звеньев (два равных звена продолжают друг друга).
На вход даётся неотрицательное число n.
Постройте кривую «степени» n.
В ледяном фрактале всё начинается с отрезка.
На каждом шаге в центре каждого отрезка «отрастают» два «уса» под углом 60 градусов длиной одна четверть от исходного отрезка.
На вход даётся неотрицательное число n.
Постройте кривую «степени» n.
Считается, что такое название фрактал получил за сходство с традиционными китайскими драконами. По крайней мере, так показалось ученым, которые впервые его исследовали. Каждая ломаная-дракон является лишь приближением к дракону-фракталу и состоит из отрезков. Ломаная с номером n будет состоять из 2n отрезков.
Итак, возьмём полоску бумаги и сложим её несколько раз пополам, а затем развернем так чтобы между углами сгиба образовались прямые углы. В итоге мы получим кривую дракона. Поскольку толщина сложенной полоски каждый раз удваивается, а длина отдельного звена уменьшается в два раза, то мы не можем получить таким наивным способом длинных кривых.
К счастью длинные кривые легко рисуются другим способом.
На вход даётся неотрицательное число n.
Постройте кривую «степени» n.
Ориентация кривой важна, первый поворот — налево.
В этой задаче мы будем строить то, что называют «обнаженное обдуваемое ветром дерево Пифагора».
Классическое дерево Пифагора состоит из множества квадратов (см. раз, два).
На вход даётся неотрицательное число n, и два угла α и β.
Необходимо построить дерево «степени» n.
Для этого нужно построить отрезок, клонировать черепашку командой T.clone().
Первую черепашку нужно повернуть на угол α налево, а вторую — на угол β направо.
После чего приказать каждой черепашке построить по такому же дереву Пифагору на единицу меньшей степени.
Длина каждого следующего отрезка в глубь должна быть в 2 раза меньше предыдущего.
PS. Вероятно, саму черепашку, которая будет рисовать дерево, нужно передавать внутрь рекурсивной функции.
from turtle import *
bgcolor("gray60")
pu()
speed(0)
ht()
shape("square")
shapesize(3.2, 3.5)
shift = [10, 0, 10, 28, 10, 0, 10, 28, 10]
tracer(False)
for i in range(9):
goto(-365 + shift[i], 267-66*i)
color("black")
for i in range(11):
stamp()
fd(70)
if pencolor() == "white":
color("black")
else:
color("white")
mainloop()
Скрыть пример
Гравитация — комета-черепашка вокруг солнца
from turtle import *
color("orange")
dot(10)
center = pos()
color("blue")
shape("turtle")
speed(0)
penup()
goto(200, 0)
pendown()
G = 800
v = Vec2D(0, 1)
t = 0
dt = 1
while t < 1100:
goto(pos() + v * dt)
setheading(towards(center))
r = distance(center)
acc = (-G / r ** 3) * pos()
v += acc * dt
t += dt
mainloop()
Скрыть пример
Управляем космическим кораблём
from turtle import *
from math import sin, cos, pi
FORCE_UNIT = 0.1 # Ускорение двигателя
HEIGHT = 350
WIDTH = 250
def one_step(): # Одна итерация движения
global speed_x, speed_y # Глобальные переменные, в которых хранится текущая скорость
cur_x, cur_y = position() # Получаем текущие координат
cur_x += speed_x # Двигаем "корабль"
cur_y += speed_y
setpos(cur_x, cur_y)
if abs(cur_x) > WIDTH: # Проверяем, что не улетели слишком далеко
speed_x *= -1
if abs(cur_y) > HEIGHT:
speed_y *= -1
def turn_left(): # Была нажата клавиша "Налево"
left(10)
def turn_right(): # Была нажата клавиша "Направо"
right(10)
def exit(): # Была нажата клавиша Escape, завершаем работу
global continue_game
continue_game = False
def speed_up(): # Была нажата клавиша "Вверх"
global speed_x, speed_y # Глобальные переменные, в которых хранится текущая скорость
alpha = heading() * pi / 180.0 # Получаем текущий угол в радианах
speed_x += FORCE_UNIT * cos(alpha) # Ускоряемся
speed_y += FORCE_UNIT * sin(alpha)
def main():
reset()
global speed_x, speed_y # Глобальные переменные, в которых хранится текущая скорость
global continue_game
speed_x = speed_y = 0
continue_game = True
speed(0) # Перемещаться будем мгновенно
pensize(2) # И рисовать за собой линию
shape("turtle") # Форма курсора
fillcolor("blue") # Цвет черепашки
pencolor("red") # Цвет линии
onkeypress(turn_left, "Left") # По нажатию кнопки "Налево" вызвать функцию turnleft()
onkeypress(turn_right, "Right") # ...
onkeypress(speed_up, "Up") # ...
onkey(exit, "Escape") # По нажатию кнопки Escape завершить работу
listen() # Начинаем "слушать" нажатия клавиш
while continue_game:
one_step() # Запускаем основной цикл
bye()
main()
Скрыть пример
Пример от разработчкиков turtle
from turtle import *
def switchpen():
if isdown():
pu()
else:
pd()
def demo2():
"""Demo of some new features."""
speed(1)
st()
pensize(3)
setheading(towards(0, 0))
radius = distance(0, 0)/2.0
rt(90)
for _ in range(18):
switchpen()
circle(radius, 10)
write("wait a moment...")
while undobufferentries():
undo()
reset()
lt(90)
colormode(255)
laenge = 10
pencolor("green")
pensize(3)
lt(180)
for i in range(-2, 16):
if i > 0:
begin_fill()
fillcolor(255-15*i, 0, 15*i)
for _ in range(3):
fd(laenge)
lt(120)
end_fill()
laenge += 10
lt(15)
speed((speed()+1)%12)
#end_fill()
lt(120)
pu()
fd(70)
rt(30)
pd()
color("red","yellow")
speed(0)
begin_fill()
for _ in range(4):
circle(50, 90)
rt(90)
fd(30)
rt(90)
end_fill()
lt(90)
pu()
fd(30)
pd()
shape("turtle")
tri = getturtle()
tri.resizemode("auto")
turtle = Turtle()
turtle.resizemode("auto")
turtle.shape("turtle")
turtle.reset()
turtle.left(90)
turtle.speed(0)
turtle.up()
turtle.goto(280, 40)
turtle.lt(30)
turtle.down()
turtle.speed(6)
turtle.color("blue","orange")
turtle.pensize(2)
tri.speed(6)
setheading(towards(turtle))
count = 1
while tri.distance(turtle) > 4:
turtle.fd(3.5)
turtle.lt(0.6)
tri.setheading(tri.towards(turtle))
tri.fd(4)
if count % 20 == 0:
turtle.stamp()
tri.stamp()
switchpen()
count += 1
tri.write("CAUGHT! ", font=("Arial", 16, "bold"), align="right")
tri.pencolor("black")
tri.pencolor("red")
def baba(xdummy, ydummy):
clearscreen()
bye()
while undobufferentries():
tri.undo()
turtle.undo()
tri.fd(50)
tri.write(" Click me!", font = ("Courier", 12, "bold") )
tri.onclick(baba, 1)
demo2()
