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