Текст книги "Рассказы о математике с примерами на языках Python и C (СИ)"
Автор книги: Дмитрий Елисеев
Жанры:
Базы данных
,сообщить о нарушении
Текущая страница: 1 (всего у книги 4 страниц)
Дмитрий Елисеев
Рассказы о математике с примерами на языках Python и C
Версия текста 1.0. (с) 2017
Введение
Как сказал еще Галилей, «Книга природы написана на языке математики», и с этим сложно не согласиться. Математика это универсальный язык науки, это базовые принципы, на которых построена вся Вселенная. 2 + 2 = 4 независимо от того, верим мы в это или нет, знаем мы это или нет, существуем мы вообще или нет, и это будет верно не только для нас, но и для жителя Альфы Центавра.
Из этого следует важное правило: математические законы нельзя придумать, их можно только открыть. Треугольник подчинялся теореме Пифагора еще до того, как Пифагор открыл и сформулировал известную теорему. Число Пи было вычислено в древнем Китае, но его значение было таким всегда – еще до того как появился не только Китай, но и наша планета Земля.
Именно поэтому я надеюсь, что кто-то из читателей с помощью этой книги откроет для себя в математике что-то новое. Увы, в представлении большинства, математика – это достаточно скучная наука, вероятно так ее преподают в школе. Если кто-то с помощью этой книги найдет для себя что-то новое, можно считать что время было потрачено не зря.
Эта книга не задачник, а скорее сборник рассказов о тех или иных математических вопросах. Т. к. математические примеры без цифр бессмысленны, «практическая» часть дается на языках программирования Python и Си.
Номер версии в заголовке указан неслучайно. Эта книга не закончена, и по мере появления каких-то новых интересных вопросов она будет дополняться. Желающие также могут присылать свои истории или задачи по адресу [email protected], наиболее интересные из них будут включены в текст. Обо найденных неточностях также просьба писать на этот адрес.
Книга распространяется бесплатно в электронном виде. Печатную версию желающие могут сделать себе самостоятельно. В архиве также приложены все файлы программ. Наличие новой версии можно проверить на странице http://dmitryelj.spb.ru/math.htm.
Приятного чтения.
Елисеев Дмитрий
История версий текста: 04.2017 – 1.0
1. Основы языков Python и Си
Математика немыслима без расчетов и примеров вычислений. Примеры в данной книге иллюстрируются фрагментами кода на языке Python. Этот язык удобен тем, что он очень прост и подходит для начинающих, поэтому кратко рассмотрим как им пользоваться.
Для использования языка Python нужно установить интерпретатор языка с сайта https://www.python.org/downloads/ или воспользоваться онлайн-версией, например на странице https://repl.it/languages/python3. Все примеры из книги работоспособны с любой версией языка Python, 2.7 или 3.
Для запуска программы необходимо:
‐ Сохранить файл в Блокноте с любым именем и расширением .py, например test1.py (удобно также создать папку в корне диска C, например C:PythonApps).
‐ Открыть консоль (нажать Win+R и набрать cmd), в консоли набрать команду (без кавычек) «python путь_к_файлу.py», например «python C:PythonAppstest1.py».
Как более удобный вариант, можно скачать бесплатную среду разработки PyСharm community edition, и редактировать и запускать файлы в ней. Скачать PyСharm можно со страницы https://www.jetbrains.com/pycharm/download/.
Для запуска программы на языке Си, ее сначала надо сохранить файле с расширением .c, и выполнить команду «gcc имя_файла.c». Будет создан exe-файл, который можно запустить.
Минимальная программа на Си выглядит так:
#include
int main()
{
printf(«Hello worldn»);
return 0;
}
Рассмотрим простые примеры использования.
Объявление и вывод переменных
Python: достаточно ввести имя и значение.
x = 3 y = 10
print(«x=», x)
print(x + y)
В отличие от языка C++, тип переменной будет определен автоматически, указывать его не нужно. Кстати, его можно узнать, введя print (type(x)).
Cи: необходимо указать тип и значение переменной.
int x = 3;
int y = 10;
printf(«x=%dn», x);
printf(«%dn», x+y);
Циклы
В отличие от того же С++ или Java, циклы задаются отступами, что после других языков программирования может быть непривычным. Часть кода, находящаяся внутри цикла, будет выполнена заданное количество раз.
Python
Вывод чисел от 1 до 9:
for p in range(1, 10):
print (p)
Вывод чисел от 1 до 9 с шагом 2:
for p in range(1, 10, 2):
print (p)
Си
Вывод чисел от 1 до 9:
for(int i=1; i<10; i++) {
printf(«%dn», i);
}
Вывод чисел от 1 до 9 с шагом 2:
for(int i=1; i<10; i+=2) {
printf(«%dn», i);
}
Массивы
Массив это линейный набор чисел, с которыми удобно выполнять однотипные операции, например вычисление суммы или среднего арифметического.
Python
Объявляем массив чисел:
values = [1, 2, 3, 5, 10, 15, 20]
Добавляем элемент в массив:
values.append(7)
Выводим массив на экран:
print(values)
Выводим элементы массива построчно:
for p in values:
print(p)
Это же можно сделать с помощью индексов (нумерация элементов массива начинается с 0):
for i in range(0, len(values)):
print (values[i])
Си: Динамические массивы поддерживаются только в C++, статические массивы создаются так:
int values[7] = { 1,2,3,5,10,15,20 };
for(int i=0; i<7; i++) {
printf(«%dn», values[i]);
}
При желании можно слегка схитрить, если максимальный размер массива заранее известен.
int values[255] = { 1,2,3,5,10,15,20 }, cnt = 7;
for(int i=0; i
printf(«%dn», values[i]);
}
values[cnt] = 7;
cnt++;
Можно пользоваться динамическим распределением памяти, хотя это немного сложнее:
int *valuesArray = (int*)malloc(10*sizeof(int));
valuesArray[0] = 1;
valuesArray[1] = 3;
valuesArray[2] = 15;
valuesArray = (int*)realloc(valuesArray, 25*sizeof(int));
valuesArray[20] = 555;
valuesArray[21] = 777;
for(int i=0; i<25; i++) {
printf(«%dn», valuesArray[i]);
}
free(valuesArray);
Важно заметить, что неинициализированные значения массива, например valuesArray[16], будут содержать «мусор», некие значения которые были до этого в памяти. Си достаточно низкоуровневый язык, и такие моменты нужно учитывать. Хорошим тоном является инициализация всех переменных при их описании. Вот такой код формально не содержит ошибок:
int x;
printf(«x=%dn», x);
Однако при его запуске выведется значение 4196608, или 0, или 32, результат непредсказуем. В большой программе такие ошибки может быть сложно найти, тем более что проявляться они могут не всегда.
Арифметические операции
Сложение, умножение,деление:
x1 = 3
x2 = (2 * x1 * x1 + 10*x1 + 7)/x1
Возведение в степень:
x3 = x1**10
print(x1, x2, x3)
Переменную также можно увеличить или уменьшить:
x1 += 1
x1 -= 10
print(x1)
Остаток от деления:
x2 = x1 % 6
print(x2)
Подсчитаем сумму элементов массива:
values = [1,2,3,5,10,15,20]
sum = 0
for p in values:
sum += p
print(sum)
Для более сложных операций необходимо подключить модуль math. Вычисление квадратного корня:
import math
print(math.sqrt(x3))
Условия задаются отступами, аналогично циклам:
print (x1)
if x1 % 2 == 0:
print(«x1 четное число»)
else:
print(«x1 нечетное число»)
Python может делать вычисления с большими числами, что достаточно удобно:
x1 = 12131231321321312312313131124141
print(10 * x1)
print(math.sqrt(x1))
Можно вывести даже факториал числа 1024, что не сделает ни один калькулятор:
print(math.factorial(1024))
В Си вычисление суммы элементов массива выглядит так:
int sum = 0;
for(int i=0; i
sum += values[i];
}
printf(«Sum=%dn», sum);
Пожалуй, этого не хватит чтобы устроиться на работу программистом, но вполне достаточно для понимания большинства примеров в книге. Теперь вернемся к математике.
2. Математические фокусы
Для «разминки» рассмотрим несколько фокусов, имеющих отношение к числам. Никаких особых сложностей в них нет, но их знание поможет развеселить или удивить знакомых знанием математики.
Умножение в уме числа на 11
Рассмотрим простой пример: 26 * 11 = 286
Сделать это в уме просто, если взять сумму чисел и поместить в середину: 26 * 11 = 2 [2+6] 6
Аналогично 43 * 11 = 473, 71 * 11 = 781 и так далее.
Чуть длиннее расчет, если сумма чисел больше либо равна 10. Но и тогда все просто: в середину кладется младший разряд, а 1 уходит в старший разряд:
47 * 11 = [4] [4 + 7 = 11] [7] = [4 + 1] [1] [7] = 517
94 * 11 = [9] [9 + 4 = 13] [4] = [10] [3] [4] = 1034
Возведение в квадрат числа, оканчивающегося на 5
Подсчитать это тоже просто. Если число рассмотреть как пару NM, то первая часть результата – это число N, умноженное на (N + 1), вторая часть числа – всегда 25. 352 = [3 * 4] [25] = 12 25
Аналогично:
252 = [2 * 3] 25 = 625 852= [8*9] 25 = 7225 и так далее.
Отгадывание результата
Попросим человека загадать любое число. Например 73. Затем чтобы еще больше запутать отгадывающего, попросим сделать следующие действия:
‐ удвоим число (146)
‐ прибавляем 12 (158)
‐ разделим на 2 (79)
‐ вычтем из результата исходное число (79 – 73 = 6)
В конце мы отгадываем, что результат – 6. Суть в том, что число 6 появляется независимо от того, какое число загадал человек.
Математически, это доказывается очень просто:
(2 * n + 12) / 2 – n = n + 6 – n = 6, независимо от значения n.
Отгадывание чисел
Есть другой фокус с отгадыванием чисел. Попросим человека загадать трехзначное число, числа в котором идут в порядке уменьшения (например 752). Попросим человека выполнить следующие действия:
‐ записать число в обратном порядке (257)
‐ вычесть его из исходного числа (752 – 257 = 495)
‐ к ответу добавить его же, только в обратном порядке (495 + 594)
Получится число 1089, которое «фокусник» и объявляет публике.
Математически это тоже несложно доказать.
‐ Любое число вида abc в десятичной системе счисления представляется так:
abc = 100 * a + 10 * b + c.
‐ Разность чисел abc – cba:
100 * a + 10 * b + c + 100 – 100 * c – 10 * b – a = 100 * a – 100 * c – (a – c) = 100 * (a – c) – (a – c)
‐ Т. к. по условию a – c > 0, то результат можно записать в виде:
100 * (a – c) – (a – c) = 100 * (a – c) – 100 + 90 + 10 – (a – c) = 100 * (a – c – 1) + 10 * 9 + (10 – a + c)
Мы узнали разряды числа, получающегося в результате:
a1 = a – c – 1, b1 = 9, c1 = 10 – a + c
‐ Добавляем число в обратном порядке:
a1b1c1 + c1b1a1 = 100 * (a – c – 1) + 10 * 9 + (10 – a + c) + 100* (10 – a + c) + 10 * 9 + a – c – 1
Если раскрыть все скобки и сократить лишнее, в остатке будет 1089.
3. Число Пи
Вобьем в стену гвоздь, привяжем к нему веревку с карандашом, начертим окружность. Как вычислить длину окружности? Сегодня ответ знает каждый школьник – с помощью числа Пи. Число Пи – несомненно, одна из основных констант мироздания, значение которой было известно еще в древности. Оно используется везде, от кройки и шитья до расчетов гармонических колебаний в физике и радиотехнике.
Сегодня достаточно нажать одну кнопку на калькуляторе, чтобы увидеть его значение: Pi = 3,1415926535… Однако, за этими цифрами скрывается многовековая история. Что такое число Пи? Это отношение длины окружности к ее диаметру. То что это константа, не зависящая от самой длины окружности, знали еще в древности. Но чему она равна? Есть ли у этого числа какая-то внутренняя структура, неизвестная закономерность? Узнать это хотели многие. Самый простой и очевидный способ – взять и измерить. Примерно так вероятно и поступали в древности, точность разумеется была невысокой. Еще в древнем Вавилоне значение числа Пи было известно как 25/8. Затем Архимед предложил первый математический метод вычисления числа Пи, с помощью расчета вписанных в круг многоугольников. Это позволяло вычислять значение не «напрямую», с циркулем и линейкой, а математически, что обеспечивало гораздо большую точность. И наконец в 3-м веке нашей эры китайский математик Лю Хуэй придумал первый итерационный алгоритм – алгоритм, в котором число вычисляется не одной формулой, а последовательностью шагов (итераций), где каждая последующая итерация увеличивает точность. С помощью своего метода Лю Хуэй получил Пи с точностью 5 знаков: π = 3,1416. Дальнейшее увеличение точности заняло сотни лет. Математик из Ирана Джамшид ибн Мас‘уд ибн Махмуд Гияс ад-Дин ал-Каши в 15-м веке вычислил число Пи с точностью до 16 знаков, а в 17-м веке голландский математик Лудольф вычислил 32 знака числа Пи. В 19-м веке англичанин Вильям Шенкс, потратив 20 лет, вычислил Пи до 707 знака, однако он так и не узнал, что в 520-м знаке допустил ошибку и все последние годы вычислений оказались напрасны (в итерационных алгоритмах хоть одна ошибка делает все дальнейшие шаги бесполезными).
Что мы знаем о числе Пи сегодня? Действительно, это число весьма интересно:
‐ Число Пи является иррациональным: оно не может быть выражено с помощью дроби вида m/n. Это было доказано только в 1761 году.
‐ Число Пи является трансцендентным: оно не является корнем какого-либо уравнения с целочисленными коэффициентами. Это было доказано в 1882 году.
‐ Число Пи является бесконечным.
‐ Интересное следствие предыдущего пункта: в числе Пи можно найти практически любое число, например свой собственный номер телефона, вопрос лишь в длине последовательности которую придется просмотреть. Можно подтвердить, что так и есть: скачав архив с 10 миллионами знаков числа Пи, я нашел в нем свой номер телефона, номер телефона квартиры где я родился, и номер телефона своей супруги. Но разумеется, никакой «магии» тут нет, лишь теория вероятности. Можно взять любую другую случайную последовательность чисел такой же длины, в ней также найдутся любые заданные числа.
И наконец, перейдем к формулам вычисления Пи, т. к. именно в них можно увидеть красоту числовых взаимосвязей – то, чем интересна математика.
Формула Лю-Хуэя (3й век):
Формула Мадхавы-Лейбница (15 век):
Формула Валлиса (17 век):
Формула Мэчина (18 век):
Попробуем вычислить число Пи по второй формуле. Для этого напишем простую программу на языке Python:
sum = 0.0
sign = 1
for p in range(0,33):
sum += 4.0 * sign / (1 + 2 * p)
print(p, sum)
sign = -sign
Запустим программу в любом онлайн-компиляторе языка Питон (например https://repl.it/languages/python3). Получаем результат:
Шаг Значение
0 4.0
1 2.666666666666667
2 3.466666666666667
3 2.8952380952380956
4 3.3396825396825403
5 2.9760461760461765
6 3.2837384837384844
7 3.017071817071818
8 3.2523659347188767
9 3.0418396189294032
10 3.232315809405594
11 3.058402765927333
12 3.2184027659273333
13 3.0702546177791854
14 3.208185652261944
15 3.079153394197428
16 3.200365515409549
17 3.0860798011238346
18 3.1941879092319425
19 3.09162380666784
20 3.189184782277596
21 3.0961615264636424
22 3.1850504153525314
23 3.099944032373808
24 3.1815766854350325
25 3.1031453128860127
26 3.1786170109992202
27 3.1058897382719475
28 3.1760651768684385
29 3.108268566698947
30 3.1738423371907505
31 3.110350273698687
32 3.1718887352371485
Как можно видеть, сделав 32 шага алгоритма, мы получили лишь 2 точных знака. Видно, что алгоритм работает, но количество вычислений весьма велико. Как известно, в 15-м веке индийский астроном и математик Мадхава использовал более точную формулу, получив точность числа Пи в 11 знаков:
Попробуем воспроизвести ее в виде программы, чтобы примерно оценить объем вычислений.
Первым шагом необходимо вычислить √12. Возникает резонный вопрос – как это сделать? Оказывается, уже в Вавилоне был известен метод вычисления квадратного корня, который сейчас так и называется «вавилонским». Суть его в вычислении √S по простой формуле:
Здесь x0 – любое приближенное значение, например для √12 можно взять 3.
Запишем формулу в виде программы:
from decimal import Decimal
print («Квадратный корень:»)
number = Decimal(12)
result = Decimal(3)
for p in range(1, 9):
result = (result + number / result)/Decimal(2)
difference = result**2 – number
print (p, result, difference)
sqrt12 = result
Результаты весьма интересны:
Шаг | Значение | Погрешность |
1 | 3.5 | 0.25 |
2 | 3.464285714285714 | 0.00127 |
3 | 3.464101620029455 | 3.3890E-8 |
4 | 3.464101615137754 | 2.392873369E-17 |
Результат: √12 = 3,464101615137754
Как можно видеть, сделав всего 4 шага, можно получить √12 с достаточной точностью, задача вполне посильная даже для ручных расчетов 15 века.
Наконец, запрограммируем вторую часть алгоритма – собственно вычисление Пи.
sum = Decimal(1)
sign = -1
for p in range(1,32):
sum += Decimal(sign) / Decimal((2 * p + 1)*(3**p))
sign = -sign
print(p, sqrt12 * sum)
print(«Result:», sqrt12 * sum)
Результаты работы программы:
Шаг Значение
1 3.079201435678004077382126829
2 3.156181471569954179316680000
3 3.137852891595680345522738769
4 3.142604745663084672802649458
5 3.141308785462883492635401088
6 3.141674312698837671656932680
7 3.141568715941784242161823554
8 3.141599773811505839072149767
9 3.141590510938080099642754230
10 3.141593304503081513121460820
11 3.141592454287646300323593597
12 3.141592715020379765581606212
13 3.141592634547313881242713430
14 3.141592659521713638451335328
15 3.141592651733997585128216671
16 3.141592654172575339199092210
17 3.141592653406165187919674184
18 3.141592653647826046431202391
19 3.141592653571403381773710565
20 3.141592653595634958372427485
21 3.141592653587933449530974820
22 3.141592653590386522717511595
23 3.141592653589603627019680710
24 3.141592653589853940610143646
Уже на 24-м шаге мы получаем искомые 11 знаков числа Пи. Задача явно требовала больше времени чем сейчас, но вполне могла быть решена в средние века.
Современные формулы не столь просты внешне, зато работают еще быстрее. Для примера можно привести формулу Чудновского:
Для сравнения, те же 24 итерации по этой формуле дают число Пи со следующей точностью:
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249.
Если сделать 100 итераций и вычислить 1000 знаков Пи, то можно увидеть так называемую «точку Фейнмана»:
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420207
Это последовательность «999999», находящаяся на 762-м знаке от начала. Желающие могут поэкспериментировать дальше самостоятельно с помощью программы на языке Python:
from math import factorial
from decimal import *
def chudnovsky(n):
pi = Decimal(0)
k = 0
while k < n:
pi += (Decimal(-1)**k) * (Decimal(factorial(6 * k)) / ((factorial(k)**3) * (factorial(3*k))) * (13591409 + 545140134 * k) / (640320**(3 * k)))
k += 1
print(«Шаг: {} из {}».format(k, n))
pi = pi * Decimal(10005).sqrt() / 4270934400
pi = pi**(-1)
return pi
# Требуемая точность (число знаков)
N = 1000
getcontext().prec = N
val = chudnovsky(N / 14)
print(val)
Эта программа не оптимизирована, и работает довольно-таки медленно, но для ознакомления с сутью алгоритма этого вполне достаточно. Кстати, с помощью формулы Чудновского два инженера Александр Йи и Сингеру Кондо в 2010 году объявили о новом мировом рекорде вычисления Пи на персональном компьютере: 5 трлн знаков после запятой. Компьютеру с 12 ядрами, 97 Гб памяти и 19 жесткими дисками потребовалось 60 дней для выполнения расчетов.
На этом мы закончим с числом Пи, хотя с ним конечно, связано куда больше интересных фактов. Например 3 марта (т. е. 03.14) отмечается международный «день числа Пи», ну а другие факты читатели могут поискать самостоятельно.
