美妙絕倫的基本算法

Image by Gerd Altmann on Pixabay

在研究和進(jìn)行有關(guān)數(shù)據(jù)處理，計算相關(guān)計算機(jī)或數(shù)學(xué)運(yùn)算的研究時，我們遇到了很多算法。 即使有時候我們不太喜歡數(shù)學(xué)，但我們肯定還是被一些自然而然地整理出來的東西所包圍，甚至都不知道。

最有趣的事情之一是弄清楚斐波那契數(shù)列如何工作。 這些序列在日常生活中經(jīng)常出現(xiàn)：花朵上的花瓣數(shù)，向日葵上的螺旋數(shù)等。

Image by Pxfuel

編碼時，我們將使用許多不同的算法。 盡管有大量的遞歸，分治，隨機(jī)化和暴力算法，但最有用的算法之一就是遞歸算法

那么究竟什么是算法？

首先，算法是解決問題需要遵循的一組任務(wù)。 算法的運(yùn)行時間是完成這些任務(wù)所需的總步數(shù)（或者稱為CS中的BigO表示法，它描述算法的性能）。

那么什么是遞歸，遞歸函數(shù)如何工作？

Image by TORLEY on Flickr

遞歸是指某事在調(diào)用自己本身或?qū)⑵涿枋鰹樽砸米陨?，直到條件為真并停止。

遞歸函數(shù)是在執(zhí)行過程中調(diào)用自身的函數(shù)，也稱為直接遞歸。 與此相反的是，當(dāng)兩個函數(shù)相互調(diào)用時-稱為間接遞歸。

我們?nèi)绾斡嬎沆巢瞧鯏?shù)列，為什么知道它很重要？

對于那些不熟悉編程的人來說，它無疑會幫助您了解如何以及何時使用遞歸或迭代函數(shù)。

對于數(shù)學(xué)家來說，該序列可幫助他們從微分方程開始時更批判性地思考并發(fā)展其邏輯。

斐波那契的數(shù)學(xué)公式

斐波那契數(shù)列的工作方式是，序列中的每個數(shù)字都是其前兩個數(shù)字的和。

對于n = 0，我們有F0 = 0，對于n = 1，我們有F1 = 1。 記住，我們總是有序列的前兩個值。 我們的工作是弄清楚序列的其余部分是如何生成的以及我們要檢查的n值的結(jié)果是什么。 所以我們總是從n> 1開始。

斐波那契數(shù)列的計算公式如下：

計算n = 6的斐波那契的步驟：

n = 0 => F0 = 0n = 1 => F1 = 1n = 2，而n> 1 => F2 = F2-1 + F2-2 = F1 + F0 = 1 + 0 = 1n = 3 => F3 = F3-1 + F3-2 = F2 + F1 = 1 + 1 = 2n = 4 => F4 = F4-1 + F4-2 = F3 + F2 = 2 + 1 = 3n = 5 => F5 = F4 + F3 = 3 + 2 = 5n = 6 => F6 = F5 + F4 = 5 + 3 = 8 依此類推n> 1

那么，如果對斐波那契數(shù)進(jìn)行平方運(yùn)算會發(fā)生什么呢？

結(jié)果不是斐波那契數(shù)，但它們被我們匯總在一起的值所掩蓋。 這讓我們開始思考：實(shí)際上，幾乎每個和都是斐波那契數(shù)列的一部分。

讓我們檢查一下金色矩形，看看斐波那契數(shù)字是如何工作的。

我們都知道 ：

矩形的面積= b x h => b底和h高度

那么，如果我們將上述平方數(shù)相加會發(fā)生什么？

再一次，我們有一些斐波那契數(shù)。

如果我們按順序?qū)⑤^大的數(shù)字除以較小的數(shù)字，例如：

13/8 = 1.625,21 / 13 = 1.615,34 / 21 = 1.619，55/34 = 1.6176,89 / 55 = 1.61818…

這也稱為黃金分割率或1.618022。 所劃分的數(shù)字越大，我們越接近黃金分割率的值。

這是一個計算斐波納契數(shù)列的JavaScript代碼。 時間復(fù)雜度是線性的，因?yàn)檠h(huán)從2到n。 它運(yùn)行時間為O（n）。

（本文翻譯自Amra Sezairi的文章《The Beauty of the Fibonacci Sequence》）