斐波那契，黄金分割与记忆

让我们首先定义将在本文中探讨的两个关键主题：

首先， 斐波那契数列是一系列数字 给定数字的方法是将其前面的两个数字相加。 该序列揭示了有关宇宙深层定律的某些东西，因此它出现在自然界的许多地方，包括诸如植物和动物之类的东西以及诸如星系的螺旋形之类的东西。 因为在这些地方都可以找到它，所以它已经成为物理学家，数学家和程序员一样着迷的话题。

其次， 记忆化是由Donald Michie （人工智能领域的一位真正有趣的英国思想家）创造的术语（或单词），它是一个编程术语，它意味着存储可能需要花费时间或空间的函数调用结果。运行，并在多次出现相同的输入时返回缓存的结果。

在本文中，我将首先描述斐波那契数列是什么以及在何处找到它。 其次，我将探讨斐波那契数列与黄金比率之间的联系。 最后，我们将研究Michie教授的备忘技术如何帮助我们更快地找到斐波那契数列中出现的第N个数字。 最后，我将讨论一些地方，在这些地方我们可以使用序列的知识来理解其他事物。

介绍

斐波那契是意大利人，出生于1175年，一直活到1250年-他为西方数学做出了重要贡献。 尽管他的名字与我们的话题同义，但他并不是第一个发现“斐波那契”数列的人，因为该知识似乎已经在意大利数学中广为人知。 该概念的较早知识显然是在梵文韵律中编码的 显然在斐波那契之前很多年在印度享有盛名。 确实是维拉哈卡（Virahaṅka） 与斐波那契数列的第一个已知描述（来源：E）有关，这位公元6世纪印度数学家对梵语韵律的长音节和短音节的分析反映了这一自然数值序列。

但实际上是在斐波那契的著作Liber Abaci（1202）中 ，他描述了给定兔子种群（在理想条件下）的生长将如何符合这种特定的自然序列。

让我们看一下斐波那契数列：这是斐波那契注意到在整个自然中重复出现的数字序列，因此他着手描述。 该序列如下所示：

  1，1，2，3，5，8，13，21，34 ... 

等等。 像这样用数学描述：

上面的等式在数学上描述了斐波纳契数列（X 1）中的第N个数等于其在数列（X 1）中的后一位，再加上在数列（X 2）中的后两位。 但是，重要的是，我们还必须在上述方程式中添加几个限定条件 ，并注意， 如果n == 1或n == 2，则Xₙ= 1。

此外，如果使用序列的“现代版本”（如我们现在经常使用的）并从0开始，则如果n == 1，则 Xₙ = 0，如果n == 2，则 Xₙ = 1。

注意：现代版本的斐波那契（实际上是相同的序列，但起点不同，始于0）将如下所示：

  0、1、1、2、3、5、8、13、21、34 ... 

用代码描述斐波那契数列

蟒蛇

以下是在斐波那契数列中查找数字的幼稚或蛮力方法 ：

但是，上述计算n的斐波那契数的方法的问题在于，随着n趋于无穷大，它的Big-O时间复杂度呈指数关系，特别是O（ 2ⁿ ） ，将给我们带来问题。它是递归的，但不缓存。 要进一步了解这意味着什么，请参阅我关于Big-O符号的文章。

这是一种非常低效的方法，其原因是它重复了相同的计算，而不是存储或缓存那些已经计算出的值。

记忆化

为了提供更好的解决方案，我们现在转向缓存先前处理过的东西（或缓存来自函数调用的返回值）的技术，这是我们在本文引言中提到的技术： memoization 。

这是我们应该用来优化这种递归算法的技术，因此，它实际上在许多编码方案中非常有用（不仅限于fib数）。

要显式使用此备注，我们可以执行以下操作：

如果安装了Python 3 ，则可以使用functools库中预编写的lru_cache为我们执行此操作，并使我们的代码更简洁 ：

在Swift中，我们可以使用Dictionary（哈希表）执行以下操作：

实施了备忘录的Fibonacci算法的时间复杂度变为O（n） ，因为我们已经存储或缓存了先前的值，因此对于n = 90而不是n = 30不再进行任何计算。

这与黄金分割率有何关系？ 好了，要回答这个问题，让我们看一些python代码，通过将给定的斐波那契数除以斐波那契序列中的前一个数，可以找到所找到的分数。

如果我们运行此代码，输出将是：

从上面的输出中我们可以看到，随着n的大小增加，输出的数字将开始朝着黄金分割率发展，在matlab生成的图上，它看起来像这样：

黄金分割率或Φ

大约= 1.618033988749895

现在让我们看一下所谓的黄金分割率：黄金分割率实际上与斐波那契数列中的一个数字与其序列中前一个数字的比率相同。 比率的用途多种多样：艺术家已将其用于制作精美的东西（我们在莱昂纳多·达·芬奇的作品中看到了这一点）。 我们还可以进一步探究并探索所谓的“ 神圣 几何学” （一个将符号和神圣含义赋予某些几何形状和比例的概念）的主题。 因此，我们还可以看到黄金比例在诸如约柜，吉萨大金字塔或几乎所有主要建筑物之类的物体和结构中的比例。

