什么是斐波那契數(shù)列?
摘自《維基百科》
?
斐波那契數(shù)列（意大利語：Successione di Fibonacci）瘩燥，又譯為菲波拿契數(shù)列服猪、菲波那西數(shù)列褂傀、斐波那契數(shù)列、黃金分割數(shù)列您访。
?
在數(shù)學上呻逆，費波那契數(shù)列是以遞歸的方法來定義：F(1)=1，F(xiàn)(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4驰吓，n∈N*）
?
用文字來說，就是費波那契數(shù)列由0和1開始，之后的費波那契系數(shù)就是由之前的兩數(shù)相加而得出辆布。首幾個費波那契系數(shù)是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
摘自《百度百科》
?
斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列茶鉴、因數(shù)學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入锋玲，故又稱為“兔子數(shù)列”，指的是這樣一個數(shù)列：1涵叮、1惭蹂、2、3割粮、5盾碗、8、13穆刻、21置尔、34、……在數(shù)學上氢伟，斐波納契數(shù)列以如下被以遞推的方法定義：F(1)=1榜轿，F(xiàn)(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N*）在現(xiàn)代物理朵锣、準晶體結(jié)構(gòu)谬盐、化學等領(lǐng)域，斐波納契數(shù)列都有直接的應(yīng)用诚些，為此飞傀，美國數(shù)學會從1963年起出版了以《斐波納契數(shù)列季刊》為名的一份數(shù)學雜志，用于專門刊載這方面的研究成果诬烹。
?
定義：
?
斐波那契數(shù)列指的是這樣一個數(shù)列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233砸烦，377，610绞吁，987幢痘，1597，2584家破，4181颜说，6765购岗，10946，17711门粪，28657喊积，46368........
?
這個數(shù)列從第3項開始，每一項都等于前兩項之和玄妈。
?
斐波那契數(shù)列的定義者乾吻，是意大利數(shù)學家列昂納多·斐波那契（Leonardo Fibonacci），生于公元1170年措近，卒于1250年溶弟，籍貫是比薩。他被人稱作“比薩的列昂納多”瞭郑。1202年辜御，他撰寫了《算盤全書》（Liber Abacci）一書。他是第一個研究了印度和阿拉伯數(shù)學理論的歐洲人屈张。他的父親被比薩的一家商業(yè)團體聘任為外交領(lǐng)事擒权，派駐地點相當于今日的阿爾及利亞地區(qū)，列昂納多因此得以在一個阿拉伯老師的指導下研究數(shù)學阁谆。他還曾在埃及碳抄、敘利亞、希臘场绿、西西里和普羅旺斯等地研究數(shù)學剖效。
看了這么多簡介之后，其實說的簡單點斐波那契數(shù)列就是一系列數(shù)字焰盗，從第三項開始當前項等于前兩項之和璧尸。下面我用OC給出斐波那契數(shù)列
第一種方式：
斐波那契數(shù)列遞歸調(diào)用，指數(shù)級增長2^n熬拒。遞歸方式效率低爷光，時間復雜度是指數(shù)級的。
/**
斐波那契數(shù)列遞歸調(diào)用澎粟，指數(shù)級增長2^n
*/
- (NSUInteger)Fibonacci:(NSUInteger)n {
if (n < 2) {
return n;
}
else {
return [self Fibonacci:n-1] + [self Fibonacci:n-2];
}
}
第二種方式：
用數(shù)組保存之前計算過的結(jié)果蛀序，減少大量重復計算，這樣算法復雜度優(yōu)化為 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];
}
}
第三種方式：
同樣是斐波那契數(shù)列徐裸，由于實際只有前兩個計算結(jié)果有用，我們可以使用中間變量來存儲啸盏，這樣就不用創(chuàng)建數(shù)組以節(jié)省空間重贺。同樣算法復雜度優(yōu)化為 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;
}
}
第四種方式：
通過使用矩陣乘方的算法來優(yōu)化斐波那契數(shù)列算法。算法的時間復雜度可以優(yōu)化為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];
// 結(jié)果矩陣 最開始的結(jié)果矩陣也可以看做是1，因為這個矩陣和任意二階A矩陣相乘結(jié)果都是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體內(nèi)部
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;
}
