斐波那契數(shù)列之兔子繁殖問題
據(jù)說很多枯燥的算法問題都是和生活密切相關(guān)的，畢竟很多算法都是人們有實際的需求才慢慢進入人們視野的，今天我們就以實際的一個生活中的問題來切入："我們來聊聊兔子繁殖的問題"
一般而言，兔子在出生兩個月后，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，那么一年以后可以繁殖多少對兔子？我們不妨拿新出生的一對小兔子分析一下：
第一個月小兔子沒有繁殖能力，所以還是一對
兩個月后，生下一對小兔對數(shù)共有兩對
三個月以后，老兔子又生下一對，因為小兔子還沒有繁殖能力，所以一共是三對。
這就是通常我們聊斐波那契數(shù)列時談到的兔子問題，可能到現(xiàn)在為止很多沒有接觸過斐波那契數(shù)列概念的朋友依然不知道到底我想要談什么？so，我們還是就上面談到的兔子問題來繼續(xù)深入一下，我們知道了三個月以后一共是三對兔子，那么依次類推我們可以得到下表：
那么我們可以從這個表中觀察到什么呢？
幼仔對數(shù)=前月成兔對數(shù)
成兔對數(shù)=前月成兔對數(shù)+前月幼仔對數(shù)
總體對數(shù)=本月成兔對數(shù)+本月幼仔對數(shù)
斐波那契數(shù)列定義
對于斐波那契數(shù)列1、1、2、3、5、8、13、……。有如下定義
F(n)=F(n-1)+F(n-2)
F(1)=1
F(2)=1
不知道大家看完上面的定義后有什么直覺性的東西呢？反正我一看完我就想到了遞歸，遞歸就是自己調(diào)用自己嘛，好吧，話不多說，我們就先用遞歸來實現(xiàn)以下這個斐波那契數(shù)列吧：
斐波那契數(shù)列遞歸實現(xiàn)
#pragma mark - 斐波那契數(shù)列
#pragma mark -
/**
查找斐波那契數(shù)列中的第n個數(shù)
@param n 斐波那契數(shù)列中的第n個數(shù)
@return 斐波那契數(shù)列中的第n個數(shù)
*/
- (NSInteger)FibSequence:(NSInteger)n {
if (n < 2) {
return n == 0 ? 0 : 1;
}else {
return [self FibSequence:n - 1] + [self FibSequence:n -2];
}
}
看完后怎么樣，是不是非常的簡單？確實它看上去很清晰很簡單。我只想說，看著很舒服，那么如果不用遞歸來實現(xiàn)的話呢？
斐波那契數(shù)列迭代實現(xiàn)
/**
查找斐波那契數(shù)列中的第n個數(shù)
@param n 斐波那契數(shù)列中的第n個數(shù)
@return 斐波那契數(shù)列中的第n個數(shù)
*/
- (NSInteger)FibSequence2:(NSInteger)n {
if (n < 2) {
return n == 0 ? 0 : 1;
}else {
NSInteger a = 0,b = 1,c = 0;
for (int i = 3; i < n - 1; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
看上去是不是也不是很難，我還是來解釋一下吧，畢竟每個人基礎(chǔ)不一樣，迭代實現(xiàn)的思路是這樣的：使用三個變量來分別記錄前兩個數(shù)的值，前一個數(shù)的值，和當(dāng)前數(shù)的值，分別對應(yīng)a、b、c，
默認(rèn)我初始化為了：0、1、0；因為當(dāng)n為0的時候剛好a為0 ，n等于1時b = 1，而c默認(rèn)為0，通過迭代不斷讓c = a + b也就是前兩個數(shù)的和，這樣就實現(xiàn)了，當(dāng)然有什么不懂得可以留言給我，實在不懂的話打上斷點一個一個數(shù)調(diào)試唄，肯定能搞懂了對吧。
