B2148 再求 f(x,n) 题解

王熙文 · 2021-07-03 13:39:17 · 题解

题意

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

题目要求使用递归求解。

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