0

在阅读SICP关于“用高阶函数形成抽象”的部分时，我很想在 C++ 中使用牛顿法实现一个简单的根求解过程。

但是我的实现是错误的，但我不知道为什么。代码编译但由于堆栈溢出而导致运行时崩溃，因为 fixedPoint 函数内的循环递归无法达到 MAX_IT。我在调试模式下运行它，所以尾递归不适用。

问题在于，fixedPoint 中的函数 g 永远不会被正确评估（我总是得到 inf. 结果）。我认为我错过了有关可调用传递和 lambda 捕获的一些内容（我尝试在 lambda 中传递 std::function）。下面我有运行平方根问题的示例代码。

#include <iostream>
#include <functional>
#include <cmath>

static constexpr double DELTA = 0.0000001;
static constexpr int MAX_IT = 50000;
using my_function = std::function<double(double)>;

double derivative(const my_function& f, const double x) {
    return (f(x + DELTA) - f(x)) / DELTA;
}

bool isConverge(const double p1, const double p2) {
    return std::abs(p1 - p2) < DELTA;
}

double fixedPoint(const my_function& g, double x = 1) {

    int itCnt = 0;
    std::function<double(double, double)> loop;
    loop = [&g, &itCnt, &loop](double x0, double x1) -> double {
        if (isConverge(x0, x1) || (++itCnt > MAX_IT)) return x1;
        return loop(x1, g(x1));
    };

    return loop(x, g(x));
}

my_function newtonsMethod(const my_function& f) {
    return [&f](double x) -> double {return x - f(x) / derivative(f, x); };
}

double findRoot(const my_function& f) {
    return fixedPoint(newtonsMethod(f));
}

double sqRoot(double x) { 
    return findRoot([x](int y) {return y * y - x; });
}

int main() {
    const double num = 133;
    std::cout << "Square root " << num << ": " << sqRoot(num) << '\n';
    return 0;
}
4

1 回答 1

2

你的问题是int从双截断

return findRoot([x](int y) {return y * y - x; });

所以当你计算 时derivative，你得到 0。

改成

return findRoot([x](double y) {return y * y - x; });

演示

于 2020-11-16T14:58:36.420 回答