信息奥赛题单｜浮点数二分

浮点数二分

题单 🧑🏻‍💻

题目来源	题目名称	题目链接	备注	难度
信息奥赛学一本通 - 1241	二分法求函数的零点	链接🔗	浮点数二分	🟢
Acwing - 790	数的三次方根	链接🔗	浮点数二分	🟢
HDU - 2199	Can you solve this equation?	链接🔗	浮点数二分	🟢

---

题解 🚀

二分法求函数的零点

题目信息 📚

【题目名称】信息奥赛学一本通1241 - 二分法求函数的零点

【题目描述】

有函数：$f(x)=x^5−15x^4+85x^3−225x^2+274x−121$

已知 $f(1.5) \gt 0,f(2.4) \lt 0$ 且方程 $f(x)=0$ 在区间 $[1.5,2.4]$ 有且只有一个根，请用二分法求出该根。

【输入】

无

【输出】

该方程在区间 $[1.5,2.4]$中的根。要求四舍五入到小数点后 $6$ 位。

【数据范围】

无

【输入样例】

无

【输出样例】

无

【原题链接】

http://ybt.ssoier.cn:8088/problem_show.php?pid=1241

---

题目解析 🍉

【题目分析】

求 函数零点、数的平方根 等问题是 浮点数二分 一些非常经典的问题，只需要在理解模版的基础上使用模版即可。

🍉 PS：一般题目要求输出 6 位小数，则 l 与 r 的误差取 const double eps = 1e-8，一般会往后两位。

🍉 PS2：慎用 C/C++ 的 pow 函数，有时候会有坑，详见其他博客。

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-8;  //定义误差

double f(double x);  //定义函数

int main() {

    double l = 1.5, r = 2.4;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (f(mid) <= 0) r = mid;   //原函数在 [1.5,2.4] 递减
        else l = mid;
    }

    cout << fixed << setprecision(6) << l << endl;

    return 0;
}

double f(double x) {
    return x * x * x * x * x - 15 * x * x * x * x + 85 * x * x * x - 225 * x * x + 274 * x - 121;
}

---

数的三次方根

题目信息 📚

【题目名称】数的三次方根

【题目描述】

给定一个浮点数 $n$，求它的三次方根。

【输入】

共一行，包含一个浮点数 $n$。

【输出】

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 $6$ 位小数。

【输入样例】

1000.00

【输出样例】

10.000000

【数据范围】

$−10000 \le n \le 10000$

【原题链接】

https://www.acwing.com/problem/content/792/

---

题目解析 🍉

【题目分析】

求 函数零点、数的平方根 等问题是 浮点数二分 一些非常经典的问题，只需要在理解模版的基础上使用模版即可。

🍉 PS：一般题目要求输出 6 位小数，则 l 与 r 的误差取 const double eps=1e-8，一般再往后两位。

🍉 PS2：该题存在负数的情况，需要 重点考虑上下限的划分。

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-8;
const double MAX = 1e5;

double n;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;
    //根据题目范围确定上下限（有负数情况）
    double l = -MAX, r = MAX;

    //浮点数二分模版
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (mid * mid * mid <= n)
            l = mid;
        else
            r = mid;
    }
    cout << fixed << setprecision(6) << l << endl;

    return 0;
}

---

Can you solve this equation?

题目信息 📚

【题目名称】HUD OJ 2199 - Can you solve this equation?

【题目描述】

Now,given the equation $8x^4 + 7x^3 + 2x^2 + 3x + 6 == Y$,can you find its solution between $0$ and $100$;

Now please try your lucky.

【输入】

The first line of the input contains an integer $T(1<=T<=100)$ which means the number of test cases.

Then T lines follow, each line has a real number $Y (fabs(Y) <= 1e10)$;

【输出】

For each test case, you should just output one real number(accurate up to $4$ decimal places),which is the solution of the equation,or “No solution!”,if there is no solution for the equation between $0$ and $100$.

【输入样例】

2
100
-4

【输出样例】

1.6152
No solution!

---

题目解析 🍉

【题目分析】

#include<bits/stdc++.h>

using namespace std;
const double eps = 1e-8;

double y;

double f(double x) {
    return 8 * x * x * x * x + 7 * x * x * x + 2 * x * x + 3 * x + 6;
}

bool check(double k, double y) {
    if (f(k) <= y) return true;
    else return false;
}

// 二分
void solve(double y) {
    // 左右边界
    double l = 0, r = 100;
    // 二分
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid, y)) l = mid;
        else r = mid;
    }
    
    cout << fixed << setprecision(4) << l << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> y;
        if (y > f(100) || y < f(0)) cout << "No solution!" << endl;
        else solve(y);
    }
    return 0;
}