乐正

Actions speak louder than words.

Sicp-ex1-16

问题

请定义一个过程,它能产生出一个按照迭代方式的求幂计算过程,其中使用一系列的求平方 ,就像fast-expt一样只用对数个步骤。(提示:请利用关系$(b^{\frac {n} {2}})^2 = (b^2)^{\frac {n} {2}}$ ,除了指数$n$和基数$b$之外,还应维持一个附加状态变量$a$,并定义好状态变换,使得 从一个状态转到另一个状态时乘积$a b^n$不变。在计算过程开始时令$a$取值1,并用计算 过程结束时$a$的值作为回答。一般说,定义一个不变量,要求它在状态转换之间保持不变 ,这以技术是思考迭代算法设计问题时的一种非常强有力的方法。)

解答

练习1.16 (ex1-16.scm) download
1
2
3
4
5
6
7
8
9
10
(define (fast-expt b n)
  (define (even? n)
    (= (remainder n 2) 0))

  (define (fast-expt-iter b n product)
    (cond ((= n 0) product)
          ((even? n) (fast-expt-iter (square b) (/ n 2) product))
          (else (fast-expt-iter b (- n 1) (* product b)))))

  (fast-expt-iter b n 1))

测试

1
2
3
4
5
6
7
8
(fast-expt 3 4)
;Value: 81

(fast-expt 2 2)
;Value: 4

(fast-expt 3 18)
;Value: 387420489

draft

« sicp-ex1-15 sicp-ex1-17 »

Comments