算法分析之猴子吃桃

猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个；第二天早上又将剩下的桃子吃掉一半，又多吃了一个；以此往后，到第十天早上想再吃时，就只剩一个桃子了。求第一天共摘了多少个桃子？

 

递推关系：

f(n)=f(n-1)/2 -1

f(n-1)=(f(n)+1)*2

边界条件: f(10)=1

 

#include <iostream>
using namespace std;
int func(int day){
    if(day==10)
        return 1; 
    else
        return (func(day+1)+1)*2; 
}
int main(){
    cout<<"第一天有%d个桃子！"<<func(1)<<endl;
    return 0;

}