下图显示了如何以图形方式表示黄金分割率。

随着艺术家和建筑师了解比例，他们想出了一些工具来帮助他们在工作中使用这种神圣的几何形状。 下图所示为基本的木制物体或工具，此工具为一个示例：画家在绘画或在纸或羊皮纸上制作东西时可以使用该比例。 您还可以使用下面的工具环游世界，并发现我们每天遇到的物体，世界各地以及整个宇宙中存在该比率。 该工具的图片旁边是帕台农神庙的图片，上面有图形化的叠加层，显示了如何使用该比例。

比内公式

因为我们知道斐波那契数与该序列中前一个数字的比率将开始接近黄金比率 ，所以我们可以通过查看方法来对n的给定斐波那契数进行反向工程，方法是仅查看位于序列。 为此，我们可以使用Binet公式。

但是，从编码角度来看，值得注意的是，尽管在编程语言中使用此方法可能会由于舍入误差而导致舍入误差，而舍入误差是无理数平方根为5的浮点近似值（Ref＃：H）。 为了更接近精度，我们需要在代码中使用任意精度浮点算法。

或等效地：

在Swift中，这种方法看起来像这样（仅限于Int数据类型的容量）：

斐波那契数列和黄金分割的用途

我们对斐波那契数列和黄金分割率的了解怎么办？ 嗯，除了有趣之外，我们还可以看到这些模式出现在诸如市场之类的市场中，在这些市场中了解这些模式以及其他模式可以帮助我们预测数字趋势。

具体来说，我们可以查看特定股票的支撑位和阻力位 ，趋势变化和价格目标（参考编号：F）。 还有一种叫作Elliott波动理论的东西，它是关于人类心理如何影响像拍拍一样的波动股票的想法。 与斐波那契模式密切相关的专利，显然“从业者通常使用该比率和相关比率来为市场浪潮建立支撑和阻力水平”，尽管尚不清楚该技术的确切功效（参考编号：F） 。

在软件开发领域，我们看到在“ Planning Poker”之类的东西中使用了fib编号，其中，卡以fib顺序出现，每张卡都有一个此类编号。

确实，序列和比率实际上还有更多的出现和应用，但是在这篇文章的背景下要介绍两个，例如比率与宇宙的这么多常数和结构的联系方式以及它的二元性质（参考编号：J）。

结论

总之，在本文中，我们探索了斐波那契数列，我们看到了如何将其编码到我们宇宙的基本定律中。

我们已经探索了编写基本的计算机程序来查找斐波那契序列中的第N个数字的方法是多么容易，但是随后我们看到了使用记忆化是实现良好算法效率的关键。 我们认识到，备忘录可用于许多其他情况，例如检索存储的设置或我们为应用程序存储的UI字符串（可能会被多次访问）。

另外，我们知道可以通过用斐波纳契数列中的数字除以该序列中的先前数来计算黄金分割率。 从中我们还发现，存在一种使用Binet公式获得n的斐波那契数的公式方法 ，该方法可以替代其他方法，因为它被认为是找到第N个斐波那契数的有效方法（尽管此方法可以由于舍入错误而变得不准确，因为无理数的浮点逻辑近似值等于5的平方根）。

参考文献

答： Socratica。 （2018）。 递归，斐波那契数列和备忘 Python教程|| 学习Python编程 。 取自：https：//www.youtube.com/watch？v = Qk0zUZW-U_M [于2018年2月27日访问]。

B： “ https://www.youtube.com/watch?v=dREpRHgkjsg”

C： https ： //medium.com/@mvxlr/swift-memoize-walk-through-c5224a558194

D： https ： //marcosantadev.com/implement-cache-lru-swift/

E：辛格（1985）。 古代和中世纪印度的所谓斐波那契数。 Mathematica历史 ，12（3），p。 229–244。

传真： http ： //math.bu.edu/people/kost/teaching/MA341/Brendan.pdf

G： https ： //artofproblemsolving.com/wiki/index.php？title = Binet％27s_Formula

高： https ： //www.youtube.com/watch？v = Es4Tk0nU1OQ

E： https : //www.goldennumber.net/leonardo-da-vinci-golden-ratio-art/

传真： https ： //www.stocktrader.com/2009/05/26/fibonacci-numbers-investors-sequence-elliot-wave-theory/

G： https ： //proofwiki.org/wiki/Euler-Binet_Formula

H： https ： //gist.github.com/topher6345/001d11fdf21b5f2f969e

我： http : //www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/lucasNbs.html

J： 量子引力：万物的新理论。 从以下位置检索的视频： https : //www.youtube.com/watch?v=_v9eTvlLi-s

最初发布（在wordpress.com上）：2018年2月27日更新：2018年7月20日