游记里的孙悟空既贪吃又调皮，一天他从皇母娘娘的蟠桃园摘了一些蟠桃，第一天他刚好吃了这些蟠桃的一半，又贪嘴多吃了一个；接下来的每一天它都会吃剩余的蟠桃的一半外加一个。第 n (n≤20) 天早上起来一看，只剩下 1 个蟠桃了。请小民同学帮助孙悟空计算那天他摘了几个蟠桃？用c++语言写出该程序

#include <stdio.h>

int main() {
    int n, x = 1;
    scanf("%d", &n);
    for (int i = n; i >= 1; i--) {
        x = (x + 1) * 2;
    }
    printf("%d", x);
    return 0;
}

注解：

利用逆推的思路，从第 n 天往前推，一直推到第一天，算出第一天摘了多少个蟠桃。每天吃剩下的是前一天的一半外加一个，也就是说第 i 天剩下的是第 i+1 天的 (i+1)/2+1，即(2i+1)/2=(i+1) 个蟠桃，所以可以用一个循环来倒推每一天剩下的蟠桃数，最终得到第一天摘了多少个蟠桃，即为答案。

时间复杂度：O(n)

空间复杂度：O(1)