Текст книги "Рассказы о математике с примерами на языках Python и C (СИ)"

Автор книги: Дмитрий Елисеев

сообщить о нарушении

Текущая страница: 3 (всего у книги 4 страниц)

8. Магический квадрат из простых чисел

Существует еще одна разновидность магического квадрата – составленного из простых чисел. Пример такого квадрата показан на рисунке:

29	131	107
167	89	11
71	47	149

Приведенную выше программу легко модифицировать для такого расчета: достаточно лишь заменить множество digits = set(range(1, 16 + 1)) на другое, содержащее простые числа.

Для примера будем искать квадраты среди трехзначных простых чисел от 101 до 491. Заменим в предыдущей версии программы строку digits = set([1, 2, 3, 4, 5, 6, 7, 8, 9]) на

primes = [ 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,

      167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,

      257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,

      353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,

      449, 457, 461, 463, 467, 479, 487, 491 ]

digits = set(primes)

Таких квадратов нашлось 40, например:

233	167	389
419	263	107
137	359	293

Сумма чисел равна вполне красивому числу 789.

Т. к. число вариантов перебора больше, программа работает дольше. Время поиска составило 724 с для Python-версии и 316 c для программы на C++.

T = 316.00s = C++

T = 724.4s = Python

Если же рассматривать минимально возможный квадрат из простых чисел, то его сумма равняется тоже вполне «красивому» числу 111:

7	61	43
73	37	1
31	13	67

Примером квадрата 4х4 может быть квадрат с также «красивой» суммой 222:

97	41	73	11
17	47	83	75
59	79	13	71
49	55	53	65

9. Числа Фибоначчи

Возьмем 2 числа: 0 и 1. Следующее число рассчитаем как сумму предыдущих чисел, затем повторим процесс.

Мы получили последовательность, известную как числа Фибоначчи:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ...

Эта последовательность была названа в честь итальянского математика 12 века Леонардо Фибоначчи. Фибоначчи рассматривал задачу роста популяции кроликов. Если предположить, что новорожденная пара кроликов 1 месяц растет, через месяц начинает спариваться, и затем через каждый месяц дает потомство, то количество пар кроликов несложно подсчитать:

Как можно видеть, число пар образует как раз те самые числа Фибоначчи. Сама последовательность Фибоначчи кажется простой. Но чем она интересна? Пример с кроликами не случаен – эти числа действительно описывают множество природных закономерностей:

‐ Множество растений имеют количество лепестков, равное одному из чисел Фибоначчи. Количество листьев на стебле также может описываться этим законом, например у тысячелистника.

‐ Другое известное изображение – спираль Фибоначчи, которая строится по похожему принципу соотношения размеров прямоугольников:

Это изображение также часто встречается в природе, от раковин моллюсков, до формы атмосферного циклона или даже спиральной галактики.

Для примера достаточно взять фотографию циклона из космоса, и наложить обе картинки вместе:

‐ Если взять и разделить друг на друга 2 любых соседних члена последовательности, например 233/377, получится число 0,618. Случайно это или нет, но это число – то самое «золотое сечение», считающееся наиболее эстетичной пропорцией.

Числа Фибоначчи несложно вывести в программе на языке Python:

from decimal import *

def printNumbers(n):

    i1 = Decimal(0)

    i2 = Decimal(1)

    for p in range(1, n+1):

        print(«F({}) = {}».format(p, i2))

        fib = i1 + i2

        i1 = i2

        i2 = fib

getcontext().prec = 100

N = 100

printNumbers(N)

Интересно заметить, что растет последовательность Фибоначчи весьма быстро, уже

F(300) = 222232244629420445529739893461909967206666939096499764990979600.

10. Высота звуков нот

Еще в древности человек заметил, что натянутая струна порождает колебания звука. Во времена Пифагора было замечено, что струны издают мелодичный звук, если их длина соотносится как небольшие целые числа (1:2, 2:3, 3:4 и т. д.). Звук от струны длиной 2/3 дает чистую квинту, 3/4 струны дает кварту а половина струны – октаву.

Рассмотрим струну с условной длиной = 1. Будем умножать длину струны на 3/2, если полученное число больше 2, разделим еще на 2.

