題目描述

一只小猴買了若干個桃子。第一天他剛好吃了這些桃子的一半，又貪嘴多吃了一個；接下來的每一天它都會吃剩余的桃子的一半外加一個。第 $n$ 天早上起來一看，只剩下 $1$ 個桃子了。請問小猴買了幾個桃子？

輸入格式

輸入一個正整數 $n$，表示天數。

輸出格式

輸出小猴買了多少個桃子。

樣例輸入

4

樣例輸出

22

提示

數據保證，$1\le n\le 20$。

思路分析
遞推公式：f(m) = 2(f(m+1)+1)
遞推邊界：f(n) = 1, n的值通過輸入獲得。

參考代碼-遞歸

#include<bits/stdc++.h>
using namespace std;
int n;
int f(int m)
{if(m==n) return 1;else return 2*(f(m+1)+1);
}
int main() {cin>>n;cout<<f(1);return 0;
}

參考代碼-遞推

#include<bits/stdc++.h>
using namespace std;
int main() {int n;cin >> n;int f = 1; //第n天的時候，只有1個//從第n-1天開始往前推while(--n) {//每天吃剩余桃子的一半，加1個。從后一天往前計算時，要先加上1個，再乘以2f = 2*(f+1);}cout << f;return 0;
}