SICP-2锻炼.34

【锻炼2.34】

为x给定值，找到一个多项式x的值，它也可以被形式化为累积。

下多项式的值：

an*x^n + an-1*x^n-1 + .... + a1*x + a0

採用著名的Horner规则，能够构造出以下的计算：

(...(an*x + an-1)*x + ... + a1)*x + a0

换句话说，我们能够从an開始。乘以x，再加上an-1，乘以x，如此下去，直到处理完a0.请填充以下的模板，做出一个利用Horner规则求多项式值得过程。假定多项式的系数安排在一个序列里，从a0直到an。

(define (horner-eval x coefficient-sequence)

(accumulate (lambda (this-coeff higher-terms) <??>)

coefficient-sequence))

比如，为了计算1 + 3x + 5x^3 + x^5 在x=2的值，你须要求值：

(horner-eval 2 (list 1 3 0 5 0 1))

【分析】

依据 Horner 规则，算式 1+3x+5x3+x5 能够转换成：

1+x(3+x(0+x(5+x(0+x))))

以上算式又能够转换为对应的前序表示：

(+1(∗x(+3(∗x(+0(∗x(+5(∗x(+0x)))))))))

lambda 部分每次的工作就是取出一个因数，并生成下面表达式(如果当前因数 this- coeff 为 1, x 为 2)： (+ 1 (*2 (accumulate ...))) ，由此能够给出完整的 horner-eval 函数定义：

【代码】

(define (horner-eval x coefficient-sequence)

    (accumulate (lambda (this-coeff higher-terms)

                    (+ this-coeff (* x higher-terms)))

                0

                coefficient-sequence))

【C语言版】

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int horner(int x, int k, int n, int *arr)

{

	if(k == n)

		return arr[k];

	else

		return (x * horner(x, k+1, n, arr) +arr[k]);

}

int main(void)

{

	int arr[6] = {1, 3, 0, 5, 0, 1};

	int x = 2;

	int result;

	result = horner(x, 0, 5, arr);

	printf("%d\n", result);

	return 0;

}

相关文章