自动搬运

查看原文

来自洛谷，原作者为

	Eason_AC Remember? / AFOed on 2022.6.14 / 彻底死咯

搬运于2025-08-24 21:07:44，当前版本为作者最后更新于2021-07-04 19:09:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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;
}