SICP 1.16

練習 1.16 — SICP 解題集

題目的提示我沒看懂。看了網上的答案才明白提示是這個意思。

對於對數複雜度的迭代求冪，我首先找了個例子例如

b^0

b^1 1

b^3 1

b^7 1

b^15 1

b^31 1

b^62 0

b^125 1

b^250 0

b^500 0

b^1000 0

再一想，這不就是把1000轉化成二進位數的過程嗎！

迭代的時候只要把1000轉成二進位，然後從高位往低位，遇到1就讓迭代數平方再乘b，遇到0就只平方。

於是寫了這麼一個程序：

(define (find-2^n m n)n (if (= m 0)n 0n (if (> (* 2 n) m) nt n nt (find-2^n m (* 2 n)))))nn(define (fast-expt-iter b n a p)n (if (= a 0.5)n pn (if (>= (- n a) 0)n (fast-expt-iter b (- n a) (/ a 2) (* p p b))n (fast-expt-iter b n (/ a 2) (* p p)))))nn(define (fast-expt1 b n)n (if (= n 0)n 1n (fast-expt-iter b n (find-2^n n 1) 1)))n

對於第1.19題，其實也可以用類似上述「位運算」的方式來寫 。

(define (get-binary-digit number digit)n ;(display number)n ;(newline)n (cond ((= (find-2^n number 1) (fast-expt1 2 digit)) 1)nt((< (find-2^n number 1) (fast-expt1 2 digit)) 0)nt(else (get-binary-digit (- number (find-2^n number 1)) digit))))nn(define (fib n)n (fib-iter1 1 0 0 1 n 0 0))n(define (fib-iter1 a b p q n m l)n (cond ((= n m) b)nt((= (get-binary-digit n l) 1)nt (fib-iter1 (+ (* b q) (* a q) (* a p))ntt (+ (* b p) (* a q))ntt (+ (* p p) (* q q))ntt (+ (* q q) (* 2 p q))ntt nntt (+ m (fast-expt1 2 l))ntt (+ l 1)))nt (else (fib-iter1 a nttt bnttt (+ (* p p) (* q q))nttt (+ (* q q) (* 2 p q))nttt nnttt mnttt (+ l 1)))))n

T 0,1 的平方是T1,1、四次方是 T 2,3，八次方是 T13,21。將n從低位往高位，每遇到1就用T p,q 去處理對應的a,b，否則a,b維持不變。get-binary-digit用來獲取數字的二進位位，例如1000就是1111101000。

> (get-binary-digit 1000 0)n(get-binary-digit 1000 1)n(get-binary-digit 1000 2)n(get-binary-digit 1000 3)n(get-binary-digit 1000 4)n(get-binary-digit 1000 5)n(get-binary-digit 1000 6)n(get-binary-digit 1000 7)n(get-binary-digit 1000 8)n(get-binary-digit 1000 9)n(get-binary-digit 1000 10)n0n0n0n1n0n1n1n1n1n1n0n

推薦閱讀：