SICP演習1.16、私のバグはどこにあるか

Question

この本を楽しみながら作業を始めたばかりです。宿題だったらよかったのに、MITに参加する余裕はなかったし、とにかく私より賢い人がたくさんいる。 ：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

Answer 1

fast-expを呼び出すのを忘れました。代わりに、3つの別々の原子を評価しました。 4から2への高速表現を実際に評価するには、次のように記述する必要があります

(fast-exp 4 2)

Answer 2

ここに書いた解決策も間違っています。例えばチェックアウト（fast-exp 2 6）。予想：64、実際：32。

Answer 3

あなたの解決策は間違った答えを計算しています。 （ http://ideone.com/quT6A を参照）実際、原則として、どのように末尾再帰を書くことができるか引数として2つの数値のみを渡す高速べき乗？計算の途中で、奇数の指数に遭遇した場合に使用する乗数がわからないため、それは可能だとさえ思いません。 ただし、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))