0

我被分配了一个项目来确定数字的平方根，而无需使用除法或 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

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

我会很感激你们能给我的任何建议。感谢您的时间。

4

1 回答 1

0

条件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;
于 2016-06-02T00:34:37.677 回答