SICP упражнение 1.16, где моя ошибка, потому что она выглядит правильно для меня

Question

Я только начал прорабатывать эту книгу для развлечения; Хотелось бы, чтобы это была домашняя работа, но я никогда не мог позволить себе посещать Массачусетский технологический институт, и в любом случае есть тонны людей, которые умнее меня. : Р

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

Решение, которое вы написали здесь, также неверно. например Выезд (быстрый опыт 2 6). Ожидаемое: 64, фактическое: 32.

Answer 3

Ваше решение рассчитывает неправильные ответы. (См. 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))