IOS 算法(基础篇) ----- 处理斐波那契序列

最近研究一些算法, 入门的就是斐波那契数列

如果你问什么是斐波那契数列?  既然你诚心诚意的发问了,  我就大发慈悲的告诉你!  

斐波那契数列, 又称黄金分割序列 ( 0.0很高大上的名字, 但我始终不太理解为什么又这么称呼 )

即, 给定初始2个值, 第三位起, 每一项位前两位之和

例如:  给定初始值 0, 1 那么,  斐波那契数列为   0, 1, 1, 2, 3, 5, 8, 13, 21, 34......

可以看出其 数学公式 为:

n = 1时   f(n) = 0;  n = 2时   f(n) = 1; 

n >3时  f(n) = f(n-1) + f(n-2)

(注: 留意下, 这里我们采用是数学位,  即第一位为0,  编程久的人喜欢称为第0位 ^-^ )

现在, 我们想实现的是, 用Swift写 斐波那契序列 方法, 并且我任意输入第几位数字, 会给我返回正确结果

且要保证运算最少(这个重点)

拆分下可以看出, 处理斐波 即重点处理   f(n) = f(n-1) + f(n-2),  往下细分

f(n-1) = f(n-2) + f(n-3)

f(n-2) = f(n-3) + f(n-4)

f(n-3) = f(n-4) + f(n-5)

....

f(2) = 1

f(1) = 0

反复调用自身方法, 直到 n= 2, n=1,  这样可以写出

因为输入的都是正整数, 所以用的UInt。 调用下这个方法

结果没错, 但我更关心是执行多少次呢?  增加些打印,  再把输入数字调小一些看看

这次输入 5, 看下结果

调用了9次,  输入6调用15次 , 输入7调用25次......(这个就不截图了>_< )   原因在于每次调用fib1()都需要递归调用fib1(n-1) 和 fib1(n-2)直至 fib1(1)和fib1(2),   即每次对fib1()调用都会额外增加两次fib1()调用, 如果计算个大点的数岂不就完蛋了 !? 

虽然写出了斐波那契数列方法,  但这只是机械式翻译, 显然不是一个合格程序员该选择的, 所以我们要简化斐波那契数列方法。

这里就要用到容器来储存之前计算结果,  减少重复计算, 就像人脑一样, 记忆了第5位为3, 第6位为5, 很容易计算出第7位为8,  第8位为13

那么定义三个容器  a = f(n - 2); b = f(n - 1); c;  增加1位则令 c = a + b, a = b, b = c, 此时b就是输出的值, 再增加就是重复之前操作即循环,  为了增加可读性, 我这里分别用 last, next, add 代表a, b, c   那么可以写出

还是输入8, 我们看下

方法调用只有6次, 输入9用7次, 这样就写出简化的斐波那契数列

当然还有更优的方法 ^_^,  for循环主体使用元组, 增加代码间接性