什么是斐波那契数列?
摘自《维基百科》
斐波那契数列（意大利语：Successione di Fibonacci），又译为菲波拿契数列、菲波那西数列、斐波那契数列、黄金分割数列。
在数学上，费波那契数列是以递归的方法来定义：F(1)=1，F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N*）
用文字来说，就是费波那契数列由0和1开始，之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 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项开始，每一项都等于前两项之和。
斐波那契数列的定义者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的列昂纳多”。1202年，他撰写了《算盘全书》（Liber Abacci）一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。
看了这么多简介之后，其实说的简单点斐波那契数列就是一系列数字，从第三项开始当前项等于前两项之和。下面我用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;
}
