SICP练习1.16，我的bug在哪里，因为它看起来对我来说是正确的

发布于 2024-08-09 12:05:04 字数 425 浏览 2 评论 0原文

我刚刚开始阅读这本书是为了好玩；我希望这是家庭作业，但我永远无法负担麻省理工学院的学费，而且还有很多比我聪明的人。 :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

原文

I've just started working through this book for fun; I wish it were homework, but I could never afford to attend MIT, and there are tons of people smarter than me anyway. :p

fast-exp is supposed to find b^n, i.e. 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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

許願樹丅啲祈禱 2024-08-16 12:05:04

您忘记调用 fast-exp。相反，您评估了三个单独的原子。要实际评估 4 到 2 的快速表达式，您必须编写

(fast-exp 4 2)

You forgot to call fast-exp. Instead, you evaluated three separate atoms. To actually evaluate the fast-exp of 4 to the 2, you'd have to write

(fast-exp 4 2)

回复收藏 0 原文

ゝ杯具 2024-08-16 12:05:04

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

回复收藏 0 原文

瞄了个咪的 2024-08-16 12:05:04

你的解决方案是计算错误的答案。（请参阅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))

Your solution is calculating wrong answers. (See http://ideone.com/quT6A) In fact, how you in principle can write a tail-recursive fast exponentiation passing only two numbers as arguments? I don't think it's even possible, because in the middle of computation you don't know what multiplier to use if you encounter odd exponent.
But I can give an example of working solution that is exactly what is expected by SICP authors (iterative process using "invariant quantity" (a * b^n), where a is initially 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))

回复收藏 0 原文

~没有更多了~