自动搬运

查看原文

来自洛谷，原作者为

	王熙文 **

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

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

以下是正文

题意

题目中已经说的很清楚了，需要注意的一点是，不仅答案可能是浮点数，$x$ 也可能是！（这个坑了我很久）

题目要求使用递归求解。

Solution 1

我们观察这个式子，可以把它转化成一个递归（递推）式：

$f(x,1)=\dfrac{x}{1+x},f(x,n)=\dfrac{x}{n+f(x,n-1)}$

因为随着 $n$ 越来越小，肯定会到边界 $f(x,1)$，所以递归可行。

这是递归的代码：

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

double x;

inline double f(int n)
{
    if(n==1) return x/(1+x);
    return x/(n+f(n-1));
}

int main()
{
    int n;
    cin>>x>>n;
    printf("%.2f",f(n));
    return 0;
}

Solution 2

同样，根据上面那个式子，也可以递推。

这是递推的代码：

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

double f[10000010];

int main()
{
    double x;
    int n;
    cin>>x>>n;
    f[1]=x/(1+x);
    for(int i=2; i<=n; ++i) f[i]=x/(i+f[i-1]);
    printf("%.2f",f[n]);
    return 0;
}

Solution 3

同样，这个代码也可以用队列实现。

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

queue<double> q;

int main()
{
    double x;
    int n;
    cin>>x>>n;
    q.push(x/(1+x));
    for(int i=2; i<=n; ++i) q.push(x/(i+q.front())),q.pop();
    printf("%.2f",q.front());
    return 0;

Solution 4

如何优化空间呢？能不能不用定义数组、STL 或使用递归呢？我们可以像求数列之和那样子，每次更新自己。

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

int main()
{
    double x;
    int n;
    cin>>x>>n;
    double f=x/(1+x);
    for(int i=2; i<=n; ++i) f=x/(i+f);
    printf("%.2f",f);
    return 0;
}