1.

3/2 = 1,5

1.5 * 3/2 = 2.25, 2.25/2 = 1,125 = 9/8

9/8 * 3/2 = 1,6875 = 27/16

Похожий ряд, если его упорядочить по возрастанию, называется пифагоровым строем:

«до» – 1

«ре» – 9/8

«ми» – 81/64

«фа» – 4/3

«соль» – 3/2

«ля» – 27/16

«си» – 243/128

«до» – 2

Он также называется квинтовым, т. к. ноты получались увеличением на квинту, т. е. на 3/2. Считается, что этот строй использовался еще при настройке лир в древней Греции, и сохранился вплоть до средних веков. Названия нот разумеется, были другие – современные названия придумал только через 1000 лет итальянский теоретик музыки Гвидо д’Ареццо в 1025 г.

Разумеется, в древней Греции никто не знал про частоту колебаний звука, зато древние греки были хорошими геометрами, и проблем с умножением и делением у них не было. Современная теория колебаний струны появилась гораздо позже, работы Эйлера и Д’Аламбера были написаны в 1750-х годах.

Как математически определяются частоты звуков нот? Сейчас мы знаем, что октава (от «до» до «до» следующей октавы) – это умножение частоты на 2 (или укорочение струны в 2 раза). Для остальных нот с 18 века используется так называемый «хорошо темперированный строй»: октава делится на 12 равных промежутков, а последовательность частот образует геометрическую прогрессию.

Для одной октавы получаются следующие коэффициенты: 1,0594, 1,1224, 1,1892, …, 2. На клавиатуре они отображаются всем известным образом, образуя 12 полутонов:

Таким образом, если знать частоту любой ноты, все остальные легко рассчитываются по вышеприведенной формуле.

Очевидно, что «базовая» частота может быть любой. Традиционно принято например, что частота камертона ноты «Ля» 440 Гц. Остальные ноты первой октавы:

ДО	261.6	ДО#	277
РЕ	293.7	РЕ#	311
МИ	329.6
ФА	349.2	ФА#	370
СОЛЬ	392	СОЛЬ#	415
ЛЯ	440	ЛЯ#	466
СИ	494

Интересно заметить, что квинта в этой системе имеет соотношение частот 2^7/12 = 1,49, что чуть-чуть отличается от «пифагорейского» чистого тона с соотношением 1.5. На слух «современная квинта» имеет небольшие биения 0,5 Гц, соответствующие разности частот 392—392,4. До сих пор есть любители исполнения старинной музыки в квинто-терцевом строе, называемым «чистым». В 18-м же веке дебаты между приверженцами «старого» и «нового» строя были довольно-таки острыми. Впрочем, преимущества равномерно темперированного строя в виде четкого соотношения между частотами нот и возможности транспонирования музыки в любую другую тональность «без потери качества» оказались решающими. Сейчас «чистый строй» имеет лишь историческое значение, и используется лишь иногда для исполнения старинных произведений.

И традиционно, программа на языке Python, выводящая частоты полутонов в обе стороны от ноты «Ля»:

import math

freqLa = 440

for p in range(-32, 32):

    freq = freqLa * math.pow(2, p / 12.0)

    print p,freq

11. Вращение планет

Еще в древней Греции ученые знали, что планеты движутся по небу, но каким образом? Сотни лет господствовала геоцентрическая система мира – в центре была Земля, вокруг которой по окружностям двигались Луна, планеты (на то время их было известно 5) и Солнце:

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

Вот так, к примеру, выглядит перемещение по небу планеты Марс, что никак не укладывается в теорию движения по кругу:

Впрочем геоцентрическая система просуществовала более 1500 лет, только в 16-м веке Коперник издал свой труд «О вращениях небесных сфер», где описывал вращение планет по круговым орбитам вокруг Солнца. Однако проблемой было то, что и при этой схеме фактические движения планет не совпадали с расчетными.

Объяснить это не мог никто, пока в 1600 году немецкий математик Иоганн Кеплер не стал изучать многолетние результаты наблюдений, сделанные астрономом Тихо Браге. Кеплер был великолепным математиком, но и у него ушло несколько лет чтобы понять суть и вывести законы, которые и сейчас называются законами Кеплера.

