洛谷B2147 求 f(x,n)

题目来源

B2147 求 f(x,n) - 洛谷

题目描述

计算 f 的值。

输入格式

输入 x 和 n。

输出格式

函数值，保留两位小数。

输入输出样例

输入 #1

4.2 10

输出 #1

3.68

算法分析

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

我们不妨算下：

f(x,1)f(x,2)f(x,3)​=1+x​=2+1+x​​=2+f(x,1)​=3+2+1+x​​​=3+f(x,2)​=3+2+f(x,1)​​⋮​

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

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

fx,n​={1+x​n+fx,n−1​​​n=1n>1​

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

fn​={1+x​n+fn−1​​​n=1n>1​

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

Code

#include <bits/stdc++.h>
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;int n;scanf("%lf",&x);scanf("%d",&n);return printf("%.2lf",f(x,n)),0;
}