P76050 递推的桃子 — 题解

专题： 函数
适用题目： 新生 OJ 本地题包中的 P76050，不要直接用于外站同名题。

解题思路

按照 a[0]=1、a[n]=2(a[n-1]+1) 递归计算；也可以通过循环自底向上计算。

复杂度

时间和递归栈空间 $O(n)$。

易错点

先确定递归终点 n=0，不要把初值误设为 0。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

long long peach(int n){
    if(n==0)return 1;
    return 2*(peach(n-1)+1);
}
int main(void) {
    int n;scanf("%d",&n);printf("%lld\n",peach(n));return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;

long long peach(int n) {
    if (n == 0) return 1;
    return 2 * (peach(n - 1) + 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    cout << peach(n) << '\n';
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。