Как оказалось, движение планет подчиняется 3-м математическим законам:

1) Планеты движутся по эллиптическим орбитам, в одном из фокусов эллипса находится Солнце:

2) Планеты движутся неравномерно: скорость планеты увеличивается при движении к Солнцу и уменьшается в обратном направлении. Но за равные промежутки времени вектор движения описывает равные площади: площади участков «А» одинаковы:

3) Квадраты периодов обращений планеты пропорциональны кубу расстояний до орбиты:

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

Что касается Марса, то его орбита более вытянутая, чем орбита Земли, чем и объясняется разница как в скорости движения, так и в яркости планеты. Картинка с сайта журнала «Наука и жизнь»:

Кстати, эта картинка хорошо объясняет, почему только некоторые годы благоприятны для запуска космических кораблей к Марсу – те годы, в которые расстояние между планетами минимально.

12. Парадоксы теории вероятности

На интуитивном уровне понимание теории вероятности довольно-таки просто. Возьмем кубик с 6 гранями, подбросим и посмотрим какая грань выпала. Интуитивно ясно, что вероятность выпадения 1 грани из 6 будет 1/6. Действительно, вероятностью называют отношение числа равновероятных событий к числу всех возможных вариантов:

Какова вероятность что выпадут 2 цифры подряд? Она равна произведению вероятностей: (1/6) * (1/6) = 1/36.

Вроде все просто, однако несмотря на простоту, есть довольно-таки много задач, где математика не всегда совпадает с бытовым «здравым смыслом». Рассмотрим несколько таких парадоксов.

Дети мистера Смита

Эту задачу описывал Мартин Гарднер. Известно что у мистера Смита двое детей, и один из них мальчик. Какова вероятность, что второй из них тоже мальчик? Интуитивно кажется, что вероятность пола ребенка всегда равна 1/2, но не все так просто.

Рассмотрим возможные варианты семей с двумя детьми:

‐ мальчик-мальчик

‐ мальчик-девочка

‐ девочка-мальчик

‐ девочка-девочка

Исходя из списка вариантов, ответ понятен. Вариант «девочка-девочка» по условию не подходит. Всего остается 3 варианта семей где есть мальчик (М + М, М + Д, Д + М), значит вероятность что второй ребенок окажется мальчиком, равна 1/3.

Бросание кубика

Вернемся к бросанию кубика. Допустим, мы бросили кубик 5 раз, и все разы выпала цифра «3». Какова вероятность, что мы бросим кубик еще раз, и выпадет снова цифра «3»?

