SICP 연습 1.16, 내 버그는 어디에 있습니까?

Question

방금이 책을 통해 재미를 위해 일하기 시작했습니다. 나는 그것이 숙제 였으면 좋겠다. 그러나 나는 MIT에 참석할 여유가 없었으며, 어쨌든 나보다 더 많은 사람들이 더 똑똑하다. :피

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

Answer 1

당신은 Fast-exp에게 전화하는 것을 잊었습니다. 대신, 당신은 세 개의 별도 원자를 평가했습니다. 실제로 4에서 2의 빠른 발을 평가하려면 글을 써야합니다.

(fast-exp 4 2)

Answer 2

여기에 작성한 솔루션도 잘못되었습니다. 예 : 체크 아웃 (Fast-Exp 2 6). 예상 : 64, 실제 : 32.

Answer 3

솔루션은 잘못된 답변을 계산하는 것입니다. (보다 http://ideone.com/qut6a) 사실, 원칙적으로 두 숫자 만 인수로 전달하는 꼬리 수반 빠른 지수를 어떻게 쓸 수 있습니까? 계산의 중간에는 홀수 지수를 만나면 어떤 승수를 사용할 것인지 모르기 때문에 가능하다고 생각하지 않습니다. 그러나 SICP 저자가 정확히 예상되는 작업 솔루션의 예를 제시 할 수 있습니다 ( "불변량"(A * B^N)을 사용하여 반복적 인 프로세스는 처음에 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))