c - C 中的牛顿-拉夫森

Question

我正在编写一个程序，使用 C 中的 Newton-Raphson 方法求给定整数 n 的平方根的近似值。我使用了以下公式:

这是我的代码:

#include <stdio.h>

double newton_raphson(int n, int iter);

double newton_raphson(int n, int iter)
{
    if(iter == 0) // base case
        return 1;
    else // iterative case
        return (1/2*(newton_raphson(n, iter-1) + n/(newton_raphson(n, iter-1))));
}

int main()
{
    int n;
    int i;

    printf("Enter a number you want to know the square root of:\n");
    fflush(stdout);
    scanf("%d", &n);
    printf("Enter number of iterations to be worked out:\n");
    fflush(stdout);
    scanf("%d", &i);

    printf("%.3f", newton_raphson(n,i-1));

    return 0;
}

当我输入 2 和 3 时，预期输出为 1.417(3 次迭代后 2 的平方根)，我得到错误 -1.#IO。例如，当我输入 5 和 2 时，我得到 0.000。我已经调试了它，但仍然无法真正弄清楚问题是什么。非常感谢任何帮助。

编辑:详细说明输出

Answer 1

您的问题似乎是您对浮点运算处理不当。

1. newton_raphson 函数的第一个参数应该是 double，尤其是因为您似乎在递归调用它。现在，您只需将一次迭代的结果转换为一个整数，然后将其传递给下一次迭代。

2. 1/2 使用整数运算。那应该是 0.5 或 1.0/2.0。请注意，在整数运算中，1/2 是 0。您看到的错误是因为您随后将该 0 传递给下一次迭代，然后它除以 0。

固定代码

#include <stdio.h>

double newton_raphson(double n, int iter);

double newton_raphson(double n, int iter)
{
    if (iter == 0) {
        return 1;
    }
    else {
        return 0.5 * (newton_raphson(n, iter - 1) + n/(newton_raphson(n, iter - 1)));
    }
}

int main()
{
    int n;
    int i;

    printf("Enter a number you want to know the square root of:\n");
    fflush(stdout);
    scanf("%d", &n);
    printf("Enter number of iterations to be worked out:\n");
    fflush(stdout);
    scanf("%d", &i);

    printf("%.3f\n", newton_raphson(n, i - 1));

    return 0;
}

可能的改进

正如其他人在评论中指出的那样，您可以使此实现更有效率。

首先，您可以通过将结果保存在变量中来消除函数调用。由于这是一个递归函数，如果您有很多迭代，这将为您节省大量的执行时间。

double newton_raphson(double n, int iter)
{
    if (iter == 0) {
        return 1;
    }
    else {
        double xk = newton_raphson(n, iter - 1);
        return 0.5 * (xk + n / xk);
    }
}

然后，您可以完全消除递归。如果您运行多次迭代，这将使您的程序消耗更少的内存，因为您摆脱了不必要的堆栈操作。

double newton_raphson(double n, int iter)
{
    int k;
    double xk = 1;
    for (k = 0; k < iter; k++) {
        xk = 0.5 * (xk + n / xk);
    }
    return xk;
}

更多提示

对于迭代计数，您应该使用 unsigned int(或简称为 unsigned)而不是 int。运行负数的迭代没有意义，例如。你不能运行 -5 迭代...所以你不需要有符号整数。

#include <stdio.h>

double newton_raphson(double n, unsigned iter);

double newton_raphson(double n, unsigned iter)
{
    unsigned k;
    double xk = 1;
    for (k = 0; k < iter; k++) {
        xk = 0.5 * (xk + n / xk);
    }
    return xk;
}

int main()
{
    int n;
    unsigned i;

    printf("Enter a number you want to know the square root of:\n");
    fflush(stdout);
    scanf("%d", &n);
    printf("Enter number of iterations to be worked out:\n");
    fflush(stdout);
    scanf("%u", &i);

    printf("%.3f\n", newton_raphson(n, i - 1));

    return 0;
}

还有一些事情:

• 通过检查函数的参数或可能返回零的函数调用的结果，保护您的代码免受可能的被零除错误的影响通常是一种很好的做法。
• 您可能应该检查负数的输入，并告诉用户您不能使用此算法计算负数的平方根。
• 对于输入，您可以允许用户输入 float 而不是整数。