面試程式設計題-猴子偷桃

近期面試兩次碰到這道題，很有意思，哈哈，是以現在寫下來紀念一下。

題目

一個猴子來到山裡的一棵桃樹下，發現有一堆桃子。第一天它吃掉一個，然後拿走一半，回到家裡，把消息告訴第二個猴子。第二天第二個猴子也來了，又吃掉一個，然後拿走了一半，回到家，告訴第三個猴子。第三個猴子也是吃掉一個，然後拿走了一半。以此類推，第10天，第10個猴子來到時，發現還剩下1個桃子。求第一天總共有多少個桃子。（優先遞歸程式）

分析

這道題要求使用遞歸程式，是以首先要了解遞歸。遞歸就是循環調用自己本身。當然遞歸要有結束條件，不然就是無限循環調用了。

這裡的結束條件就是第10天時，還剩下一顆桃子。

做這些題目，最好多畫圖，多舉例，然後得出規律，最後去驗證規律是否正确。比如以下分析：

從最後一天往前推算，n1,n2,n3,n4,n5......n1表示第n天的桃子數量
天數  桃子數量
天： *n2+
天： *n3+
天： *n4+
天： *n5+
天： *n6+
天： *n7+
天： *n8+
天： *n9+
天： *n10+
天：  
           

推出函數式：

f() = 1
f(n) = 2*f(n+)+1,  n取值範圍[1,10)

           

程式編碼

public class Main {
    public static void main(String[] args) {
        int r = stolenPeach();
        System.out.println(r);
    }

    /**
     * 猴子偷桃問題
     * @param n
     * @return
     */
    public static int stolenPeach(int n){
        if(n == ){
            return ;
        }else{
            return  *stolenPeach(n+) + ;
        }
    }
}
           

輸出結果：1023