Различия

Показаны различия между двумя версиями страницы.

--- bb:redbook:204 [2017/08/30 09:12]
prospero78 [3. Задача о золотом сечении]
+++ bb:redbook:204 [2020/10/29 07:08] (текущий)
@@ Строка 1: / Строка 1: @@
-===== 2.3 Свойства чисел Фибоначчи ======
+=====2.4 Рекурсия на примере факториала=====
-==== 1. Фибоначчи: гений средневековья ====
+====1. Понятие о рекурсии====
-**Леонардо Бездельник**, видимо, обладал отменным чувством самоиронии. И это отличает людей с высоким интеллектом от задавак. О его познаниях в области счётной арифметики и геометрии, говорит тот факт, что примеры из его учебника (а это 13 век) дошли до нашего времени, и вполне себе употребимы. Более того, от него дошли идеи, которые развиты сейчас не очень полно, и будущее у них впереди. Наш соотечественник **Стахов А.П.** (( У Стахова Алексея Петровича есть замечательная книга «Коды золотой пропорции». Настоятельно рекомендуется к прочтению. )) разработал умопомрачительную //позиционную систему счисления на иррациональном основании// (на идеях Фибоначчи). Он же предложил создавать компьютеры на //избыточной позиционной системе счисления//, которые обладают мощнейшей устойчивостью к сбоям. И это всё дело будущего. Вот такой он, этот **Леонардо Боначчи** из 12-го века.
+''Рекурсия'' это такая ''рекурсия'', которая в ''рекурсии'' подразумевает ''рекурсию'', которая продолжает вызывать ''рекурсию'', которая... ''Рекурсия'' — это обращение к себе. Причём, это обращение может быть настолько многоуровневым, что смотря на самую дальнюю точку — просто не видишь её конец. Очень не плохо показана идея ''рекурсии'' в фильме "Начало" с [[https://ru.wikipedia.org/wiki/%D0%94%D0%B8_%D0%9A%D0%B0%D0%BF%D1%80%D0%B8%D0%BE,_%D0%9B%D0%B5%D0%BE%D0%BD%D0%B0%D1%80%D0%B4%D0%BE|Леонардо Ди Каприо]]. Если вы его не могли посмотреть, то ещё можно понять что такое ''рекурсия'' из детского не очень доброго стишка, но, возможно, как любят говорить киношники — "основанного на реальных событиях":
-==== 2. Золотая пропорция ====
+	У попа была собака. Он её любил.
-В //Эпоху Возрождения// **Леонардо да Винчи** создал очень известный рисунок — **«Витрувианский человек»**. Рисунок на столько совершенен, что потрясает воображение. Как оказалось, чтобы создать такой совершенный рисунок, **Леонардо да Винчи** воспользовался подсказкой, данной ему **Фибоначчи**. Например, отношение длины всего тела, к той части, что от пупка до пяток — 1,6180339887. А если взять длину части тела от пупка до пяток и сравнить с длиной от пупка до макушки — 1,6180339887...??? А если взять длину всей кисти к длине ладони — 1,6180339887!!! А если соотнести длину ладони к длине пальцев получится... 1,6180339887!!!! И это число преследует человека повсюду. Вот так Леонардо, с помощью математики создал свой шедевр. Мы тоже попробуем сейчас найти это число так точно, на сколько оно того заслуживает.
+	Она съела кусок мяса — он её убил.
+	В землю закопал и на могиле написал:
+		"У попа была собака. Он её любил.
+		Она съела кусок мяса — он её убил.
+		В землю закопал и на могиле написал:
+			"У попа была собака....
+И так до бесконечности. Несчастная собака... Несчастный поп...
+Но такова жестокая суть рекурсии.
-==== 3. Задача о золотом сечении ====
+====2. Вычисление факториала====
-Чтобы точно вычислить значение //золотого сечения//, нам необходимо знать, как создать //непредельный ряд// с основанием "1" ((Непредельный ряд с основанием «1» хорошо известен из задачи Фибоначчи «О кроликах», предельный ряд с основанием «0» известен всем программистам — это классический двоичный ряд «0 1 2 4 8 16 32…». Мало кто знает, что таких рядов множество, и чем выше индекс непредельного ряда — тем больше избыточность такой позиционной системы счисления. И тем более она помехоустойчива. Всем известно, что чем сложнее система — тем выше вероятность отказа. С непредельными позиционными системами счисления — всё с точностью наоборот: чем крупнее система, тем выше надёжность. Это очень необычное свойство.)) . В целом, этот метод известен. Достаточно взять сумму двух предыдущих членов ряда, чтобы получить третий. А вот чтобы найти саму //золотую пропорцию// — необходимо разделить последующий член пропорции, на предыдущий. И здесь есть интересная особенность: чем выше номера членов — тем точнее пропорция.
+Для расчёта [[https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB|факториала]] можно пойти родственным путём, что и в прошлом примере, но //рекурсивным// он уже не будет((Вообще, вычисление в настоящем случае факториала через [[https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F|рекурсию]] — довольно //неэффективный// алгоритм. Надо стараться искать обходные пути. Вообще с рекурсией надо быть очень внимательным, так как //неограниченная// рекурсия мгновенно вызовет переполнение стека. На этом принципе работают чуть ли не половина вирусов для **MS Windows**. Можно отдельно почитать статью с множеством технических подробностей на http://codenet.ru/.)). В **КП** рекурсия разрешена и выполняется процедурой при вызове самой себя (прямо или косвенно). Важно понимать, что серия рекурсивных вызовов никогда не закончится, если не установить ограничитель. При вычислении факториала таким ограничителем служит число, по отношению к которому вычисляется факториал. Очень важно помнить, что факториал растёт //чудовищно// быстро, и чтобы избежать ошибки переполнения, это число не должно быть большим. Ниже, пример рекурсивного вычисления факториала на **КП**.
-Итак, нам потребуется три переменных. Две хранят предыдущее значение двух членов //ряда Фибоначчи//, одна — последующее. Также нам потребуется переменная, которая будет отвечать за счётчик цикла. И, собственно, сам цикл.
+  Hello11.odc
-	Hello10.odc:
 <code=oberon2>
-MODULE TestHello10;
+MODULE TestHello11;
 	(* это программа на языке
 	Компонентный Паскаль. Она показывает
-	как можно найти точную золотую пропорцию. *)
+	как можно вычислить произвольный факториал рекурсией. *)
-	IMPORT Log,
+	IMPORT мВв := In,
-		мМат := Math;
+		мЛог := Log;
+	PROCEDURE Факт_Получ (пцФактор: INTEGER): INTEGER;
+	BEGIN
+		IF пцФактор = 1 THEN
+			мЛог.String('Достигнуто дно  '); мЛог.Ln;
+			RETURN 1
+		ELSE
+			мЛог.String('пцФактор='); мЛог.Int(пцФактор); мЛог.Ln;
+			RETURN пцФактор * Факт_Получ(пцФактор - 1);
+		END;
+	END Факт_Получ;
 	PROCEDURE Старт*;
 		VAR
-			цРез0, цРез1, цРез: LONGINT;
+			цФактор: INTEGER; (* факториал *)
-			цИтер: INTEGER;
+			цБаза: INTEGER; (* основание факториала *)
 	BEGIN
-		цРез0 := 0;
+		мЛог.String('Введите основание факториала: ');
-		цРез1 := 1;
+		мВв.Open;
-		цИтер:= 1;
+		мВв.Int(цБаза); мЛог.Ln;
-		WHILE цИтер < 40 DO
+		мЛог.String('BEGIN цБаза='); мЛог.Int(цБаза); мЛог.Ln;
-			цРез := цРез0 + цРез1;
+		цФактор := Факт_Получ(цБаза);
-			Log.Int(цИтер); Log.String(' * '); Log.Real(цРез / цРез1); Log.Ln;
+		мЛог.String('f('); мЛог.Int(цБаза); мЛог.String(')= '); мЛог.Int(цФактор); мЛог.Ln;
-			цРез0 := цРез1;
-			цРез1 := цРез;
-			INC(цИтер)
-		END;
 	END Старт;
 BEGIN
-END TestHello10.
+END TestHello11.
-^TestHello10.Старт
+"6" выделить перед пуском!!!
+^TestHello11.Старт 6
 </code>
-В программе применён простейший метод обмена данными: вычисляется новый член ряда, находится новое значение золотой пропорции, а затем старым членам присваивается новое значение из найденного нового члена.
+Обратите внимание, что в этом примере можно было использовать только одну переменную для вычисления факториала, если бы вывод в ''мЛог.Int(цФактор)'' выполнялся через вызов ''мЛог.Int(Фактор_Получ(пцФактор))''. Соответственно, строку выше можно было бы удалить и отказаться от объявления переменной "пцФактор".
-А теперь посмотрим на вывод программы:
+Вывод программы представлен ниже:
-  компилируется "TestHello10"   168   0
+  компилируется "TestHello11"   220   0
-  старый модуль TestHello10 выгружен
+  Введите основание факториала:
-*  1.0
+  BEGIN цБаза= 6
-*  2.0
+  пцФактор= 6
-*  1.5
+  пцФактор= 5
-*  1.666666666666667
+  пцФактор= 4
-*  1.6
+  пцФактор= 3
-*  1.625
+  пцФактор= 2
-*  1.615384615384615
+  Достигнуто дно
-*  1.619047619047619
+  f( 6)=  720
-*  1.617647058823529
-*  1.618181818181818
+Как видно из вывода переменная ''цБаза'' с каждым вызовом действительно уменьшалась на "1", и это была настоящая ''рекурсия''. :-)
-*  1.617977528089888
-*  1.618055555555556
-*  1.618025751072961
-*  1.618037135278515
-*  1.618032786885246
-*  1.618034447821682
-*  1.618033813400125
-*  1.618034055727554
-*  1.618033963166706
-*  1.618033998521803
-*  1.618033985017358
-*  1.618033990175597
-*  1.618033988205325
-*  1.618033988957902
-*  1.618033988670443
-*  1.618033988780243
-*  1.618033988738303
-*  1.618033988754322
-*  1.618033988748204
-*  1.618033988750541
-*  1.618033988749648
-*  1.618033988749989
-*  1.618033988749859
-*  1.618033988749909
-*  1.61803398874989
-*  1.618033988749897
-*  1.618033988749894
-*  1.618033988749895
-*  1.618033988749895
-Обратите внимание на интересную закономерность: нечётный результат — //меньше// золотой пропорции, чётный — //больше//. Следующая пара повторяет эту закономерность, но уже гораздо ближе к истинной золотой пропорции. И каждый шаг приближает вычисления к ней ((Точное значение числа золотой пропорции установить невозможно — это число иррационально (не имеет конца). С помощью классического двоичного ряда можно получить только число «2». Кроме того, ряды золотой пропорции обладают признаками чётности (если их представлять двоичным кодом). Такое свойство непредельных позиционных систем счисления позволяет проектировать компьютеры с автоматическим частично-гарантированным исправлением одиночных и множественных ошибок. У классического двоичного ряда — такое невозможно. Вообще. Это вообще очень большая и интересная тема.)).
-На шаге 38 и 39 эти числа уже равны. И здесь нет ошибки: сказывается// недостаточная точность// вычислений с плавающей запятой. В примере использован цикл WHILE и это не оптимальное решение. Требуется вручную контролировать переменную "i". В качестве самостоятельного задания, предлагается переписать этот цикл использую FOR. [↑]

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

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

Различия

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