Exercise 2.34: Evaluating a polynomial in x
at a given value of x can be formulated as an accumulation. We evaluate
the polynomial
a
n
x
n
+
a
n
−
1
x
n
−
1
+
⋯
+
a
1
x
+
a
0
using a well-known algorithm called
Horner’s rule, which structures
the computation as
(
…
(
a
n
x
+
a
n
−
1
)
x
+
⋯
+
a
1
)
x
+
a
0
.
In other words, we start with a
n, multiply by x, add
a
n
−
1, multiply by x, and so on, until we reach
a
0.
Fill in the following template to produce a procedure that evaluates a
polynomial using Horner’s rule. Assume that the coefficients of the polynomial
are arranged in a sequence, from a
0 through a
n.
(define
(horner-eval x coefficient-sequence)
(accumulate
(lambda (this-coeff higher-terms)
⟨??⟩)
0
coefficient-sequence))
For example, to compute 1
+
3
x
+
5
x
3
+
x
5 at x
=
2 you
would evaluate
(horner-eval 2 (list 1 3 0 5 0 1))
练习 2.34：在给定 x 值处对多项式求值，可以表述为一种累积操作。我们用一种称为霍纳规则 (Horner's rule) 的著名算法来对多项式
a_n x^n + a_{n-1} x^{n-1} + ⋯ + a_1 x + a_0
求值，该算法将计算组织为
(⋯((a_n x + a_{n-1}) x + ⋯ + a_1) x + a_0)。
换句话说，从 a_n 开始，乘以 x，加上 a_{n-1}，再乘以 x，如此类推，直到加上 a_0。
填写下列模板，产生一个用霍纳规则对多项式求值的过程。假设多项式的各系数按从 a_0 到 a_n 的顺序排列在一个序列中。
(define
(horner-eval x coefficient-sequence)
(accumulate
(lambda (this-coeff higher-terms)
⟨??⟩)
0
coefficient-sequence))
例如，要在 x = 2 处计算 1 + 3x + 5x^3 + x^5，可以求值
(horner-eval 2 (list 1 3 0 5 0 1))
(define
(horner-eval x coefficient-sequence)
(accumulate
(lambda (this-coeff higher-terms)
⟨??⟩)
0
coefficient-sequence))(horner-eval 2 (list 1 3 0 5 0 1))