sicp习题试解 (1.17)

; ======================================================================

;

; Structure and Interpretation of Computer Programs

; (trial answer to excercises)

;

; 计算机程序的构造和解释(习题试解)

;

; created: code17 02/28/05

; modified:

; (保持内容完整不变前提下，可以任意转载)

; ======================================================================

;; SICP No.1.17

;; 辅助函数

(define (double x)

(+ x x))

(define (halve x)

(/ x 2))

(define (even? x)

(= (remainder x 2) 0))

;; 递归版本

(define (fast-mult-r a b)

(cond ((= b 0) 0)

((even? b) (double (fast-mult-r a (halve b))))

(else (+ a (fast-mult-r a (- b 1))))))

;; 迭代版本

(define (fast-mult-i a b)

(expt-iter a b 0))

(define (expt-iter a b s)

(cond ((= b 0) s)

((even? b) (expt-iter (double a) (halve b) s))

(else (expt-iter (double a) (halve (- b 1)) (+ s a)))))

;; Test-it:

;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.

;; > (fast-mult-r 13 19)

;; 247

;; > (fast-mult-i 19 13)

;; 247

;; > (fast-mult-r 5 58)

;; 290

;; > (fast-mult-i 58 5)

;; 290

;; >