--PAGE_BREAK--
Если же число № составное, то его по определению, можно представить в виде произведения хотя бы двух сомножителей: n=n1n2, где n1 ≠ 1 и n2 ≠ 1.
Но тогда n1>n и n2
6. Простейшей реализацией идеи индукции в применении к числам Фибоначчи является само определение чисел Фибоначчи. Оно состоит в указании двух первых чисел Фибоначчи: U1=1 и U2=1 и в индуктивном переходе от Un и Un+1 к Un+2, даваемым рекуррентным соотношением: Un+Un+1=Un+2.В частности, отсюда автоматически следует, что если некоторая последовательность чисел начинается с двух единиц, а каждое из следующих получается сложением двух предыдущих, то эта последовательность является последовательностью чисел Фибоначчи.
В качестве примера рассмотрим так называемую «задачу о прыгуне». Она состоит в следующем.
"Задача о прыгуне". Прыгун может прыгать в одном направлении вдоль разделенной на клетки полосы, перемещаясь при каждом прыжке либо в соседнюю клетку, либо через клетку. Сколькими способами может он сдвинуться на n-1 клетку и, в частности, переместиться из первой клетки в n-ю? (Способы прыганья считаются одинаковыми, если в ходе каждого из них прыгун побывает в одних и тех же клетках). Обозначим искомое число через хn. Очевидно х1=1(ибо переход из первой клетки в первую же осуществляется только одним способом-отсутствием прыжков) и х2=1 (переход из первой клетки во вторую также единствен: он состоит в одном непосредственном прыжке на соседнюю клетку). Пусть целью прыгуна является достижение n+2-й клетки. Общее число способов осуществление этой цели в наших обозначениях равно хn+2.Но с самого начала эти способы разбиваются на два класса: начинающиеся с прыжка во вторую клетку и начинающиеся с прыжка в третью клетку. Из второй клетки прыгун может переместиться в n+2-ю хn+1 способами, а из третьей хn способами.
Таким образом, последовательность чисел х1, х2,…, хn,…удовлетворяет рекуррентному соотношению:
xn+хn+1=хn+2 и поэтому совпадает с последовательностью чисел Фибоначчи хn=Un.
7. Докажем по индукции следующую важную формулу:
Un+m=Un-1Um+UnUm+1.(31)
Доказательство этой формулы будем вести индукцией по m.
При m=1 эта формула принимает вид:
Un+1=Un-1U1+UnU2, что очевидно.
При m=2 формула (31) также верна, потому что
Un+2=Un-1U2+UnU3=Un-1+2Un=Un-1+Un +Un=Un+1+Un.
Основание индукции, таким образом, доказано.
8.Полагая в формуле (31) m = n, мы получаем
U2n=Un-1Un+UnUn+1,
или
U2n=Un(Un-1+Un+1) (32)
Из написанного равенства видно, что U2n делится на Un.
Так как Un=Un+1-Un-1, формулу (32) можно переписать так:
U2n=(Un+1-Un-1)=(Un+1+Un-1), или
U2n= U2n+1-U 2n-1, т. е. разность квадратов двух чисел Фибоначчи, номера которых отличаются на два, есть снова число Фибоначчи (и причем с четным номером).
Аналогично(полагая m=2n) можно показать, что
U3n=U3n+1+U3n-U3n-1.
9.В дальнейшем нам пригодиться следующая формула:
U2n =Un-1Un+1+(-1)n+1 (33)
Докажем ее индукцией по n.
Для n=2, формула (33) принимает вид:
U22=U1U3-1,
что очевидно.
Предположим теперь в формулу (33) доказанной для некоторого n, прибавим к обеим частям ее по UnUn+1. Получим
U2n+UnUn+1= Un-1Un+1+ UnUn+1+(-1)n+1,
Или
Un (Un+Un+1)= Un+1(Un-1+Un)+(-1)n+1,
Или
Un Un+2= U2n+1+(-1)n+1,
Или
U2n+1= Un Un+2+(-1)n+2,
Этим индуктивный переход обоснован и формула (33) доказана для любого n.
10. Аналогичным способом можно установить такие свойства чисел Фибоначчи:
U1U2+U2U3+U3U4+…+U2n-1U2n=U22n.
U1U2+U2U3+U3U4+…+U2nU2n+1=U22n+1-1.
nU1+(n-1)U2+(n-2)U3+…+2Un-1+Un=Un+4-(n+3)
U1+2U2+3U3+…+nUm=nUn+2-Un+3+2
11. До сих пор мы определяли числа Фибоначчи рекуррентно, т. е. индуктивно, по их номеру. Оказывается, что любое число Фибоначчи можно определить и непосредственно, как некоторую функцию его номера.
Исследуем для этого различные последовательности U1, U2, U3,…., Un,…, удовлетворяющие соотношению
Un=Un-2+Un-1 (34)
Все такие последовательности мы будем называть решениями уравнения (34)
Будем обозначать буквами V,V`, V`` соответственно последовательности:
w1,w2,w3,…
w1`,w2`,w3`,…
w1``,w2``,w3``,…
Сначала докажем две леммы.
ЛЕММА 1.
Если V – есть решение уравнения (34), а c – произвольное число, то последовательность cV (т. е. последовательность cw1,cw2,cw3,…) есть так же решение уравнения (11)
ДОКАЗАТЕЛЬСТВО: Умножив соотношение wn=wn-2+wn-1 почленно на c, получаем cwn=cwn-2+cwn-1, а это и требовалось доказать.
ЛЕММА 2.
Если последовательности V`и V`` являются решениями уравнения (34), то и их сумма V`+ V`` (т. е. последовательность w`1+w``1, w2`+w2``, w3` +w3``) является решением уравнения (11)
ДОКАЗАТЕЛЬСТВО: Из условия леммы мы имеем:
w`n=w`n-2+w`n-1
и
w``n=w``n-2+w``n-1
Сложив эти два равенства почленно, получим:
w`n +w``n= (w`n-2+w``n-2)+(w`n-1+w``n-1).
Этим лемма доказана.
Из этих лемм также выводится знаменитая формула Бине:
/>
Рассмотрим теперь некоторые свойства чисел Фибоначчи, касающиеся их делимости. Докажем следующую теорему.
ТЕОРЕМА. Если № делиться на m, то и Un делиться на Um.
ДОКАЗАТЕЛЬСТВО:
Пусть № делиться на m, т. е. № = mk. Будем вести доказательство индукцией по k.
Для k=1, № = m, так что в этом случае Un делиться на Um очевидным образом. Предположим теперь что Umk делиться на Um и рассмотрим Um(k+1). Тогда имеем: Um(k+1) = Umk+m и на основании формулы (31) получим:
Um(k+1) = Umk+m= Umk-1Um+ UmkUm+1
Первое слагаемое правой части написанного равенства, очевидно, делиться на Um. Второе же его слагаемое кратно Umk т. е. по индуктивному предположению тоже делиться на Um. Значит, на Um делиться и их сумма, т. е. Um(k+1). Теорема доказана.
Большой интерес представляет вопрос об арифметической природе чисел Фибоначчи, об их делителях.
Докажем, что при № составном и отличном от 4 Un есть составное число. Действительно, для такого № можно написать n=n1n2, где 1
12, либо n2>2. Пусть для определенности n1>2. Тогда ввиду только что доказанный теоремы Un делиться на Un1 причем 1
Существует огромное количество различных обобщений чисел Фибоначчи. Одним из наиболее интересных является гипотенузный ряд Шишкова.
Существует связь между теоремой Пифагора и числами Фибоначчи.
С2+B2=A2 – теорема Пифагора.
Поместим для наглядности рядом числа Фибоначчи:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4161 6765...
Полагая, что числа Фибоначчи непосредственно связаны с прямоугольными треугольниками, берем попарно суммы, состоящие из квадратов чисел Фибоначчи, и находим в этом же ряду соответствующее число, равное квадрату гипотенузы, или сумме двух возведенных в квадрат чисел Фибоначчи. Эти числа, равные квадрату гипотенузы, сумме двух возведенных в квадрат катетов, подчеркнуты в ряду Фибоначчи чертой. Эти подчеркнутые числа Ф являются и квадратом гипотенузы ранее расположенных катетов, и, одновременно, катетами, квадрат гипотенузы которых расположен дальше в ряду Фибоначчи.
Примеры: 12+12 =2; 12 +22=5; 22 +32=13 и т. д.
Таким образом числа Фибоначчи характеризуют не только золотое сечение, но и прямоугольные треугольники.
3. Золотое сечение
Иоганн Кеплер говорил, что геометрия владеет двумя сокровищами – теоремой Пифагора и золотым сечением. И если первое из этих двух сокровищ можно сравнить с мерой золота, то второе с драгоценным камнем.
Теорему Пифагора знает каждый школьник, а что такое золотое сечение – далеко не все. Так что же такое золотое сечение, и какая существует связь между ним и числами Фибоначчи?
Как уже упоминалось в разделе 2, число (1 + />)/2 ≈ 1.61803 играет важную роль во многих разделах математики, равно как и в мире искусств, где с античных времен оно рассматривалось как эстетически самое благоприятное отношение. Поэтому оно имеет специальное название – отношение золотого сечения и обозначается греческой буквой Ф в честь Фидия, который, как утверждается, сознательно использовал его в своих скульптурах. Связь этого числа с числами Фибоначчи устанавливается посредством Формулы Бине (или точнее, формулы Бернулли-Бине):
F(z) = (/>– />) / />.
Однако, есть и другой – геометрический – подход к определению золотого сечения. Через золотое сечение числа Фибоначчи проявляют свои свойства в самых различных сферах. Многие наблюдаемые закономерности в этой области до сих пор не объяснены наукой. Но знать о них должен каждый исследователь.
Человек различает окружающие его предметы по форме. Интерес к форме какого-либо предмета может быть продиктован жизненной необходимостью, а может быть вызван красотой формы. Форма, в основе построения которой лежат сочетание симметрии и золотого сечения, способствует наилучшему зрительному восприятию и появлению ощущения красоты и гармонии. Целое всегда состоит из частей, части разной величины находятся в определенном отношении друг к другу и к целому. Принцип золотого сечения – высшее проявление структурного и функционального совершенства целого и его частей в искусстве, науке, технике и природе.
Золотое сечение – гармоническая пропорция. В математике пропорцией называют равенство двух отношений: a: b = c: d.
Отрезок АВ можно разделить точкой C на две части следующими способами:
1) на две равные части АВ: АC = АВ: ВC;
2) на две неравные части в любом отношении (такие части пропорции не образуют);
3) таким образом, когда АВ: АC = АC: ВC.
Последнее и есть золотое сечение или деление отрезка в крайнем и среднем отношении.
продолжение
--PAGE_BREAK--Золотое сечение – это такое пропорциональное деление отрезка на неравные части, при котором весь отрезок так относится к большей части, как сама большая часть относится к меньшей; или другими словами, меньший отрезок так относится к большему, как больший ко всему.
a
: b = b: c или с: b = b: а.
/>
Pис. 2. Геометрическое изображение золотой пропорции
Если c принять за единицу, то отрезки золотой пропорции выражаются бесконечными иррациональными дробями b = 0,618..., a = 0,382… Как мы уже знаем, числа 0.618 и 0.382 являются коэффициентами последовательности Фибоначчи. На этой пропорции базируются основные геометрические фигуры.
Прямоугольник с таким отношением сторон стали называть золотым прямоугольником. Он также обладает интересными свойствами. Если от него отрезать квадрат, то останется вновь золотой прямоугольник. Этот процесс можно продолжать до бесконечности. А если провести диагональ первого и второго прямоугольника, то точка их пересечения будет принадлежать всем получаемым золотым прямоугольникам.
Разумеется, есть и золотой треугольник. Это равнобедренный треугольник, у которого отношение длины боковой стороны к длине основания равняется 1.618.
/>
Pис. 3. Золотой треугольник
Есть и золотой кубоид – это прямоугольный параллелепипед с ребрами, имеющими длины 1.618, 1 и 0.618.
В звездчатом пятиугольнике каждая из пяти линий, составляющих эту фигуру, делит другую в отношении золотого сечения, а концы звезды являются золотыми треугольниками.
/>
Pис. 4. Построение правильного пятиугольника и пентаграммы
Принято считать, что понятие о золотом делении ввел в научный обиход Пифагор, древнегреческий философ и математик (VI в. до н. э.). Есть предположение, что Пифагор свое знание золотого деления позаимствовал у египтян и вавилонян. И действительно, пропорции пирамиды Хеопса, храмов, барельефов, предметов быта и украшений из гробницы Тутанхамона свидетельствуют, что египетские мастера пользовались соотношениями золотого деления при их создании.
Французский архитектор Ле Корбюзье нашел, что в рельефе из храма фараона Cети I в Абидосе и в рельефе, изображающем фараона Pамзеса, пропорции фигур соответствуют величинам золотого деления. Зодчий Хесира, изображенный на рельефе деревянной доски из гробницы его имени, держит в руках измерительные инструменты, в которых зафиксированы пропорции золотого деления.
Греки были искусными геометрами. Даже арифметике обучали своих детей при помощи геометрических фигур. Kвадрат Пифагора и диагональ этого квадрата были основанием для построения динамических прямоугольников.
/>
Pис. 5. Динамические прямоугольники
Платон (427-347 гг. до н. э.) также знал о золотом делении. Его диалог «Тимей» посвящен математическим и эстетическим воззрениям школы Пифагора и, в частности, вопросам золотого деления.
В фасаде древнегреческого храма Парфенона присутствуют золотые пропорции. При его раскопках обнаружены циркули, которыми пользовались архитекторы и скульпторы античного мира. В Помпейском циркуле (музей в Неаполе) также заложены пропорции золотого деления.
/>
Pис. 6. Античный циркуль золотого сечения
В дошедшей до нас античной литературе золотое деление впервые упоминается в «Началах» Евклида. Во 2-й книге «Начал» дается геометрическое построение золотого деления. После Евклида исследованием золотого деления занимались Гипсикл (II в. до н. э.), Папп (III в. н. э.) и др. В средневековой Европе с золотым делением познакомились по арабским переводам «Начал» Евклида. Переводчик Дж. Kампано из Наварры (III в.) сделал к переводу комментарии. Секреты золотого деления ревностно оберегались, хранились в строгой тайне, они были известны только посвященным.
В эпоху Возрождения усиливается интерес к золотому делению среди ученых и художников в связи с его применением, как в геометрии, так и в искусстве, особенно в архитектуре. Леонардо да Винчи, художник и ученый, видел, что у итальянских художников эмпирический опыт большой, а знаний мало. Он задумал и начал писать книгу по геометрии, но в это время появилась книга монаха Луки Пачоли, и Леонардо оставил свою затею. По мнению современников и историков науки, Лука Пачоли был настоящим светилом, величайшим математиком Италии в период между Фибоначчи и Галилеем. Лука Пачоли был учеником художника Пьеро Дела Франчески, написавшего две книги, одна из которых называлась «О перспективе в живописи». Его считают творцом начертательной геометрии.
Лука Пачоли прекрасно понимал значение науки для искусства. В 1496 г по приглашению герцога Моро он приезжает в Милан, где читает лекции по математике. В Милане при дворе Моро в то время работал и Леонардо да Винчи. В 1509 г. в Венеции была издана книга Луки Пачоли «Божественная пропорция» с блестяще выполненными иллюстрациями, ввиду чего полагают, что их сделал Леонардо да Винчи. Книга была восторженным гимном золотой пропорции. Среди многих достоинств золотой пропорции монах Лука Пачоли не преминул назвать и ее «божественную суть» как выражение божественного триединства бог сын, бог отец и бог дух святой (подразумевалось, что малый отрезок есть олицетворение бога сына, больший отрезок – бога отца, а весь отрезок – бога духа святого).
Леонардо да Винчи также много внимания уделял изучению золотого деления. Он производил сечения стереометрического тела, образованного правильными пятиугольниками, и каждый раз получал прямоугольники с отношениями сторон в золотом делении. Поэтому он дал этому делению название золотое сечение. Так оно и держится до сих пор как самое популярное.
В то же время на севере Европы, в Германии, над теми же проблемами трудился Аль Брехт Дюрер. Он делает наброски введения к первому варианту трактата о пропорциях. Дюрер пишет. «Необходимо, чтобы тот, кто что-либо умеет, обучил этому других, которые в этом нуждаются. Это я и вознамерился сделать».
продолжение
--PAGE_BREAK--Судя по одному из писем Дюрера, он встречался с Лукой Пачоли во время пребывания в Италии. Аль Брехт Дюрер подробно разрабатывает теорию пропорций человеческого тела. Важное место в своей системе соотношений Дюрер отводил золотому сечению. Рост человека делится в золотых пропорциях линией пояса, а также линией, проведенной через кончики средних пальцев опущенных рук, нижняя часть лица – ртом и т. д. Известен пропорциональный циркуль Дюрера.
Великий астроном XVI в. Коган Кеплер назвал золотое сечение одним из сокровищ геометрии. Он первый обращает внимание на значение золотой пропорции для ботаники (рост растений и их строение).
В последующие века правило золотой пропорции превратилось в академический канон и, когда со временем в искусстве началась борьба с академической рутиной, в пылу борьбы «вместе с водой выплеснули и ребенка». Вновь «открыто» золотое сечение было в середине XIX в. В 1855 г. немецкий исследователь золотого сечения профессор Цейзинг опубликовал свой труд «Эстетические исследования». Он абсолютизировал пропорцию золотого сечения, объявив ее универсальной для всех явлений природы и искусства.
Цейзинг проделал колоссальную работу. Он измерил около двух тысяч человеческих тел и пришел к выводу, что золотое сечение выражает средний статистический закон. Деление тела точкой пупа – важнейший показатель золотого сечения. Пропорции мужского тела колеблются в пределах среднего отношения 13: 8 = 1,625 и несколько ближе подходят к золотому сечению, чем пропорции женского тела, в отношении которого среднее значение пропорции выражается в соотношении 8: 5 = 1,6. У новорожденного пропорция составляет отношение 1: 1, к 13 годам она равна 1,6, а к 21 году равняется мужской. Пропорции золотого сечения проявляются и в отношении других частей тела – длина плеча, предплечья и кисти, кисти и пальцев и т. д.
Справедливость своей теории Цейзинг проверял на греческих статуях. Наиболее подробно он разработал пропорции Аполлона Бельведерского. Подверглись исследованию греческие вазы, архитектурные сооружения различных эпох, растения, животные, птичьи яйца, музыкальные тона, стихотворные размеры. Цейзинг дал определение золотому сечению, показал, как оно выражается в отрезках прямой и в цифрах. Когда цифры, выражающие длины отрезков, были получены, Цейзинг увидел, что они составляют ряд Фибоначчи, который можно продолжать до бесконечности в одну и в другую сторону. Следующая его книга имела название «Золотое деление как основной морфологический закон в природе и искусстве». В 1876 г. в России была издана небольшая книжка, почти брошюра, с изложением этого труда Цейзинга.
В конце XIX – начале XX вв. появилось немало чисто формалистических теории о применении золотого сечения в произведениях искусства и архитектуры. С развитием дизайна и технической эстетики применение закона золотого сечения распространилось на конструирование машин, мебели и пр.
Пропорция, выражаемая числом Ф, по мнению многих исследований, является наиболее приятной для человеческого глаза.
Леонардо де Винчи считал, что идеальные пропорции человеческого тела должны быть связаны с числом Ф. Деление отрезка в отношении Ф он назвал «золотым сечением». В эпоху возрождения «золотое сечение» было очень популярно среди художников, скульпторов и архитекторов. Размеры картины было принято брать такими, чтобы отношение ширины к высоте равнялось Ф. Этот термин сохранился до наших дней, и само «золотое сечение» по прежнему играет важную роль в искусстве. Им руководствовался, например, великий архитектор Ле Корбюзье.
Прямоугольник с таким отношением сторон стали называть «золотым прямоугольником».
Форму «золотого сечения» придавали книгам, столам почтовым открыткам. В дальнейшем книгам и другим бумажным изделиям стали чаще придавать форму прямоугольника с отношением сторон корень из двух. Это связано с тем, что при перегибании такого прямоугольника по средней линии образуются два прямоугольника с тем же соотношением сторон.
Число золотого сечения Ф обладает какой-то странной неуловимостью. Оно появляется в различных проекциях, так и не давая ответа на вопрос, как это число связано с тем или иным явлением. Интерес к мистическому числу Ф достаточно периодичен. Он возникает с обнаружением нового проявления этого числа в каком-либо явлении природы.
Проходит время, и интерес к нему спадает. Но ненадолго. Числу Ф находят всё новое и новое применение, но оно так и остается недоступным для ясного и полного понимания его свойств и степени его влияния на окружающий мир.
3.1. Проявление золотого сечения в природе
Просто удивительно, сколько постоянных можно вычислить при помощи последовательности Фибоначчи, и как ее члены проявляются в огромном количестве сочетаний.
Однако не будет преувеличением сказать, что это не просто игра с числами, а самое важное математическое выражение природных явлений из всех когда-либо открытых. Приводимые ниже примеры показывают некоторые интересные приложения этой математической последовательности.
Раковина
Раковина закручена по спирали. Если ее развернуть, то получается длина, немного уступающая длине змеи. Небольшая десятисантиметровая раковина имеет спираль длиной 35 см. Спирали очень распространены в природе. Форма спирально завитой раковины привлекла внимание Архимеда. Он изучал ее и вывел уравнение спирали. Спираль, вычерченная по этому уравнению, называется его именем. Увеличение ее шага всегда равномерно. В настоящее время спираль Архимеда широко применяется в технике. ОБ: ОА=ОВ: ОБ=ОГ: ОВ=… =1.618 (ОБ+ОГ):(ОВ+ОА)=… =1.618
/>
Pис. 7. Спираль Архимеда
Растения и животные
продолжение
--PAGE_BREAK--Еще Гете подчеркивал тенденцию природы к спиральности. Винтообразное и спиралевидное расположение листьев на ветках деревьев подметили давно. Спираль увидели в расположении семян подсолнечника, в шишках сосны, ананасах, кактусах и т. д. Совместная работа ботаников и математиков пролила свет на эти удивительные явления природы. Выяснилось, что в расположении листьев на ветке семян подсолнечника, шишек сосны проявляет себя ряд Фибоначчи, а стало быть, проявляет себя закон золотого сечения. Паук плетет паутину спиралеобразно. Спиралью закручивается ураган. Испуганное стадо северных оленей разбегается по спирали. Молекула ДНK закручена двойной спиралью. Гете называл спираль «кривой жизни».
Среди придорожных трав растет ничем не примечательное растение – цикорий. Приглядимся к нему внимательно. От основного стебля образовался отросток. Тут же расположился первый листок.
/>
Pис. 8. Цикорий
Отросток делает сильный выброс в пространство, останавливается, выпускает листок, но уже короче первого, снова делает выброс в пространство, но уже меньшей силы, выпускает листок еще меньшего размера и снова выброс. Если первый выброс принять за 100 единиц, то второй равен 62 единицам, третий – 38, четвертый – 24 и т. д. Длина лепестков тоже подчинена золотой пропорции. В росте, завоевании пространства растение сохраняло определенные пропорции. Импульсы его роста постепенно уменьшались в пропорции золотого сечения. В ящерице с первого взгляда улавливаются приятные для нашего глаза пропорции – длина ее хвоста так относится к длине остального тела, как 62 к 38.
/>
Pис. 9. Ящерица живородящая
И в растительном, и в животном мире настойчиво пробивается формообразующая тенденция природы – симметрия относительно направления роста и движения. Здесь золотое сечение проявляется в пропорциях частей перпендикулярно к направлению роста.
Природа осуществила деление на симметричные части и золотые пропорции. В частях проявляется повторение строения целого.
/>
Pис. 10. Яйцо птицы
Великий Гёте, поэт, естествоиспытатель и художник (он рисовал и писал акварелью), мечтал о создании единого учения о форме, образовании и преобразовании органических тел. Это он ввел в научный обиход термин морфология.
Пьер Кюри в начале нашего столетия сформулировал ряд глубоких идей симметрии. Он утверждал, что нельзя рассматривать симметрию какого-либо тела, не учитывая симметрию окружающей среды.
Закономерности золотой симметрии проявляются в энергетических переходах элементарных частиц, в строении некоторых химических соединений, в планетарных и космических системах, в генных структурах живых организмов.
Эти закономерности, как указано выше, есть в строении отдельных органов человека и тела в целом, а также проявляются в биоритмах и функционировании головного мозга и зрительного восприятия.
Последовательность чисел Фибоначчи обладает удивительной связью с живой природой. В частности, она лежит в основе ботанического явления филлотаксиса, законы которого определяют внешние формы сосновой шишки, кактуса, ананаса, пальмового дерева и т. д.
Семена в головке подсолнуха расположены на пересечении левосторонних и правосторонних спиралей, число которых выражается с помощью соседних чисел Фибоначчи. Но самым выдающимся открытием современной науки, несомненно, стало обнаружение чисел Фибоначчи и золотого сечения в структуре генетического кода.
Космос
Из истории астрономии известно, что И. Тициус, немецкий астроном XVIII в., с помощью этого ряда нашел закономерность и порядок в расстояниях между планетами солнечной системы.
Однако один случай, который, казалось бы, противоречил закону: между Марсом и Юпитером не было планеты. Сосредоточенное наблюдение за этим участком неба привело к открытию пояса астероидов. Произошло это после смерти Тициуса в начале XIX в. Ряд Фибоначчи используют широко: с его помощью представляют архитектонику и живых существ, и рукотворных сооружений, и строение Галактик. Эти факты – свидетельства независимости числового ряда от условий его проявления, что является одним из признаков его универсальности.
Пирамиды
Многие пытались разгадать секреты пирамиды в Гизе. В отличие от других египетских пирамид это не гробница, а скорее неразрешимая головоломка из числовых комбинаций. Замечательные изобретательность, мастерство, время и труд архитекторов пирамиды, использованные ими при возведении вечного символа, указывают на чрезвычайную важность послания, которое они хотели передать будущим поколениям. Их эпоха была дописьменной, доиероглифической и символы были единственным средством записи открытий.
Ключ к геометро-математическому секрету пирамиды в Гизе, так долго бывшему для человечества загадкой, в действительности был передан Геродоту храмовыми жрецами, сообщившими ему, что пирамида построена так, чтобы площадь каждой из ее граней была равна квадрату ее высоты.
Площадь треугольника
356 x 440 / 2 = 78320
Площадь квадрата
280 x 280 = 78400
Длина грани пирамиды в Гизе равна 783.3 фута (238.7 м), высота пирамиды – 484.4 фута (147.6 м). Длина грани, деленная на высоту, приводит к соотношению Ф=1.618.Высота 484.4 фута соответствует 5813 дюймам (5-8-13) – это числа из последовательности Фибоначчи.
Эти интересные наблюдения подсказывают, что конструкция пирамиды основана на пропорции Ф=1,618. Современные ученые склоняются к интерпретации, что древние египтяне построили ее с единственной целью – передать знания, которые они хотели сохранить для грядущих поколений.
Интенсивные исследования пирамиды в Гизе показали, сколь обширными были в те времена познания в математике и астрологии. Во всех внутренних и внешних пропорциях пирамиды число 1.618 играет центральную роль.
Пирамиды в Мексике. Не только египетские пирамиды построены в соответствии с совершенными пропорциями золотого сечения, то же самое явление обнаружено и у мексиканских пирамид. Возникает мысль, что как египетские, так и мексиканские пирамиды были возведены приблизительно в одно время людьми общего происхождения.
На поперечном сечении пирамиды видна форма, подобная лестнице. В первом ярусе 16 ступеней, во втором 42 ступени и в третьем – 68 ступеней.
Эти числа основаны на соотношении Фибоначчи следующим образом:
16 x 1.618 = 26
16 + 26 = 42
26 x 1.618 = 42
42 + 26 = 68
Интересно, что и на Марсе в районе Сидония обнаружены аномальные объекты, имеющие пирамидальную форму, а один из объектов напоминает человеческое лицо. Взаимное расположение этих объектов также связано с золотой пропорцией. Случайное ли это совпадение, или же «пирамиды» на Марсе служат неким знаком погибшей цивилизации? Данный вопрос еще ждет своего окончательного разрешения.
3.2. Последовательность Фибоначчи и хронология
В качестве инструмента хронологии усилиями некоторых ученых в конце XX века впервые была избрана гармоническая система числовых отношений, и, в частности, – ряд Фибоначчи.
Приметы такого ряда очевидны в хронологии эпох I тыс. н. э. – I тыс. до н. э. Числа ряда удачно фиксируют поздний железный век (I тыс. н. э.) и начало железного века (I тыс. до н. э.).
В интервале 5-2 тыс. до н. э. сосредоточены культуры энеолита, ранней и поздней бронзы Европы, к интервалу 8-5 тыс. до н. э. относят европейский мезолит и неолитические культуры Ближнего Востока. Правда, мезолит Ближнего Востока датируют иначе: 10-7 тыс. до н. э., а мезолит Восточной Европы – 11-6 тыс. до н. э.
Особенности в хронологии культур 10-5 тыс. до н. э. региональны. Они зависят, от неравномерности развития, которая возникла в верхнем палеолите и сохранялась на протяжении всего времени в дальнейшем.
Замеченные расхождения в хронологии археологических эпох имеют региональный масштаб, никак не затрагивают самой числовой последовательности, присущей ряду Фибоначчи: 1, 1, 2, 3, 5, 8. Очевидно, что в хронологии археологических культур более раннего времени, развитию которых присущ планетарный характер, следует ожидать более строгого соответствия ряду Фибоначчи.
Продолжим ряд, его составляют такие числа: 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1 597, 2 584, 4181 и т. д.
Сначала казалось удивительным: некоторые элементы этой последовательности, действительно, соответствуют хронологическим рубежам в древнейшей истории человечества, особенно если к числам добавить наименование «тыс. лет до н. э. », или «тыс. лет тому назад», или просто «тыс. лет».
Так, позицию 233 тыс. лет в приводимой последовательности можно отождествить с датой рисского оледенения в Европе, общепризнанная геологическая дата которого 230 тыс. лет т. н. Позиция, соответствующая 377 тыс. лет, близка дате в 400 тыс. лет т. н. этому времени относят выход человечества из биоценоза.
Около середины II миллионолетия (1 597 тыс. л., согласно ряду) складывается древнейшая археологическая культура олдувай, в середине III миллионолетия (2 584 тыс. лет) появляются австралопитековые формы ископаемого человека, с которым связывают так называемое начало орудийности.
На протяжении 720-600 тыс. лет складывается трудовая традиция и формируется речь. Дата завершения этих процессов находится почти рядом с позицией ряда в 610 тыс. лет.
Действительно, эти рубежи разграничивают развитие человечества на отдельные этапы, которые иногда называют временными ступенями. Переход с одной временной ступени на другую считают эволюцией системы. Повторим ряд, обозначив жирным шрифтом те ступени, хронология которых проверена: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610, 987,1 597, 2584.
Одиннадцать из 18 позиций ряда проверены и подтверждены с достаточной степенью надежности и точности. Иногда говорят, что одно подтверждение – случайность, два – совпадение, три – тенденция.
В нашем случае не три, а 60% совпадений проверены и подтверждены. Такое число подтверждений можно считать выражением не столько тенденции, сколько закономерности.
Итак, хронология и периодизация, можно сказать, исторического развития с помощью ряда Фибоначчи разделена на 18 временных ступеней, имеющих планетарный характер. Повторим их 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1 597, 2 584. События, хронология которых оказывается за пределами ряда, имеют региональный характер.
Хронологические границы археологических эпох и периодов, найденные с помощью ряда Фибоначчи, жесткие. В них нет соглашения: они либо приемлемы, либо – нет. В основе такого выбора лежит научное мировоззрение, которое всегда строго и определенно.
Таковы, в первом приближении, возможности использования ряда Фибоначчи в разработке периодизации и общей хронологии развития человечества с древнейших времени до начала современной эпохи.
3.3. Последовательность Фибоначчи и теханализ рынков
Если практически все в нашем мире базируется на коэффициентах Фибоначчи, почему бы не использовать их в техническом анализе движения цен на биржах.
Впервые это предложил Ральф Нельсон Эллиотт.
Ральф Hельсон Эллиотт был инженером. После серьезной болезни в начале 1930-х гг. он занялся анализом биржевых цен, особенно индекса Доу-Джонса. После ряда весьма успешных предсказаний Эллиотт опубликовал в 1939 году серию статей в журнале Financial World Magazine. В них впервые была представлена его точка зрения, что движения индекса Доу-Джонса подчиняются определенным ритмам. Согласно Эллиотту, все эти движения следуют тому же закону, что и приливы – за приливом следует отлив, за действием (акцией) следует противодействие (реакция). Эта схема не зависит от времени, поскольку структура рынка, взятого как единое целое, остается неизменной.
Эллиотт писал: «Закон природы включает в рассмотрение важнейший элемент-ритмичность. Закон природы – это не некая система, не метод игры на рынке, а явление, характерное, видимо, для хода любой человеческой деятельности. Его применение в прогнозировании революционно».
Этот шанс предсказать движения цен побуждает легионы аналитиков трудиться денно и нощно. Мы сосредоточимся на способности делать предсказания и попытаемся выяснить, возможно, это или нет. Вводя свой подход, Эллиотт был очень конкретен. Он писал: «Любой человеческой деятельности присущи три отличительных особенности: форма, время и отношение, и все они подчиняются суммационной последовательности Фибоначчи».
При анализе поведения финансовых рынков пропорции чисел Фибоначчи дают ориентиры не только возможных уровней отката цен, но и указывают возможную величину хода в случае продолжения тенденции на рынке. Если после хода рынок откатывается, а затем продолжает ход в том же направлении, то в типичном случае величина продолженного хода может составить 1.618.
Очень кратко суть волновой теории Элиотта, касающейся поведения цен на рынках, заключается в следующем.
Полный цикл «бычьего» рынка состоит из 8 волн: 5 волн роста, за которыми следуют 3 волны падения.
Тенденция подразделяется на 5 волн в направлении следующей в иерархии, более продолжительной тенденции.
Коррекция всегда состоит из трех волн.
Простые коррекции бывают двух типов: зигзаги 5-3-5 и плоские волны 3-3-5.
Треугольники, как правило, образуются на четвертых волнах (эта модель всегда предшествует последней волне). Треугольник может также быть корректирующей волной В.
Любая волна является частью более длинной и подразделяется на более короткие.
Иногда одна из импульсных волн растягивается. Остальные две должны оставаться равными по времени и протяженности.
Математической основой теории волн Эллиотта является последовательность Фибоначчи. Количество волн, образующих тенденцию, совпадает с числами Фибоначчи.
Коэффициенты Фибоначчи и основанные на них отношения длины коррекции используются для определения ценовых ориентиров. Отношение длины коррекции к предыдущему движению рынка часто равняется 62%, 50% и 38% (Рис 23).
Правило чередования предупреждает, что не следует ждать одинакового проявления ценовой динамики два раза подряд.
«Бычьи» рынки не должны опускаться ниже основания предыдущей четвертой волны.
Волна 4 не должна перехлестываться с волной 1
Основными аспектами теории волн Элиотта являются (в порядке значимости): форма волны, соотношение волн и время.
В самом общем виде система приложения чисел Фибоначчи к валютному рынку FOREX (foreign exchange) работает следующим образом.
/>
Рис. 11. График цен на рынке FOREX
На рисунке 11 по оси X отложены цены швейцарского франка в долларах, по оси Y – время с шагом в 60 минут.
Методика прогностических расчетов строится на том, что численное соотношение значений «движение – откат» должно давать коэффициенты «золотого сечения», то есть:
— 1,618; 2,618; 4,236 (при движении);
— 0,618;' 0,382; 0,236 (при откате);
Эти численные значения и представляют собой те важные уровни, которые рынок «вспоминает» по ходу изменения цен. Именно на них ориентируется трейдер в своей игре.
Наиболее простое употребление числа Фибоначчи находят при расчете уровня отката (retracement) или отскока (rebound). Так как цены не могут непрерывно расти или падать продолжительное время, после каждого их изменения существует той или иной величины откат в противоположную сторону. Особенно ярко это явление видно после сильного и продолжительного движения. При этом откат 33% наиболее вероятен, а откат 66% наименее вероятен.
/>
Рис. 12. Уровни отката и отскока
Использование последовательности Фибоначчи позволяет увеличить наиболее вероятную нижнюю границу с 33% до 38,2% (число Фибоначчи 0,382) и в то же время уменьшить наименее вероятную дальнюю границу с 66% до 61,8% (число Фибоначчи 0,618). Достижение уровня в 38,2% происходит чрезвычайно часто, что обусловлено огромной популярностью теории Эллиотта. Действительно, поскольку большинство участников рынка ожидает именно такой откат, именно он и происходит. Расчет уровней откатов и отскоков – достаточно простое занятие, что делает этот анализ привлекательным. Кроме того, откаты и отскоки действуют как на главных трендах, так и на вторичных и краткосрочных. Таким образом, их можно наблюдать на недельных и часовых графиках.
3.4. Фундаментальные физические константы
Недавно физиками найдено простое и красивое соотношение, связывающее важнейшие безразмерные константы: постоянную тонкой структуры (α), число пи (π) и золотое отношение (Φ), вытекающее из чисел Фибоначчи. Формула имеет вид:
/>
На основе этой формулы получено новое расчетное значение постоянной тонкой структуры (α):
Альфа = α = 1/137,036009823754683675307501201348…
Напомним, что постоянная тонкой структуры α по определению равняется e2/hc, где e – заряд электрона, h – постоянная Планка, с – скорость света; приблизительно α равно 1/137.
Полученные результаты указывают на геометрический статус постоянной тонкой структуры, а также на то, что все безразмерные параметры, которые характеризуют микромир и Вселенную, являются принципиально вычисляемыми.
Исследования фундаментальных физических констант показали, что известные на сегодня фундаментальные физические константы очень жестко связаны между собой т. е. являются взаимозависимыми [22]. Это порождает надежду на то, что наконец-то появится хоть какая-то возможность подступиться к решению запутанной головоломки о таинственном числе «альфа», что не дает покоя физикам. Появились основания считать, что важнейшая физическая константа – постоянная тонкой структуры (α), также может быть связана с другими константами. Если такая связь действительно существует, то с учетом безразмерности постоянной тонкой структуры (α), наиболее простым соотношением эта константа должна быть связана не с размерными, а с безразмерными константами. Это тем более представляет интерес, поскольку значения некоторых безразмерных констант определены с очень высокой точностью.
В физике мы имеем дело с двумя классами констант – с физическими константами и с геометрическими константами. Н. В. Косинов считает, и к этому его подтолкнули результаты исследования фундаментальных физических констант, что постоянная тонкой структуры (α) νе есть физическая константа, а является геометрической константой. Поэтому представляет интерес выяснить какая существует связь у этой константы с другими геометрическими константами. По его мнению, известная связь постоянной тонкой структуры (α) с некоторыми физическими константами (постоянной Планка, зарядом, скоростью света) есть вторичное проявление более глубокой взаимосвязи физики и геометрии. Истоки такой связи и роль в этом математических констант современной наукой еще не раскрыты. Все безразмерные константы очень жестко связаны между собой внутри собственного семейства безразмерных констант, а их связь с размерными фундаментальными физическими константами является лишь следствием, т. е. вторичным проявлением общей взаимосвязи фундаментальных констант. Здесь уместно сослаться на мнение А. Пуанкаре о дополнительности физики и геометрии. Согласно Пуанкаре, на опыте мы всегда наблюдаем некую «сумму» физики и геометрии [3]. Если это так, то подобная «сумма» физики и геометрии должна проявляться на примере единого константного базиса в виде совокупности физических и геометрических констант. В качестве единого константного базиса для описания законов природы достаточно всего лишь трех физических и двух геометрических констант. Н. В. Косинов считает, что среди семейства фундаментальных физических констант существует только пять первичных суперконстант, от которых происходят все другие константы [22]. В пятиконстантном онтологическом базисе – три суперконстанты размерные, а две – безразмерные. Три размерные онтологические суперконстанты являются физическими, а две безразмерные онтологические суперконстанты – геометрическими. Пяти первичных суперконстант оказалось вполне достаточно, чтобы на их основе получить расчетом множество других фундаментальных констант [22]. Теперь становится понятным, что сотни констант в современной физике необоснованно наделены фундаментальным статусом, поскольку они не являются первичными константами. Здесь уместно вспомнить правило Оккама, в соответствии с которым не следует без необходимости увеличивать число сущностей, а также мнение Френеля о том, что «природа склонна к управлению многим с помощью малого» [1].
На роль одной из геометрических суперконстант претендует постоянная тонкой структуры (α). Так что, видимо, константы α и π имеют первичный онтологический статус. Из этих соображений очень важным является выяснение роли и места постоянной тонкой структуры (α) в семействе безразмерных констант.
Ниже показана интересная взаимосвязь, выявленная между тремя важнейшими безразмерными константами: постоянной тонкой структуры (α), числом пи (π) и золотым сечением (Φ). Это простая и красивая формулу. Найденное соотношение имеет вид:
где: Φ = Phi = 1,6180339…
С использованием числа φ = phi = 0,6180339… формула примет вид:
/>
/>
То, что α и π оказались связанными с золотым отношением Φ, вытекающим из чисел Фибоначчи, указывает на причастность постоянной тонкой структуры (α), и числа пи (π) к закону гармонии в природе. Если природа не прошла мимо этой взаимосвязи, то двух безразмерных констант должно быть вполне достаточно для геометрического константного базиса Вселенной. Для ученых также должно быть вполне достаточно двух безразмерных констант, чтобы на их основе, с помощью расчета, получать другие безразмерные константы.
Воспользуемся этими формулами для вычисления точного значения постоянной тонкой структуры.
Значение числа пи (π) сегодня известно с очень большой точностью и уже вычислено до 206 158 430 000 знаков (!) [21]:
Πθ = π = 3,1415926535897932384626433832795… (точно).
Значение золотого сечения (Φ) также известно с очень большой точностью и уже вычислено до 1 500 000 000 знаков:
Phi =Φ = 1,61803398874989484820458683436564… (ςочно),
phi = φ = 0,61803398874989484820458683436564… (ςочно).
Столь точные значения чисел π, Φ θ φ οозволяют, на основе приведенных выше формул, вычислить значение постоянной тонкой структуры (α). Ниже приведено значение числа «альфа», полученное расчетом, где, для примера, показаны 33 знака этой константы:
Альфа = α = 0,00729735199737736169573530153098411…
Обратное значение постоянной тонкой структуры (α– 1) соответственно равно:
(Альфа)– 1 = α– 1 = 137,036009823754683675307501201348…
Если учесть вышеизложенное, то вся запутанная головоломка о таинственном числе «альфа» проистекала из того, что не была учтена геометрическая сущность этой константы. В результате, не до конца выясненная связь физики и геометрии породила сложнейшую проблему постоянной тонкой структуры, которую безуспешно пытались решить выдающиеся ученые прошлого столетия. И сейчас эта проблема входит в 10 важнейших проблем физики, которые получили название «проблемы тысячелетия» [21, с. D3].
Новый геометрический статус постоянной тонкой структуры (α) позволит в корне изменить представления об этой константе и снимет с нее завесу таинственности. Если принять геометрическую сущность постоянной тонкой структуры, то это будет означать, что все безразмерные параметры, которые характеризуют микромир и Вселенную, являются принципиально вычисляемыми. Кроме того, окончательно прояснится в чем состоит и как проявляется связь физики и геометрии в различных явлениях материального мира и как эта связь представлена в константных базисах физических теорий. Ведь до сих пор остаются без ответа вопросы: какой геометрией воспользовалась природа и что является онтологическим базисом материи?
Помимо этого, кроме приведенных выше формул существуют математические соотношения для точного и независимого вычисления значения постоянной тонкой структуры (α), как это имеет место отдельно для числа пи (π) и отдельно для золотой пропорции (Φ). Их, эти независимые математические соотношения, необходимо искать.
Итак, в результате анализа, основанного на использовании пропорции Фибоначчи, физики пришли к следующим интригующим выводам:
1. Найдено простое и красивое соотношение, связывающее важнейшие безразмерные константы: постоянную тонкой структуры α, число π и золотое отношение Φ.
2. Формула позволила получить новое точное значение постоянной тонкой структуры. Полученные результаты подтверждают геометрический статус постоянной тонкой структуры.
3. Геометрический статус постоянной тонкой структуры указывает на то, что все безразмерные параметры, которые характеризуют микромир и Вселенную, являются принципиально вычисляемыми.
4. Геометрический статус постоянной тонкой структуры указывает на то, что существуют математические соотношения для точного и независимого вычисления значения постоянной тонкой структуры (α), как это имеет место отдельно для числа пи (π) и отдельно для золотой пропорции (Φ).
5. Постоянная тонкой структуры и число пи являются онтологическими суперконстантами, от которых происходят все безразмерные физические константы.
6. То, что α и π оказались связанными с золотым отношением Φ, вытекающим из чисел Фибоначчи, указывает на причастность постоянной тонкой структуры (α), и числа пи (π) к закону гармонии в природе.
7. Отсутствие геометрической теории с применением двух констант – числа пи и постоянной тонкой структуры говорит о том, что геометрия, которой воспользовалась природа остается еще вне поля зрения ученых.
продолжение
--PAGE_BREAK--
4. Алгоритмы вычисления чисел Фибоначчи и их сложность
В последней главе дипломной работы исследуем вопрос о возможности быстрого вычисления чисел Фибоначчи на компьютере. Эта задача представляет интерес, в связи с тем, что пропорции Фибоначчи обнаруживают свое проявление в самых разнообразных областях. Как известно, правильность – далеко не единственное качество, которым должна обладать хорошая программа. Одним из важнейших качеств является эффективность, характеризующая прежде всего время выполнения программы T(n) для различных входных данных (параметра n).
Нахождение точной зависимости T(n) для конкретной программы – задача достаточно сложная. По этой причине обычно ограничиваются асимптотическими оценками этой функции, то есть описанием ее примерного поведения при больших значениях параметра n. Иногда для асимптотических оценок используют традиционное отношение O (читается «О большое») между двумя функциями f(n) = O(g(n)), определение которого можно найти в любом учебнике по математическому анализу, хотя чаще применяют отношение эквивалентности Θ (читается «тэта большое»).
В качестве первого примера вернемся к только что рассмотренным программам нахождения факториала числа. Легко видеть, что количество операций, которые должны быть выполнены для нахождения факториала n! Числа № в первом приближении прямо пропорционально этому числу, ибо количество повторений цикла (итераций) в данной программе равно n. В подобной ситуации принято говорить, что программа (или алгоритм) имеет линейную сложность (сложность O(n) или Θ(n)). Или более обще:
ОПРЕДЕЛЕНИЕ. Алгоритм имеет линейную сложность, если количество выполняемых при этом машинных операций (сложность O(n) или Θ(n)) пропорционально первой степени объема данных задачи (например, количеству перемножаемых чисел, количеству городов в транспортной задаче и т. п.)
Можно ли вычислить факториал быстрее? Оказывается, да. Можно написать такую программу, которая будет давать правильный результат для тех же значений n, для которых это делают все приведенные выше программы, не используя при этом ни итерации, ни рекурсии. Ее сложность будет Θ(1), что фактически означает организацию вычислений по некоторой формуле без применения циклов и рекурсивных вызовов!
Не менее интересен и пример вычисления n-го числа Фибоначчи. В процессе ее исследования фактически уже было выяснено, что ее сложность является экспоненциальной и равна Θ(2n). Подобные программы практически не применимы на практике. В этом очень легко убедиться, попробовав вычислить с ее помощью 40-е число Фибоначчи. По этой причине вполне актуальна следующая задача.
Задача 1: Написать программу, печатающую n-ое число Фибоначчи, которая имела бы линейную сложность.
Вот решение этой задачи, в котором переменные j и k содержат значения двух последовательных чисел Фибоначчи.
Текст программы.
public class FibIv1 {
public static void main(String [] args) throws Exception {
int № = Xterm. inputInt(«Введите n-> „);
Xterm. print(“f(» + № + ")");
if (n
Xterm. print(" не определено\n");
} else if (n
Xterm. println(" = " + n);
} else {
long i = 0;
long j = 1;
long k;
int m = n;
while (--m > 0) {
k = j;
j += i;
i = k;
}
Xterm. println(" = " + j);
}
}
}
Следующий вопрос вполне естественен – а можно ли находить числа Фибоначчи еще быстрее?
После изучения определенных разделов математики совсем просто вывести следующую формулу для n-ого числа Фибоначчи Fn, которую легко проверить для небольших значений n:
/>
Может показаться, что основываясь на ней, легко написать программу со сложностью Θ(1), не использующую итерации или рекурсии.
Текст программы.
public class FibIv2 {
public static void main(String [] args) throws Exception {
int № = Xterm. inputInt(«Введите n-> „);
double f = (1.0 + Math. sqrt(5.)) / 2.0;
int j = (int)(Math. pow(f,n) / Math. sqrt(5.) + 0.5);
Xterm. println(“f(» + № + ") = " + j);
}
}
На самом деле эта программа использует вызов функции возведения в степень Math. pow(f,n), которая не может быть реализована быстрее, чем за логарифмическое время (log2 №). Про алгоритмы, в которых количество операций примерно пропорционально log № (в информатике принято не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность (Θ(log №)).
Для вычисления n-го числа Фибоначчи существует такой алгоритм, программную реализацию которого мы приведем без дополнительных комментариев, – иначе нужно объяснять слишком много (связь чисел Фибоначчи со степенями матрицы порядка два, использование классов для работы с матрицами, алгоритм быстрого возведения матрицы в степень).
Задача 2: Написать программу, печатающую n-ое число Фибоначчи, которая имела бы логарифмическую сложность.
Текст программы.
public class FibIv3 {
public static void main(String [] args) throws Exception {
int № = Xterm. inputInt(«Введите n-> „);
Xterm. print(“f(» + № + ")");
if (n
Xterm. println(" не определено");
} else if (n
Xterm. println(" = " + n);
} else {
Matrix b = new Matrix(1, 0, 0, 1);
Matrix c = new Matrix(1, 1, 1, 0);
while (n>0) {
if ((n&1) == 0) {
№ >>>= 1; c. square();
} else {
n-= 1; b. mul(c);
}
}
Xterm. println(" = " + b. fib());
}
}
}
class Matrix {
private long a, b, c, d;
public Matrix(long a, long b, long c, long d) {
this. a = a; this. b = b; this. c = c; this. d = d;
}
public void mul(Matrix m) {
long a1 = a*m. a+b*m. c; long b1 = a*m. b+b*m. d;
long c1 = c*m. a+d*m. c; long d1 = c*m. b+d*m. d;
a = a1; b = b1; c = c1; d = d1;
}
public void square() {
mul(this);
}
public long fib() {
return b;
}
}
Если попробовать посчитать десятимиллионное число Фибоначчи с помощью этой и предыдущей программ, то разница во времени счета будет вполне очевидной. К сожалению, результат будет неверным (в обоих случаях) в силу ограниченности диапазона чисел типа long.
В заключение приведем сравнительную таблицу времен выполнения алгоритмов с различной сложностью и объясним, почему с увеличением быстродействия компьютеров важность использования быстрых алгоритмов значительно возрастает.
Рассмотрим четыре алгоритма решения одной и той же задачи, имеющие сложности log n, n, n2, 2n и соответственно. Предположим, что второй из этих алгоритмов требует для своего выполнения на некотором компьютере при значении параметра n=103 ровно одну минуту времени. Тогда времена выполнения всех этих четырех алгоритмов на том же компьютере при различных значениях параметра будут примерно такими, как в таблице 2.
Таблица 2
Сравнительная таблица времен выполнения алгоритмов
Сложность алгоритма
n=10
n=103
n=106
log n
0.2 сек.
0,6 сек.
1,2 сек.
n
0.6 сек.
1 мин.
16,6 час.
n2
6 сек.
16,6 час.
1902 года
2n
1 мин.
10295 лет
10300 000 лет
Когда начинающие программисты тестируют свои программы, то значения параметров, от которых они зависят, обычно невелики. Поэтому даже если при написании программы был применен неэффективный алгоритм, это может остаться незамеченным. Однако, если подобную программу попытаться применить в реальных условиях, то ее практическая непригодность проявится незамедлительно.
С увеличением быстродействия компьютеров возрастают и значения параметров, для которых работа того или иного алгоритма завершается за приемлемое время. Таким образом, увеличивается среднее значение величины, и, следовательно, возрастает величина отношения времен выполнения быстрого и медленного алгоритмов. Чем быстрее компьютер, тем больше относительный проигрыш при использовании плохого алгоритма.
5. Методика изучения чисел Фибоначчи в старших классах
5.1. Общие методические указания
Начинать изучение чисел Фибоначчи следует с демонстрации их естественного появления во многих задачах и ситуациях. Помимо классической задачи о кроликах необходимо сформулировать и другие задачи, в которых появляются числа Фибоначчи.
Наглядный пример естественного возникновения чисел Фибоначчи дают, например, так называемые «родословные деревья пчел» Рассмотрим родословную пчелы-самца. Каждый самец (называемый также трутнем) появляется на свет непарным путем от самки (называемой также маткой), однако каждая самка имеет двух родителей – самца и самку. Несколько начальных уровней такого дерева представлены ниже на рисунке 13.
/>
Рис. 13.
У трутня один дед и одна бабка, один прадед и две прабабки, два прапрадеда и три прапрабабки. И вообще, как легко установить по индукции, у него ровно Fn+1 праn-дедушек и Fn+2 праn-бабушек.
Числа Фибоначчи часто обнаруживаются в природе – возможно, по причинам, аналогичным закону образования родословного дерева пчел. К примеру, семечки, плотно набитые в крупную «корзинку» обыкновенного подсолнуха, располагаются по спиралям – обычно это 34 спирали, закручивающиеся в одном направлении, и 55 спиралей – в другом. Корзинки поменьше будут иметь соответственно 21 и 34, или же 13 и 21 спираль, а однажды в Англии демонстрировался гигантский подсолнух с 89 спиралями одного направления и 144 – другого. Подобные закономерности обнаруживаются и в некоторых видах сосновых шишек.
Еще рассмотрим пример другого рода. Предположим, что друг на друга наложены две стеклянные пластинки. Сколько существует способов аn прохождения луча света через пластинки или отражения от них после изменения его направления № раз? Несколько первых случаев таковы (см. рис. 14):
а0= 1 а1 = 2 а2 = 3 а3 = 5
/>
Рис. 14.
Когда № четно, получается четное число преломлений, и луч проходит насквозь; когда же № нечетно, луч отражается и выходит с той стороны, с которой и вошел. По-видимому, аn будут числами Фибоначчи и непродолжительное разглядывание рисунка показывает почему: при № ≥ 2 преломляющиеся № раз лучи либо претерпевают свое первое отражение от внешней поверхности и продолжают прохождение an-1 способами, либо начинают с отражения от внутренней поверхности и затем снова отражаются в обратном направлении, чтобы закончить прохождение an-2 способами. Таким образом, получается фибоначчиева рекуррентность an = an-1 + an-2.Начальные условия отличаются, но не очень, поскольку а0= 1 = F2 и а1 = 2 = F3; следовательно, все просто сдвигается на два, так что au = Fu+2.
После демонстрации элементарных задач нужно кратко рассказать об истории изучения чисел Фибоначчи, напомнить, что эти числа ввел в 1202 г. Леонардо Фибоначчи, и математики постепенно стали выяснять все больше и больше интересного о них. Например, Эдуард Люка, причастный к головоломке о ханойской башне, активно занимался ими во второй половине девятнадцатого столетия (в действительности, благодаря именно Люка, название «числа Фибоначчи» стало общеупотребительным). Одно из его удивительных достижений состояло в использовании свойств чисел Фибоначчи для доказательства того, что 39-значное число Мерсенна 2127 – 1 является простым.
После первого знакомства с числами Фибоначчи имеет смысл поговорить о проявлениях свойств чисел Фибоначчи в природе, искусстве, науке и технике. Здесь же нужно сформулировать понятие «золотого сечения» и на примерах проиллюстрировать все разнообразие ситуаций, в которых оно обнаруживается. Данная тема воспринимается школьниками обычно очень эмоционально, и это надо использовать, чтобы закрепить интерес к ее изучению и к изучению математики вообще.
После этого можно выбрать одно или несколько направлений, которые будут изучаться более подробно. Выигрышным вариантом следует признать изучение рекуррентных соотношений. В рамках данной темы возможны отклонения в самых различных направлениях. Многообразие задач здесь тоже очень велико. И ценно также то, что в процессе изучения темы выстраивается стройная теория рекуррентных соотношений. Т. е. учащиеся знакомятся с цельной теорией, имеющей множество приложений. Используемые же при этом методы достаточно элементарны и доступны для понимания. При этом охватываются многие разделы комбинаторики.
На уроках информатики стоит решить несколько комбинаторных задач и написать для них программы, вычисляющие неизвестные значения. Можно поэкспериментировать с нахождением времени, необходимого машине на вычисление тех или иных чисел.
5.2. Решение задач
При решении многих комбинаторных задач школьники часто пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского recurrere – возвращаться). Пользуясь рекуррентным соотношением, можно свести задачу об № предметах к задаче об № – 1 предметах, потом к задаче об № – 2 предметах и т. д. Последовательно уменьшая число предметов, доходим до задачи, которую уже легко решить. Во многих случаях удается получить из рекуррентного соотношения явную формулу для решения комбинаторной задачи.
Например, так можно вывести формулу Рn = n! для числа перестановок № элементов с помощью формулы для числа размещений без повторений. Но ту же формулу можно вывести и иначе, найдя сначала рекуррентное соотношение, которому удовлетворяет Рn.
Пусть у нас есть № предметов a1,..., an-1, an. Любую их перестановку можно получить так: взять некоторую перестановку предметов a1,..., an-1 и присоединить к ней элемент аn. Ясно, что элемент аn может занять различные места. Его можно поставить в самое начало, между первым и вторым элементами перестановки, между вторым и третьим, можно поставить и в самый конец. Число различных мест, которые может занять элемент аn, равно n, и потому из каждой перестановки элементов a1,..., an-1 получается № перестановок элементов a1,..., an-1, an. Но это означает, что перестановок из № элементов в № раз больше, чем перестановок из № – 1 элементов. Тем самым установлено рекуррентное соотношение:
Рn = № Рn-1.
Пользуясь этим соотношением, последовательно выводим, что:
Рn = № Рn-1 = № (n-1) Рn-2 = № (n-1) … 2Р1.
Но Рn = l, так как из одного элемента можно сделать лишь одну перестановку. Поэтому:
Рn = № (n-1) … 2 1 = n!.
Таким образом, мы снова получили формулу Рn = n!.
Много рекуррентных соотношений встречалось нам при решении задач на разбиения, задач о фигурах на шахматной доске и т. д. Сейчас мы рассмотрим еще несколько таких задач, а в заключение остановимся на общей теории рекуррентных соотношений.
Задача о кроликах: Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?
Решение: Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут н исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов.
Обозначим через F(n) количество пар кроликов по истечении № месяцев с начала года. Мы видим, что через № + 1 месяцев будут эти F(n) пар и еще столько новорожденных пар кроликов, сколько было в конце месяца № – 1, то есть еще F(n – 1) пар кроликов. Иными словами, имеет место рекуррентное соотношение:
F(n + l) = F(n) + F(n – l). (35)
Так как, по условию, F(0) = 1 и F(1) = 2, то последовательно находим:
F(2) = 3, F(3) = 5, F(4) = 8 и т. д.
В частности, F(12) =377.
Числа F(n) называют числами Фибоначчи. Они обладают целым рядом замечательных свойств. Сейчас мы выведем выражение этих чисел через комбинаторные коэффициенты Ckm. Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.
Найти число n-последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не идут подряд.
Чтобы установить эту связь, возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность 010010100010 устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители – в конце 7-го месяца, «дед» – в конце 5-го месяца и «прадед» – в конце второго месяца. Исходная пара кроликов зашифровывается при этом последовательностью 000000000000.
Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд – только что появившаяся пара не может, по условию, принести приплод через месяц. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов всегда имеют разную «генеалогию», так как, по условию, крольчиха дает приплод, состоящий только из одной пары кроликов.
Установленная связь показывает, что число n-последовательностей, обладающих указанным свойством, равно F(n).
Докажем теперь, что
F(n) = />+ C1n + />+… + />, (36)
где р = (n+1)/2, если № нечетно, и р = n/2, если № четно.
Иными словами, р – целая часть числа (n+1)/2 – (в дальнейшем мы будем обозначать целую часть числа α χерез E(α); ςаким образом, р = E [(n+1)/2].
В самом деле, F(n) – это число всех n-последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно k единиц и № – k нулей, равно />. Так как при этом должно выполняться неравенство k ≤ № – k + 1, то k изменяется от 0 до E [(n+1)/2]. Применяя правило суммы, приходим к соотношению (36).
Равенство (36) можно доказать и иначе. Положим:
G (n) = />+ C1n + />+… + />,
где р = E [(n+1)/2]. Из равенства />= />+ />легко следует, что:
G(n) = G(n – 1) + G(n – 2). (37)
Кроме того, ясно, что G(1)=2 = F(1) и G(2) =3 = F(2).
Так как обе последовательности F(n) и G(n) удовлетворяют рекуррентному соотношению Х(n) =Х(n – 1) + X (n – 2), то имеем:
G(3) = G(2) + G(1) = F(2) + F(l) = F(3),
и, вообще, G(n)=F(n).
Приведем и другой метод доказательства.
Мы непосредственно установили связь между задачей Фибоначчи и комбинаторной задачей. Эту связь можно было установить и иначе, непосредственно доказав, что число Т(n) решений комбинаторной задачи удовлетворяет тому же рекуррентному соотношению:
T(n+1) = T(n) + T(n – 1), (38)
что и числа Фибоначчи.
В самом деле, возьмем любую (n-1)-последовательность нулей и единиц, удовлетворяющую условию, что никакие две единицы не идут подряд. Она может оканчиваться или на 0, или на 1. Если она оканчивается на 0, то, отбросив его, получим n-последовательность, удовлетворяющую нашему условию. Обратно, если взять любую n-последовательность нулей и единиц, в которой подряд не идут две единицы, и приписать к ней нуль, то получим (n+1)-последовательность с тем же свойством. Мы доказали, что число «хороших» последовательностей, оканчивающихся на нуль, равно Т(n).
Пусть теперь последовательность оканчивается на 1. Так как двух единиц подряд быть не может, то перед этой единицей стоит нуль. Иными словами, последовательность оканчивается на 01. Остающаяся же после отбрасывания 0 и 1 (n – 1)-последовательность может быть любой, лишь бы в ней не шли подряд две единицы.
Поэтому число «хороших» последовательностей, оканчивающихся единицей, равно Т(n – 1). Но каждая последовательность оканчивается или на 0, или на 1. В силу правила суммы получаем, что Т(n + 1) = Т(n) + Т(n – 1).
Мы получили, таким образом, то же самое рекуррентное соотношение. Отсюда еще не вытекает, что числа Т(n) и F(n) совпадают.
Чтобы доказать совпадение чисел Т(n) и F(n), надо еще показать, что T(n)=F(n) и T(2) – F(2) – тогда уже в силу рекуррентного соотношения имеем и T(3)=F(3), T(4)=T(4) и т. д. Существуют две 1-последовательности, удовлетворяющие поставленному условию: 0 и 1, и три 2-последовательности; 00, 01 и 10.
Поэтому T(1) = 2 = F(1) и T(2) =3 =. F(2). Тем самым утверждение доказано.
Для решения комбинаторных задач часто применяют метод, использованный выше. Устанавливают для данной задачи рекуррентное соотношение и показывают, что оно совпадает с рекуррентным соотношением для другой задачи, решение которой нам уже известно. Если при этом совпадают и начальные члены последовательностей в достаточном числе (позже мы остановимся подробнее на том, сколько членов должны совпадать), то обе задачи имеют одинаковые решения.
Применим описанный прием для решения следующей задачи.
Задача. Пусть дано некоторое множество из № предметов, стоящих в определенном порядке. Разобьем это множество на две непустые части так, чтобы одна из этих частей лежала левее второй (то есть, скажем, одна часть состоит из элементов от первого до m-го, а вторая – из элементов от (m + 1)-го до n-го). После этого каждую из частей таким же образом разобьем на две непустые части (если одна из частей состоит уже из одного предмета, она не подвергается дальнейшим разбиениям). Этот процесс продолжается до тех пор, пока не получим части, состоящие из одного предмета каждая. Сколько существует таких процессов разбиения (два процесса считаются различными, если хотя бы на одном шагу они приводят к разным результатам)?
Решение: Обозначим число способов разбиения для множества из n+1 предметов через Вn. На первом шагу это множество может быть разбито № способами (первая часть может содержать один предмет, два предмета,..., и предметов). В соответствии с этим множество всех процессов разбиений распадается на № классов – в s-й класс входят процессы, при которых первая часть состоит из s предметов.
Подсчитаем число процессов в s-м классе. В первой части содержится s элементов. Поэтому ее можно разбивать далее Bs-1 различными процессами. Вторая же часть содержит № – s+1 элементов, и ее можно разбивать далее Bn-s процессами. По правилу произведения получаем, что s-й класс состоит из Bs-1Bn-s различных процессов. По правилу суммы отсюда вытекает, что:
Bn = B0Bn-1 + B1 Bn-2 + … + Bn-1 B0(39)
Мы получили рекуррентное соотношение для Bn. Этому соотношению удовлетворяют числа:
Тn = />
Чтобы доказать равенство
Вn = Тn = />. (40)
нам осталось показать, что начальные члены Т0и В0последовательностей T0, T1,..., Tn, … и В0, В1,..., Вn,… совпадают.
Мы имеем T0= />=1. С другой стороны, В0 = 1, так как множество из одного элемента можно разделить единственным образом. Итак, В0= T0.Но по рекуррентной формуле имеем В1 = />=1.Так как T0удовлетворяет той же рекуррентной формуле, то T1 =/>= 1.Далее устанавливаем, что:
B2 = B0B1 + B1 B0= 2 и T2 = T0T1 + T1 T0= 2 и т. д.
Итак, все члены обеих последовательностей совпадают. Таким образом, доказан следующий результат:
Число процессов последовательного деления множества из № + 1 элементов, расположенных в некотором порядке, равно:
Тn = />.
продолжение
--PAGE_BREAK--