經典演算法題每日演練——第三題猴子吃桃

猴子第一天摘下若干個桃子，當即吃了一半，還不過癮就多吃了一個。第二天早上又將剩下的桃子吃了一半，還是不過癮又多
吃了一個。以後每天都吃前一天剩下的一半再加一個。到第 10 天剛好剩一個。問猴子第一天摘了多少個桃子？

分析: 這是一套非常經典的演算法題，這個題目體現了演算法思想中的遞推思想，遞迴有兩種形式，順推和逆推，針對遞推，只要
我們找到遞推公式，問題就迎刃而解了。
令 S10=1，容易看出 S9=2(S10+1)，簡化一下
S9=2S10+2
S8=2S9+2
…..
Sn=2Sn+1+2

遙想公瑾當年，老師説遞迴是最簡潔，最容易理解的，好，就用遞迴試一下：

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 }

當我們玩轉遞迴的時候，老師説線性遞迴會將 “變數，引數，返回值” 在 “遞” 的過程中壓棧，如果遲遲 “遞” 不到頭的話，棧就會越積越多，
最後就爆掉了，window 中系統預設的堆疊空間是 1M 。
那麼解決方法是什麼？尾遞迴，下面我們繼續上程式碼：

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 //將當前的值計算出傳遞給下一層
19 return SumPeachTail(day + 1, 2 * total + 2);
20 }
21 }

那麼兩種遞迴有什麼區別呢？上圖説話。

從圖中我們可以清晰的看到 “線性遞迴” 和 “尾遞迴” 的區別，那到底有什麼本質區別呢？尾遞迴中在每次向下遞迴的過程中，都會將當前
層的結果計算出來後向下一層傳遞，從理論上説，傳到下一層後，上一層的引數值已經沒有存在的必要了，可以清除上一層中的變數佔
用的棧空間，那麼最終達到的效果就是永遠不會出現 StackOverflowException 了，但實際上是否真有這個效果，得要看編譯程式是否
真的給你優化了。
下面我們將 day=10 改成 day=int.MaxValue，跑一下程式看看：

很可惜，有圖有真相，丟擲異常了，當然我是菜鳥，早已看不懂彙編了，大家也可以討論討論，目前我個人認為 C#編譯器沒有給
我做這個優化:-D 。

下一步我們就要計算一下這個遞迴的時間複雜度是多少，關於求 “遞迴” 的時間複雜度主要有三種：
1. 代換法。
2. 遞迴樹法。
3. 主定理。

這一篇我就説下代換法，作法如下
①：猜一下遞迴式複雜度的上界或者下界。
②：用數學歸納法證明你的複雜度是正確的。

為了具有通用性，我們將 “猴子吃桃” 的問題反過來寫，也就是已知 S1，求 S10，當然原理是一樣的，通用公式就有如下形式：
Tn=2Tn-1+2 ①
假使 Tn=O(n) ②
則必定存在一個 c>0 的自然數使
Tn<=cO(n)=cn ③ ③代入①知 Tn<=2c(n-1)+2=2cn-2c+2 =cn-c+1 =cn-(c-1) 當c>=1 時，則必有 Tn<=cn 最後得出遞迴式的時間複雜度為 O(N) 。文章來自互聯網博客網站，原文地址：http://www.cnblogs.com/huangxincheng/archive/2012/08/08/2628022.html

經典演算法題每日演練——第三題 猴子吃桃