时间戳

首页 > 解决方案 > 为什么我在 C 中得到关于霍纳规则的错误输出

c - 为什么我在 C 中得到关于霍纳规则的错误输出

问题描述

f(x) = a 0 + a 1 *x + a 2 *x 2 +...+a n *x n

首先，我创建一个动态数组来存储n的值。然后我定义了一个函数来描述霍纳规则，但是无论我改变输出的方式，我都会得到一个巨大的数字。代码有什么问题？

#include <stdio.h>
#include <malloc.h>

int f(int n, int *p, int x);

int main() {
    int *pA;
    int length;
    int x;
    int i;

    printf("input the length of Array:"); ///createArray of 'An'
    scanf("%d", &length);

    printf("please input x = ");
    scanf("%d", &x);

    pA = (int *)malloc(4 * length);
    for (i = 0; i < length; i++) {
         printf("input the No.%d element:", i + 1);
         scanf("%d", &pA[i]);    
    }

    printf("%d\n", f(length, pA, x));   ///Horner's rule

    return 0;
}

int f(int n, int *p, int x) {
    int i;
    int pn = p[n - 1];

    for (i = n; i >= 1; i--) {
        pn = p[i - 2] + x * pn;
    }

    return pn;
}

标签： c

解决方案

给定多项式

f(x) = a 0 + a 1 x + a 2 x 2 + ... + a n x n

霍纳规则让我们用这个公式来评估它

f(x) = a 0 + x(a 1 + x(a 2 + ... x(a n -1 + xan ) ... ))

我们可以将其转换为递归公式并向后遍历系数数组。

f n = a n 
f i = a i + x⋅f i + 1

请记住，所述数组的实际大小将是n + 1并且有一个众所周知的习惯用法用于以这种方式遍历数组，该函数的可能实现可能如下。

double evaluate_poly_using_horner(size_t n, int const *c, double x)
{
    if ( n == 0 )
        return 0.0;

    double result = c[n - 1];

    for( size_t i = n - 1; (i--) > 0; )
    {
        result = c[i] + x * result;
    }
    return result;
}

这将解决 OP 代码中的问题，其中条件i >= 1导致循环体执行到i == 1，从而导致访问数组的边界p（p[i - 2] = ...变得p[-1] = ...）。

另请注意，这些行

#include <malloc.h>
// ...
int *pA;
// ...
pA = (int *)malloc(4 * length);
//   ^^^^^^^       ^
// ...

可以写成

#include <stdlib.h>
// ...
int *pA = malloc((sizeof *pA) * length);
if ( !pA ) {
    // Deal with the failed allocation, maybe exit(1)
}
// ...
free(pA);      // <- Don't leak memory!

推荐阅读