SICP 全笔记

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_nx^n + a_{n-1}x^{n-1}+\dots+a_1x+a_0 $$ using a well-known algorithm called Horner’s rule, which structures the computation as

$$ (\dots (a_nx+a{n-1})x+\dots+a_1)x + a_0 $$ In other words, we start with an, multiply by x, add an-1, multiply by x, and so on, until we reach a0.16 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 a0 through an.

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) <??>)
              0
              coefficient-sequence))

For example, to compute 1 + 3x + 5x3 + x5 at x = 2 you would evaluate

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

对公式

$$ (\dots (a_nx+a{n-1})x+\dots+a_1)x + a_0 $$ 使用 accumulate 求解。

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))

;;; tests begin
(load "../testframe.scm")

(assert= (horner-eval 2 (list 1 3 0 5 0 1))
         79)

问题：什么样的问题是可以通过 accumulate 这样的高阶函数来解决的呢？