B2147 求 f(x,n)

· · 题解

Content

求给定 x,n，求 f(x,n)=\sqrt{n+\sqrt{(n-1)+\sqrt{(n-2)+\sqrt{\dots+2+\sqrt{1+x}}}}} 的值。

Solution

乍一看这题目很烦人，其实，如果我们可以转换一下，这道题目就很简单。

我们不妨算下：

\begin{aligned}f(x,1)&=\sqrt{1+x}\\f(x,2)&=\sqrt{2+\sqrt{1+x}}=\sqrt{2+f(x,1)}\\f(x,3)&=\sqrt{3+\sqrt{2+\sqrt{1+x}}}=\sqrt{3+f(x,2)}=\sqrt{3+\sqrt{2+f(x,1)}}\\&\vdots\end{aligned}

然后我们可以发现，f(x,n) 是一个层层包含的递归关系：如果 n=1，那么 f(x,n)=\sqrt{1+x}，否则，f(x,n)=\sqrt{n+f(x,n-1)}，于是就这么样递归下去然后向上累加答案，足够通过本题。

然而，如果 n 的范围很大，递归的层数很多，我们如果还用递归的话就会内存爆炸，那么怎么办呢？我们考虑把它转为一个递推公式：

f_{x,n}=\begin{cases}\sqrt{1+x}&n=1\\\sqrt{n+f_{x,n-1}}&n>1\end{cases}

然后你就可以明白了，这不就可以用数组直接循环递推出来就可以了吗？你可能发现了第一维的 x，然后你注意到题目中 x 是个实数，那么就不能够以它作为数组的第一维，那么怎么办？我们又发现，n>1 时，f_{x,n} 只和 n 和 f_{x,n-1} 有关，并不和 x 有关。所以我们考虑直接将第一维省去，得到：

f_n=\begin{cases}\sqrt{1+x}&n=1\\\sqrt{n+f_{n-1}} &n>1\end{cases}

然后你就可以用递推通过本题了。

Code

1 递归

#include <cstdio>
#include <cmath>
using namespace std;

inline double f(double x, int n) {
    if(n > 1) return sqrt(n + f(x, n - 1));
    else return sqrt(1 + x);
}

int main() {
    double x; scanf("%lf", &x);
    int n; scanf("%d", &n);
    return printf("%.2lf", f(x, n)), 0;
}

2 递推

#include <cstdio>
#include <cmath>
using namespace std;

int main() {
    double x; scanf("%lf", &x);
    int n; scanf("%d", &n);
    double f[10007] = {0.0}; f[1] = sqrt(1 + x);
    F(int, i, 2, n) f[i] = sqrt(i + f[i - 1]);
    return printf("%.2lf", f[n]), 0;
}