2.4 Рекурсия на примере факториала [Оберон / Компонентный Паскаль / Вики]

Это старая версия документа!

Содержание

2.3 Свойства чисел Фибоначчи

2.3 Свойства чисел Фибоначчи

1. Фибоначчи: гений средневековья

Леонардо Бездельник, видимо, обладал отменным чувством самоиронии. И это отличает людей с высоким интеллектом от задавак. О его познаниях в области счётной арифметики и геометрии, говорит тот факт, что примеры из его учебника (а это 13 век) дошли до нашего времени, и вполне себе употребимы. Более того, от него дошли идеи, которые развиты сейчас не очень полно, и будущее у них впереди. Наш соотечественник Стахов А.П. ¹⁾ разработал умопомрачительную позиционную систему счисления на иррациональном основании (на идеях Фибоначчи). Он же предложил создавать компьютеры на избыточной позиционной системе счисления, которые обладают мощнейшей устойчивостью к сбоям. И это всё дело будущего. Вот такой он, этот Леонардо Боначчи из 12-го века.

2. Золотая пропорция

В Эпоху Возрождения Леонардо да Винчи создал очень известный рисунок — «Витрувианский человек». Рисунок на столько совершенен, что потрясает воображение. Как оказалось, чтобы создать такой совершенный рисунок, Леонардо да Винчи воспользовался подсказкой, данной ему Фибоначчи. Например, отношение длины всего тела, к той части, что от пупка до пяток — 1,6180339887. А если взять длину части тела от пупка до пяток и сравнить с длиной от пупка до макушки — 1,6180339887…??? А если взять длину всей кисти к длине ладони — 1,6180339887!!! А если соотнести длину ладони к длине пальцев получится… 1,6180339887!!!! И это число преследует человека повсюду. Вот так Леонардо, с помощью математики создал свой шедевр. Мы тоже попробуем сейчас найти это число так точно, на сколько оно того заслуживает.

3. Задача о золотом сечении

Чтобы точно вычислить значение золотого сечения, нам необходимо знать, как создать непредельный ряд с основанием «1» ²⁾ . В целом, этот метод известен. Достаточно взять сумму двух предыдущих членов ряда, чтобы получить третий. А вот чтобы найти саму золотую пропорцию — необходимо разделить последующий член пропорции, на предыдущий. И здесь есть интересная особенность: чем выше номера членов — тем точнее пропорция.

Итак, нам потребуется три переменных. Две хранят предыдущее значение двух членов ряда Фибоначчи, одна — последующее. Также нам потребуется переменная, которая будет отвечать за счётчик цикла. И, собственно, сам цикл.

Hello10.odc:

MODULE TestHello10;
	(* это программа на языке
	Компонентный Паскаль. Она показывает
	как можно найти точную золотую пропорцию. *)
 
	IMPORT Log,
		мМат := Math;
 
	PROCEDURE Старт*;
		VAR
			цРез0, цРез1, цРез: LONGINT;
			цИтер: INTEGER;
 
	BEGIN
		цРез0 := 0;
		цРез1 := 1;
		цИтер:= 1;
		WHILE цИтер < 40 DO
			цРез := цРез0 + цРез1;
			Log.Int(цИтер); Log.String(' * '); Log.Real(цРез / цРез1); Log.Ln;
			цРез0 := цРез1;
			цРез1 := цРез;
			INC(цИтер)
		END;
	END Старт;
 
BEGIN
END TestHello10.
 
^TestHello10.Старт

В программе применён простейший метод обмена данными: вычисляется новый член ряда, находится новое значение золотой пропорции, а затем старым членам присваивается новое значение из найденного нового члена.

А теперь посмотрим на вывод программы:

компилируется "TestHello10"   168   0
старый модуль TestHello10 выгружен
1 *  1.0
2 *  2.0
3 *  1.5
4 *  1.666666666666667
5 *  1.6
6 *  1.625
7 *  1.615384615384615
8 *  1.619047619047619
9 *  1.617647058823529
10 *  1.618181818181818
11 *  1.617977528089888
12 *  1.618055555555556
13 *  1.618025751072961
14 *  1.618037135278515
15 *  1.618032786885246
16 *  1.618034447821682
17 *  1.618033813400125
18 *  1.618034055727554
19 *  1.618033963166706
20 *  1.618033998521803
21 *  1.618033985017358
22 *  1.618033990175597
23 *  1.618033988205325
24 *  1.618033988957902
25 *  1.618033988670443
26 *  1.618033988780243
27 *  1.618033988738303
28 *  1.618033988754322
29 *  1.618033988748204
30 *  1.618033988750541
31 *  1.618033988749648
32 *  1.618033988749989
33 *  1.618033988749859
34 *  1.618033988749909
35 *  1.61803398874989
36 *  1.618033988749897
37 *  1.618033988749894
38 *  1.618033988749895
39 *  1.618033988749895

Обратите внимание на интересную закономерность: нечётный результат — меньше золотой пропорции, чётный — больше. Также стоит обратить внимание на тот факт, что в качестве имён переменных и имён процедур использованы имена на русском языке. Следующая пара повторяет эту закономерность, но уже гораздо ближе к истинной золотой пропорции. И каждый шаг приближает вычисления к ней ³⁾.

На шаге 38 и 39 эти числа уже равны. И здесь нет ошибки: сказывается недостаточная точность вычислений с плавающей запятой. В примере использован цикл 'WHILE' и это не оптимальное решение. Требуется вручную контролировать переменную 'цИтер'. В качестве самостоятельного задания, предлагается переписать этот цикл использую FOR.

¹⁾

У Стахова Алексея Петровича есть замечательная книга «Коды золотой пропорции». Настоятельно рекомендуется к прочтению.

²⁾

Непредельный ряд с основанием «1» хорошо известен из задачи Фибоначчи «О кроликах», предельный ряд с основанием «0» известен всем программистам — это классический двоичный ряд «0 1 2 4 8 16 32…». Мало кто знает, что таких рядов множество, и чем выше индекс непредельного ряда — тем больше избыточность такой позиционной системы счисления. И тем более она помехоустойчива. Всем известно, что чем сложнее система — тем выше вероятность отказа. С непредельными позиционными системами счисления — всё с точностью наоборот: чем крупнее система, тем выше надёжность. Это очень необычное свойство.

³⁾

Точное значение числа золотой пропорции установить невозможно — это число иррационально (не имеет конца). С помощью классического двоичного ряда можно получить только число «2». Кроме того, ряды золотой пропорции обладают признаками чётности (если их представлять двоичным кодом). Такое свойство непредельных позиционных систем счисления позволяет проектировать компьютеры с автоматическим частично-гарантированным исправлением одиночных и множественных ошибок. У классического двоичного ряда — такое невозможно. Вообще. Это вообще очень большая и интересная тема.

Инструменты пользователя

Инструменты сайта

Содержание

2.3 Свойства чисел Фибоначчи

1. Фибоначчи: гений средневековья

2. Золотая пропорция

3. Задача о золотом сечении

Инструменты страницы