二分算法实例应用（一）

方程求解 （POJ 4140）

Description

求下面方程的根：f(x) = x^3- 5x^2+ 10x - 80 = 0。

Input

-

Output

精确到小数点后9位。

Sample Input

-

Sample Output

5.705085932

算法思想：

对方程f(x)求导，得f'(x)=3x^2-10x+10。其中f'(x)>0恒成立。

故，f(x)为严格单调增函数。由方程易知f(0)<0，且f(100)>0，所以由零点定理可知，在区间[0,100]内有且仅有一个实根。

由于f(x)在[0,100]内是单调的，所以可以用二分法在区间[0,100]中进行根的满足性探索。

代码逻辑：

1. 在C语言中，进行浮点数为0判断时，一般考虑判断该数的绝对值是否小于一个极小值ε，通常ε选10^-6。

   代码如下：

   #define EPS 1e-6

2. 设计求f(x)的值的函数。

   double fun(double x) {
       return pow(x, 3) - 5 * pow(x, 2) + 10 * x - 80;
   }

3. 采用二分法进行解的探索，

   1. 使用left,right变量来记录根的存在区间的左右端点。x取区间中点。
   2. 若f(x)>0则表明x点为更小的右端点，修改右端点为x；反之，若f(x)≤0则表明x为更大的左端点，修改左端点为x；
   3. 再计算当前区间中点的函数值，返回步骤2进行判断。直至找到一个使f(x)=0的根x。

代码整合：

//
// Created by Ss1Two on 2023/2/7.
//

#include "stdio.h"
#include "math.h"

double EPS = 1e-6;//无穷小值Epsilon->ε=10^-10,用于判断浮点数是否为0

double EquationSolving();//线性方程求解函数声明

double fun(double x);//线性方程计算函数声明

int main(void) {
    printf("%.9f\n", EquationSolving());
    return 0;
}


double fun(double x) {
    return pow(x, 3) - 5 * pow(x, 2) + 10 * x - 80;
}

double EquationSolving() {
    //x->自变量，y->函数值，left->解区间左端点，right->解区间右端点
    double x, left = 0, right = 100, y;

    x = left + (right - left) / 2;
    y = fun(x);

    while (fabs(y) > EPS) {
        if (y > 0) {
            right = x;
        } else {
            left = x;
        }
        x = left + (right - left) / 2;
        y = fun(x);
    }
    return x;
}

Created by Ss1Two on 2023/2/7