scheme - 如果事先不了解 Scheme 的底函数和舍入函数，如何完成 SICP 练习 1.45(计算 n 次方根函数)？

Question

同时完成 SICP's Exercise 1.45 ，人们很快就会注意到，需要应用 average-damp 过程来求一个数的 n 次方根的次数非常接近 n 的以 2 为底的对数，向下舍入。换句话说，我们使用 (floor (/(log n) (log 2)))。众多online solutions采用这种确切的方法，我能找到的唯一异常(exception)是 a complex and uncommented solution from the Schemewiki .

但是，据我所知，Structure and Interpretation of Computer Programs 直到本练习出现的章节。这就提出了一个问题:我们对读者打算如何完成这个练习一无所知吗？或者如果失败了，是否有任何明显的方法可以做到这一点(即在事先不知道 floor 的情况下舍入 (/(log n) (log 2)))？

Answer 1

我认为您根本不需要了解Scheme 过程floor，因为练习说明明确说明您可能“假设您需要的任何算术运算都可以作为原语使用。”如果您需要 floor，您可以假设它是可用的。

但事实证明，您根本不需要 floor。只需定义repeated，使浮点计数有效下降:

(define (repeated f n)
  (if (< n 2)
      f
      (lambda (x) (f ((repeated f (- n 1)) x)))))

结合本书中的其他定义，您可以定义 nth-root 而无需 floor 过程:

(define (nth-root x n)
  (fixed-point ((repeated average-damp
                          (/ (log n) (log 2)))
                (lambda (y) (/ x (expt y (- n 1)))))
               1.0))