什么是斐波那契数列?
摘自《维基百科》
斐波那契数列(意大利语: Successione di Fibonacci), 又译为菲波拿契数列, 菲波那西数列, 斐波那契数列, 黄金分割数列.
在数学 https://zh.wikipedia.org/wiki/數學 上, 费波那契数列是以递归 https://zh.wikipedia.org/wiki/递归 的方法来定义: F(1)=1,F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)(n>=4,n∈N*)
用文字来说, 就是费波那契数列由 0 和 1 开始, 之后的费波那契系数就是由之前的两数相加而得出. 首几个费波那契系数是: https://zh.wikipedia.org/wiki/0 , https://zh.wikipedia.org/wiki/1 , https://zh.wikipedia.org/wiki/1 , https://zh.wikipedia.org/wiki/2 , https://zh.wikipedia.org/wiki/3 , https://zh.wikipedia.org/wiki/5 , https://zh.wikipedia.org/wiki/8 , https://zh.wikipedia.org/wiki/13 , https://zh.wikipedia.org/wiki/21 , https://zh.wikipedia.org/wiki/34 , https://zh.wikipedia.org/wiki/55 , https://zh.wikipedia.org/wiki/89 , https://zh.wikipedia.org/wiki/144 , https://zh.wikipedia.org/wiki/233 ......
摘自《百度百科》
斐波那契数列 (Fibonacci sequence), 又称黄金分割数列, 因数学家列昂纳多. 斐波那契(Leonardoda Fibonacci) 以兔子繁殖为例子而引入, 故又称为 "兔子数列", 指的是这样一个数列: 1,1,2,3,5,8,13,21,34,...... 在数学上, 斐波纳契数列以如下被以递推的方法定义: F(1)=1,F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)(n>=4,n∈N*)在现代物理, 准晶体结构, 化学等领域, 斐波纳契数列都有直接的应用, 为此, 美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志, 用于专门刊载这方面的研究成果.
定义:
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........
这个数列从第 3 项开始, 每一项都等于前两项之和.
斐波那契数列 https://baike.baidu.com/item/数列 的定义者, 是意大利数学家列昂纳多. 斐波那契 (Leonardo Fibonacci), 生于公元 1170 年, 卒于 1250 年, 籍贯是比萨 https://baike.baidu.com/item/比萨 . 他被人称作 "比萨的列昂纳多".1202 年, 他撰写了《算盘全书》(Liber Abacci) 一书. 他是第一个研究了印度和阿拉伯数学理论的欧洲人. 他的父亲被比萨的一家商业团体聘任为外交领事, 派驻地点相当于今日的阿尔及利亚地区, 列昂纳多因此得以在一个阿拉伯老师的指导下研究数学. 他还曾在埃及 https://baike.baidu.com/item/埃及 , 叙利亚, 希腊, 西西里和普罗旺斯等地研究数学.
看了这么多简介之后, 其实说的简单点斐波那契数列就是一系列数字, 从第三项开始当前项等于前两项之和. 下面我用 OC 给出斐波那契数列
第一种方式:
斐波那契数列递归调用, 指数级增长 2^n. 递归方式效率低, 时间复杂度是指数级的.
- /**
- 斐波那契数列递归调用, 指数级增长 2^n
- */
- - (NSUInteger)Fibonacci:(NSUInteger)n {
- if (n <2) {
- return n;
- }
- else {
- return [self Fibonacci:n-1] + [self Fibonacci:n-2];
- }
- }
第二种方式:
用数组保存之前计算过的结果, 减少大量重复计算, 这样算法复杂度优化为 O(n).
- - (NSUInteger)Fibonacci2:(NSUInteger)n {
- if (n < 2) {
- return n;
- }
- else {
- NSMutableArray *array = [NSMutableArray arrayWithCapacity:n + 1];
- array[0] = @(0);
- array[1] = @(1);
- for (int i = 2; i < array.count; i++) {
- array[i] = @([array[i - 1] unsignedIntegerValue] + [array[i - 2] unsignedIntegerValue]);
- }
- return [array[n] unsignedIntegerValue];
- }
- }
第三种方式:
同样是斐波那契数列, 由于实际只有前两个计算结果有用, 我们可以使用中间变量来存储, 这样就不用创建数组以节省空间. 同样算法复杂度优化为 O(n).
- - (NSUInteger)Fibonacci3:(NSUInteger)n {
- // NSDate *now1 = [NSDate date];
- if (n < 2) {
- return n;
- }
- else {
- NSUInteger a = 0, b = 1;
- for (int i = 1; i < n; i++) {
- b = a + b;
- a = b - a;
- }
- // NSLog(@"fb3 耗时:%lf", [now1 timeIntervalSinceNow]);
- return b;
- }
- }
第四种方式:
通过使用矩阵乘方的算法来优化斐波那契数列算法. 算法的时间复杂度可以优化为 O(log n).
- // 计算二阶矩阵的相乘
- - (NSArray *)multiArrayA:(NSArray *)arrayA arrayB:(NSArray *)arrayB {
- // 定义一个空的二阶矩阵
- NSMutableArray *arrayC = [NSMutableArray arrayWithObjects:@[@0,@0].mutableCopy,@[@0,@0].mutableCopy, nil];
- for (int i = 0; i < 2; i++) {
- for (int j = 0; j < 2; j++) {
- for (int k = 0; k < 2; k++) {
- NSNumber *numA = arrayA[i][k];
- NSNumber *numB = arrayB[k][j];
- NSNumber *numC = arrayC[i][j];
- // 新二阶矩阵的值计算
- numC = @(numC.unsignedIntegerValue + numA.unsignedIntegerValue * numB.unsignedIntegerValue);
- [arrayC[i] replaceObjectAtIndex:j withObject:numC];
- }
- }
- }
- return arrayC;
- }
- - (NSUInteger)Fibonacci4:(NSUInteger)n {
- // NSDate *now2 = [NSDate date];
- // 结果矩阵 最开始的结果矩阵也可以看做是 1, 因为这个矩阵和任意二阶 A 矩阵相乘结果都是 A
- NSArray *arrayA = [NSArray arrayWithObjects:@[@1,@0],@[@0,@1], nil];
- // 元矩阵, 这里可以把元矩阵看做是 2**0=1
- NSArray *arrayB = [NSArray arrayWithObjects:@[@1,@1],@[@1,@0], nil];
- while (n) {
- // 取 n 的二进制的最后一位和 1 做与运算, 如果最后一位是 1, 则进入 if 体内部
- if (n & 1) {
- // 如果在该位置 n 的二进制为 1, 则计算 ans 和 base 矩阵
- arrayA = [self multiArrayA:arrayA arrayB:arrayB];
- }
- // base 矩阵相乘, 相当于初始 base 矩阵的幂 * 2
- arrayB = [self multiArrayA:arrayB arrayB:arrayB];
- // n 的二进制往右移一位
- n>>= 1;
- }
- NSNumber *result = arrayA[0][1]; // 最后获取到的二阶矩阵的 [0][1] 即 f(n)的值
- // NSLog(@"fb4 耗时:%lf", [now2 timeIntervalSinceNow]);
- return result.unsignedIntegerValue;
- }
参考资料
算法之矩阵计算斐波那契数列 https://www.cnblogs.com/huxianglin/p/5995649.html
来源: http://www.jianshu.com/p/6f0f8cc639ff