?

? ? ? ? 猴子第一天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不過(guò)癮就多吃了一個(gè)。第二天早上又將剩下的桃子吃了一半，還是不過(guò)癮又多

吃了一個(gè)。以后每天都吃前一天剩下的一半再加一個(gè)。到第10天剛好剩一個(gè)。問(wèn)猴子第一天摘了多少個(gè)桃子？

?

分析: 這是一套非常經(jīng)典的算法題，這個(gè)題目體現(xiàn)了算法思想中的遞推思想，遞歸有兩種形式，順推和逆推，針對(duì)遞推，只要

? ? ? ? 我們找到遞推公式，問(wèn)題就迎刃而解了。

? ? ? ? ? ? ? ?令S₁₀=1，容易看出?S9=2(S10+1)，?簡(jiǎn)化一下?

? ? ? ? ? ? ? ? ?S₉=2S₁₀+2

? ? ? ? ? ? ? ? ?S₈=2S₉+2

? ? ? ? ? ? ? ? ? ? ?.....

? ? ? ? ? ? ? ? ?S_n=2S_n+1+2

?

遙想公瑾當(dāng)年，老師說(shuō)遞歸是最簡(jiǎn)潔，最容易理解的，好，就用遞歸試一下：

1 class Program 2 { 3 static void Main(string[] args) 4 { 5 int sum = SumPeach(1); 6 7 Console.WriteLine("第一天摘得桃子有:{0}", sum); 8 9 Console.Read(); 10 } 11 12 //遞歸 13 static int SumPeach(int day) 14 { 15 if (day == 10) 16 return 1; 17 18 return 2 * SumPeach(day + 1) + 2; 19 } 20 }

?

當(dāng)我們玩轉(zhuǎn)遞歸的時(shí)候，老師說(shuō)線性遞歸會(huì)將“變量，參數(shù)，返回值”在“遞”的過(guò)程中壓棧，如果遲遲“遞”不到頭的話，棧就會(huì)越積越多，

最后就爆掉了，window中系統(tǒng)默認(rèn)的堆棧空間是1M。

那么解決方法是什么？ 尾遞歸，下面我們繼續(xù)上代碼：

1 class Program 2 { 3 static void Main(string[] args) 4 { 5 int sum = SumPeachTail(1, 1); 6 7 Console.WriteLine("第一天摘得桃子有:{0}", sum); 8 9 Console.Read(); 10 } 11 12 //尾遞歸 13 static int SumPeachTail(int day, int total) 14 { 15 if (day == 10) 16 return total; 17 18 //將當(dāng)前的值計(jì)算出傳遞給下一層 19 return SumPeachTail(day + 1, 2 * total + 2); 20 } 21 }

?

那么兩種遞歸有什么區(qū)別呢？上圖說(shuō)話。

?

從圖中我們可以清晰的看到“線性遞歸”和“尾遞歸”的區(qū)別，那到底有什么本質(zhì)區(qū)別呢？尾遞歸中在每次向下遞歸的過(guò)程中，都會(huì)將當(dāng)前

層的結(jié)果計(jì)算出來(lái)后向下一層傳遞，從理論上說(shuō)，傳到下一層后，上一層的參數(shù)值已經(jīng)沒(méi)有存在的必要了，可以清除上一層中的變量占

用的棧空間，那么最終達(dá)到的效果就是永遠(yuǎn)不會(huì)出現(xiàn)StackOverflowException了，但實(shí)際上是否真有這個(gè)效果，得要看編譯程序是否

真的給你優(yōu)化了。

下面我們將day=10改成day=int.MaxValue，跑一下程序看看：

很可惜，有圖有真相，拋出異常了，當(dāng)然我是菜鳥(niǎo)，早已看不懂匯編了，大家也可以討論討論，目前我個(gè)人認(rèn)為C#編譯器沒(méi)有給

我做這個(gè)優(yōu)化:-D。

?

下一步我們就要計(jì)算一下這個(gè)遞歸的時(shí)間復(fù)雜度是多少，關(guān)于求“遞歸”的時(shí)間復(fù)雜度主要有三種：

1. ?代換法。

2. ?遞歸樹(shù)法。

3. ?主定理。

?

這一篇我就說(shuō)下代換法，作法如下

①：猜一下遞歸式復(fù)雜度的上界或者下界。

②：用數(shù)學(xué)歸納法證明你的復(fù)雜度是正確的。

?

為了具有通用性，我們將“猴子吃桃”的問(wèn)題反過(guò)來(lái)寫(xiě)，也就是已知S1，求S10，當(dāng)然原理是一樣的，通用公式就有如下形式：

? ? ? ? ? ? ? ? ?T_n=2T_n-1+2 ? ? ? ? ? ? ① ?

假使 ? ? ? ? ? Tn=O(n) ? ? ? ? ? ? ? ? ? ②

則必定存在一個(gè) c>0的自然數(shù)使

? ? ? ? ? ? ? ? Tn<=cO(n)=cn ? ? ? ? ? ③

③代入①知?

? ? ? ? ? ? ? ? Tn<=2c(n-1)+2=2cn-2c+2

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =cn-c+1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =cn-(c-1)

當(dāng)c>=1時(shí)，則必有?Tn<=cn ?

?

最后得出遞歸式的時(shí)間復(fù)雜度為O(N)。

?

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的经典算法题每日演练——第三题 猴子吃桃的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。