最近研究一些算法, 入门的就是斐波那契数列
如果你问什么是斐波那契数列? 既然你诚心诚意的发问了, 我就大发慈悲的告诉你!
斐波那契数列, 又称黄金分割序列 ( 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循环主体使用元组, 增加代码间接性
