二分法的区间

Question

我被分配了一个项目来确定一个数字的平方根而不使用除法或 math.h 库。在做我自己的研究后，我决定使用二分法来解决这个问题。我使用了 Bisection Wikipedia 页面中的伪代码部分：

https://en.wikipedia.org/wiki/Bisection_method#Example:_Finding_the_root_of_a_polynomial

设置算法。

我的代码

#include <iostream>
#include <cmath>
#include <stdlib.h> 

using namespace std;

void __attribute__((weak)) check(double alt_sqrt(double));

//default check function - definition may be changed - will not be graded
void __attribute__((weak)) check(double alt_sqrt(double))
{
    if(alt_sqrt(123456789.0) == sqrt(123456789.0))cout << "PASS\n";
    else cout << "FAIL\n";
    return;
}

//change this definition -  will be graded by a different check function
double my_sqrt(double x)
{
    int i = 0;
    double a = 0.0;         // Lower Bound
    double b = x + 1;       // Upper Bound
    double c = 0.0;         // Guess for square root
    double error = 0.00001;
    double fc = 0.0;
    while(i < 10000)
    {
        c = (a+b)*0.5;
        fc = c * c - x;
        if(abs(fc) < error || (b-a)*0.5 < error)        // Check for solution
        {
            cout << "Square root is: " << c << endl;
            break;
        }
        if(fc < 0)      // Setup new interval
        {
            a = c;
            cout << "a is: " << a << endl;
        }
        else b = c;
        cout << "b is: " << b << endl;
        i++;
    }
    return c;
}

//Do not change this function
int main()
{
    check(my_sqrt);
    return 0;
}

我目前在 main 中获得的教授测试用例的输出是

Square root is: 1.23457e+08
FAIL

正确的输出应该是

Square root is: 11,111.11106
PASS

我认为我设置新间隔的方式出错了。我的想法是，如果两个值之间的差异是负数，那么我需要将下限向上推，如果差异是正数，那么我需要将上限下限。

如果你们能给我任何建议，我将不胜感激。谢谢你的时间。

Answer 1

条件 fb - fa < 0 是错误的，因为忽略浮点错误，fa < fb，即 a * a - x < b * b < x 对于 0 <= a < b.

将始终为真

将条件更改为 fc < 0 提高了准确性，但不幸的是，这种改进无法使程序打印 "PASS"。为了提高程序打印的准确性"PASS"，删除有害的中断部分

    if(abs(fc) < error || (b-a)*0.5 < error)        // Check for solution
    {
        cout << "Square root is: " << c << endl;
        break;
    }

删除这个有害的中断并添加行

cout << "Square root is: " << c << endl;

就在

之前

return c;

给了我

Square root is: 11111.1
PASS

但不幸的是，这不是您想要的。要打印您想要的内容，

#include <iomanip>

应该加上打印部分应该是

std::cout.imbue(std::locale(""));
cout << fixed << setprecision(5) << "Square root is: " << c << endl;

二分法的区间

Interval for bisection method

c++

bisection