IOS|IOS 算法(基础篇) ----- 处理斐波那契序列
最近研究一些算法, 入门的就是斐波那契数列
如果你问什么是斐波那契数列?既然你诚心诚意的发问了,我就大发慈悲的告诉你!
斐波那契数列, 又称黄金分割序列 ( 0.0很高大上的名字, 但我始终不太理解为什么又这么称呼 )
即, 给定初始2个值, 第三位起, 每一项位前两位之和
例如:给定初始值 0, 1 那么,斐波那契数列为0, 1, 1, 2, 3, 5, 8, 13, 21, 34......
可以看出其 数学公式 为:
【IOS|IOS 算法(基础篇) ----- 处理斐波那契序列】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循环主体使用元组, 增加代码间接性
文章图片
推荐阅读
- 2020-04-07vue中Axios的封装和API接口的管理
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- iOS中的Block
- Python基础|Python基础 - 练习1
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- Java|Java基础——数组
- 记录iOS生成分享图片的一些问题，根据UIView生成固定尺寸的分享图片
- 《算法》-图[有向图]