递归函数在C中返回0

Question

我正在尝试使用一种称为 Neville 方法的特定方法来实现一种称为拉格朗日插值的插值方法。

我的问题是函数 returning 0，我不确定为什么。

这是一种递归方法，最终应该 return 根据其内插的数据估计给定输入的输出。

值 P_0,1,2,...,n-1,n 调用 P_1,2,...,n-1,n 和 P_0 ,1,2,...n-1。 P_1,2,...,n-1,n 调用 P_2,...,n-1,n 和 P_1,2,...,n-1。当它下降到 P_0、P_1、... 或 P_n 时，它正在调用 f(x_0)、f(x_1)、.. . 或 f(x_n)，这是事先已知的，因为它是插值数据的一部分。

在我展示递归函数的代码之前，我应该提到插值数据是一个二维数组，第一列是输入值 (x)，第二列是输出值 (y)。它只是一个随机排序的二维数组，x 和 y 都相等。

我还创建了一个函数，它获取数组的一部分，给定开始和结束索引，returns 作为另一个二维数组。这是为了辅助插值功能。

如下所示：

int **index_array(int **array, int beg, int stop)
{
    int i, **new_array, new_array_length;

    new_array_length = stop - beg + 1;

    new_array = malloc(sizeof(int *) * (new_array_length));

    for (i = 0; i < new_array_length; i++)
    {
        new_array[i] = malloc(sizeof(int)*2);
    }

    for (i = 0; i < new_array_length; i++)
    {
        new_array[i][0] = array[beg + i][0];
        new_array[i][1] = array[beg + i][1];
    }

    return new_array;
}

这里是插值函数：

int Lagrange_Neville(int **array, int n, int x)
{

    int i;

    if (n == 1)
    {
        return array[0][1];
    }

    return 1/(array[n-1][0] - array[0][0]) * ((x - array[0][0])*Lagrange_Neville(index_array(array, 1, n-1), n-1, x)-(x-array[n-1][0])*Lagrange_Neville(index_array(array, 0, n-2), n-1, x));
}

我的主要（）：

int main(void)
{

    srand(time(NULL));

    int **array, **new_array, n, beg, end, x;

    n = 10;
    beg = 5;
    end = n-1;
    x = 5;

    array = createArray(n);

    printf("First array:\n");
    print_array(array, n);

    new_array = index_array(array, beg, end);

    printf("New array from indices %d to %d of the old array:\n", beg, end);
    print_array(new_array, end-beg+1);

    printf("Output of lagrange interpolating estimated at x = %d\n", x);
    printf("%d\n", Lagrange_Neville(array, n, x));

    return 0;
}

我的输出：

First array:
2 2
5 5
7 7
9 9
12 12
13 13
16 16
17 17
20 20
21 21

New array from indices 5 to 9 of the old array:
13 13
16 16
17 17
20 20
21 21

Output of lagrange interpolating estimated at x = 5
0

感谢任何帮助。

Answer 1

首先跳出来的是你的 Lagrange_Neville() 函数被声明为返回 int，而你在这里使用整数除法：

return 1/(array[n-1][0] - array[0][0]) * ((x - array[0][0])*Lagrange_Neville(index_array(array, 1, n-1), n-1, x)-(x-array[n-1][0])*Lagrange_Neville(index_array(array, 0, n-2), n-1, x));

因为 array 被声明为包含整数，而 1 显然是一个整数，您将在第一个除法中得到一个整数结果，它可能给出 0。您可以更改除法以给出float 通过使用 1.0 作为分子代替 1 结果，但是由于函数 returns int 你仍然会得到一个转换为的答案那种类型，这可能不是你想要的。尝试声明该函数，使其 returns 成为浮点类型。

Answer 2

零来自函数 returns:

中的第一项

1/(array[n-1][0] - array[0][0])

您正在执行 1 除以大于一的数的整数除法。由于数学结果小于 1，并且由于数字的小数部分被截断，所以最终得到 0。

您需要通过使至少一个操作数成为 double 来进行浮点数学计算。您可能也应该 return 一个 double 来自您的函数。

double Lagrange_Neville(int **array, int n, int x)
{

    int i;

    if (n == 1)
    {
        return array[0][1];
    }

        //   v---- constant of type double
    return 1.0/(array[n-1][0] - array[0][0]) * ((x - array[0][0])*Lagrange_Neville(index_array(array, 1, n-1), n-1, x)-(x-array[n-1][0])*Lagrange_Neville(index_array(array, 0, n-2), n-1, x));
}

递归函数在C中返回0

Recursive Function returning 0 in C

c

arrays

algorithm

recursion

interpolation