Ответ прост. Интуитивно кажется, что вероятность такого события очень мала. Но в реальности кубик не имеет какой-либо встроенной «памяти» на предыдущие события. Какие бы числа не выпадали до текущего момента, вероятность нового числа также равна 1/6 (а вот если говорить о вероятности выпадения такой серии «в целом», то она действительно равна 1/(6 * 6 * 6 * 6 * 6 * 6) = 1/46656.

Кстати, такая вероятность это много или мало? Интуитивно кажется что мало, и в принципе оно так и есть. Одному человеку пришлось бы бросать кубик каждые 10 секунд 4 дня, чтобы дождаться выпадения 6 цифр подряд. Однако если рассматривать большие числа, то такие вероятности становятся неожиданно большими. Например, если 6 раз кубик бросят все 5 миллионов жителей Петербурга, то 6 цифр подряд выпадут примерно у 100 человек – довольно-таки значительное количество. Это на самом деле важный момент: даже довольно-таки маловероятные события гарантированно произойдут, если речь идет о большом числе попыток. Это важно при прогнозировании таких событий как ДТП, аварии, катастрофы, и прочие негативные явления, которые в большом городе увы, не редкость. По этой же причине редкие заболевания эффективнее лечить в большом городе – редкая болезнь, встречающаяся 1 раз на 100000 человек, может практически не встречаться в небольшом городе и у врачей не будет опыта борьбы с ней, а в мегаполисе таких больных наберется в несколько раз больше.

Парадокс Монти Холла

Этот известный парадокс хорошо описан в Википедии.

Представьте, что вы стали участником игры, в которой вам нужно выбрать одну из трёх дверей. За одной из дверей находится автомобиль, за двумя другими дверями – козы. Вы выбираете одну из дверей, например, номер 1, после этого ведущий, который знает, где находится автомобиль, открывает одну из оставшихся дверей, за которой находится коза. После этого он спрашивает вас, не желаете ли вы изменить свой выбор. Увеличатся ли ваши шансы выиграть автомобиль, если вы примете предложение ведущего и измените свой выбор?

Интуитивно кажется, что если автомобиль спрятан за одной из дверей, то вероятность его найти равна 1/3, и смена двери ничего не даст. Однако это неверно.

Принцип прост: если игрок изначально правильно указал дверь с автомобилем (а вероятность этого действительно ⅓), то замена двери приведет его к проигрышу.

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

Парадокс дней рождений

Допустим, в организации работает 24 человека. Какова вероятность что хотя бы двое отмечают день рождения в один и тот же день? Интуитивно кажется, что эта вероятность весьма мала и будет равна 24/365, но и в этом случае интуиция ошибается. В реальности, мы должны рассматривать количество пар, которые могут образовать данные люди. Это число довольно-таки велико, например, если обозначить 5 человек как ABCDE, то количество возможных пар будет 10 (AB, AC, AD, AE, BC, BD, BE, CD, CE, DE), а для группы из 24 человек возможно 276 пар.

Для точного расчета воспользуемся принципом произведения вероятностей. Вероятность того, что для 2х людей день рождения не совпадет, равна 364/365. Для 3х человек вероятность что все дни не совпадут, равна произведению 364/365 * 363/365, и так далее. Для n-человек формула приведена в Википедии:

(n! – обозначение факториала, n! = 1 * 2* .. * (n – 1) * n)

Нужная нам вероятность обратного события равна обратной величине:

Вывести все значения несложно с помощью программы на Python:

import math

def C(n):

    return 1000 – 1000 * math.factorial(365) / (math.factorial(365 – n) * 365**n)

for n in range(3, 50):

    print(«{} – {}%»).format(n, 0.1 * C(n))

365! это очень большое число, поэтому здесь использованы целочисленные вычисления языка Python, уже затем значение было переведено в проценты.

В результате получаем следующую таблицу:

3	0.0082	4	0.0163	5	0.0271
6	0.0404	7	0.0562	8	0.0743
9	0.0946	10	0.1169	11	0.1411
12	0.1670	13	0.1944	14	0.2231
15	0.2529	16	0.2836	17	0.3150
18	0.3469	19	0.3791	20	0.4114
21	0.4436	22	0.4756	23	0.5072
24	0.5383	25	0.5686	26	0.5982
27	0.6268	28	0.6544	29	0.6809
30	0.7063	31	0.7304	32	0.7533
33	0.7749	34	0.7953	35	0.8143
36	0.8321	37	0.8487	38	0.8640
39	0.8782	40	0.8912	41	0.9031
42	0.9140	43	0.9239	44	0.9328
45	0.9409	46	0.9482	47	0.9547
48	0.9605	49	0.9657	50	0.9703

Как видно из таблицы, уже при количестве сотрудников 50 человек, хотя бы 1 день рождения почти гарантированно совпадет (вероятность 97%), а для 24 человек получаем вероятность равную 0.538, т. е. более 50%.

13. Поверхность Луны

Посмотрим на фотографию поверхности Луны. Эта фотография была сделана в телескоп с балкона:

Что мы видим? Очевидно, лунную поверхность, покрытую кратерами, оставшимися от предыдущих столкновений метеоритов с Луной.

Казалось бы, причем здесь математика? При том, что столкновение с метеоритом – случайное событие, его частота подчиняется теории вероятности. На Луне нет атмосферы, нет эрозии и ветра, поэтому лунная поверхность – идеальная «книга», в которой записаны события последних десятков тысяч лет. Изучая поверхность Луны, можно подсчитать какого размера объекты падали на ее поверхность.

Исследование поверхности Луны камерами высокого разрешения ведется и сейчас. Было подсчитано, что за последние 7 лет на Луне образовались не менее 220 новых кратеров. Это важно еще и потому, что данные подсчеты помогут оценить опасность для Земли.

Есть ли кратеры на Земле? Разумеется есть. Данная фотография сделана вовсе не на Луне или на Марсе, а в США:

Так называемый Аризонский кратер возник около 50 тыс. лет назад после падения метеорита диаметром 50 метром и весом 300 тысяч тонн. Диаметр кратера составляет более километра. В Сибири находится кратер Попигай размером 100 км, он был открыт в 1946 году.

Разумеется, такие большие кратеры довольно-таки редки. Последнее же падение крупного метеорита было по историческим меркам весьма недавно, всего лишь около 100 лет назад. В 1908 г. в тунгусской тайге упал метеорит, мощность взрыва оценивалась от 10 до 50 мегатонн. По отзывам, взрывная волна обогнула земной шар, а световые явления в атмосфере были столь сильны, что в Лондоне ночью можно было читать газету. Лишь по случайности падение метеорита пришлось на малонаселенные районы Сибири – если бы удар был чуть раньше или позже, такой мощности хватило бы, чтобы полностью уничтожить город размером с Санкт-Петербург. Совсем же недавно, в 2013 году, метеорит размером около 20 метров разрушился в атмосфере, а его многочисленные обломки упали в районе Челябинска. Пострадало примерно 1500 человек, в основном от выбитых ударной волной стекол. По оценкам NASA суммарная мощность составила до 400 килотонн.

Увы, то, что для определенного района Земли может быть катастрофой, для космоса совершенно заурядный момент. Это лишь вопрос времени, достаточно посмотреть на поверхность Луны. По одной из гипотез, 66 миллионов лет назад наша планета столкнулась с большим астероидом, в результате чего было уничтожено 75% видов живых существ, в том числе и динозавры. Поэтому задача наблюдения и прогнозирования астероидной опасности должна быть в обязательном списке дел для человечества, если мы не хотим повторить их судьбу.

14. Так ли случайны случайные числа?

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

На языке Python вывести случайное число можно так:

import random

print(random.randint(0, 9))

Но как это работает? Задача вывода действительно случайного числа далеко не так проста как кажется. Чтобы вывести что-то на компьютере, это что-то надо сначала запрограммировать. Но очевидно, что задать формулой случайный, хаотический процесс, невозможно – по определению формула и хаос противоречат друг другу. Именно поэтому числа на самом деле являются псевдослучайными – они лишь похожи на случайные, а в реальности являются результатом вполне конкретного алгоритма.

Одним из наиболее популярных и простых алгоритмов, является линейный конгруэнтный метод (linear congruential generator). Его формула проста:

Рассмотрим пример реализации на языке Python:

x = 123456789

m = 2**31 – 1

for p in range(10):

    x = (1103515245 * x + 12345) % m

    print(x)

Программа действительно выводит числа, которые вполне похожи на случайные: 295234770, 465300796, 1475666158, 588454008, 929838277, 50298429, 1089988954, 698778454, 2010473888, 36125306. Как нетрудно догадаться, при повторном запуске программы числа будут одни и те же. Чтобы числа не повторялись, такой генератор обычно инициализируют значением текущего системного времени.

Увы, такой генератор имеет определенные недостатки: во-первых, его последовательность рано или поздно начинает повторяться, во-вторых, он не является криптостойким – зная текущее значение, можно вычислить следующее, что к примеру, может позволить злоумышленнику узнать «случайно» сгенерированный пароль по его первым буквам.

Существуют другие алгоритмы генерации псевдослучайных чисел, например на основе простых чисел Мерсенна (Mersenne Twister generator). Существуют также аппаратные генераторы случайных чисел, например такая функция присутствует в процессорах Intel. Есть даже сайт https://www.random.org, с помощью которого можно сгенерировать случайную последовательность чисел. По заверениям авторов, они используют 3 радиоприемника, настроенных на частоту шума атмосферных помех.

Разумеется, в большинстве обычных программ, например при написании компьютерной игры, «качеством» случайных чисел можно пренебречь, встроенные алгоритмы вполне неплохи. Но при разработке специализированного ПО, где вопрос криптостойкости имеет значение, стоит уже обратить внимание на то, насколько надежен применяемый алгоритм.