scheme - 计算多项式函数[方案/球拍]

Question

我正在尝试编写一个尾递归函数poly，该函数将计算给定值和系数列表的多项式的值。如，如果 coeff 是系数列表，(a0, a1, a2,...an)则应(poly x coeff)计算该值a0 + a1x +a2*x^2 + a3*x^3 + ...an*x^n

这些函数也有望在线性时间内运行 (O(n))

我对此的想法是创建一个辅助函数，它有一个额外的参数（acc）来跟踪你在列表中的位置，所以你知道将它提升到什么权力，但我想不出该怎么做

Answer 1

不需要辅助函数来跟踪您在列表中的位置，因为您一次只需要向前移动一个列表元素直到到达末尾。这是一个可能的骨架

(define (poly coeff)
  (let loop ((power 0) (total 0) (clist coeff))
    (cond
       ((null? clist) ???)
       (else (loop (+ 1 power) (??????) (cdr clist))))))

这就是为你完成的大部分工作。你真正需要做的就是弄清楚你应该如何计算指数和加法。有两个基本选项，我知道我会选择哪一个（更少的 cpu 周期）。