2

我刚开始读这本书是为了好玩。我希望这是家庭作业，但我永远无法负担上麻省理工学院的费用，而且还有很多人比我聪明。:p

fast-exp 应该找到 b^n，即 4^2 = 16, 3^3 = 27

(define (fast-exp b n)
  (define (fast-exp-iter n-prime a)
    (cond ((= n-prime 1) a)
          ((= (remainder n-prime 2) 1) (fast-exp-iter (- n-prime 1) (* a b)))
          (else (fast-exp-iter (/ n-prime 2) (* a b b)))))
  (fast-exp-iter n 1))

fast-exp 4 2; Expected 16, Actual 2
4

3 回答 3

5

你忘了叫 fast-exp。相反，您评估了三个单独的原子。要实际评估 4 到 2 的 fast-exp，您必须编写

(fast-exp 4 2)
于 2009-10-29T13:23:57.513 回答
2

您在此处编写的解决方案也不正确。例如签出（fast-exp 2 6）。预期：64，实际：32。

于 2010-02-25T15:20:24.640 回答
1

您的解决方案是计算错误的答案。（参见http://ideone.com/quT6A）事实上，原则上你如何编写一个尾递归快速幂运算，只传递两个数字作为参数？我认为这甚至是不可能的，因为在计算过程中，如果遇到奇数指数，您不知道要使用什么乘数。但我可以举一个工作解决方案的例子，这正是 SICP 作者所期望的（使用“不变量”（a * b^n）的迭代过程，其中 a 最初为 1）

(define (pow x y)
  (define (powi acc x y)
    (cond
      ((= y 0) acc)
      ((odd? y) (powi (* acc x) x (- y 1)))
      (else (powi acc (* x x) (/ y 2)))))
  (powi 1 x y))
于 2012-08-10T01:00:44.693 回答