sicp习题试解 (1.20)

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

;

; Structure and Interpretation of Computer Programs

; (trial answer to excercises)

;

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

;

; created: code17 02/28/05

; modified:

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

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

;; SICP No.1.20

;; 本题为理解题

;; 一般情况下，正则序的操作总是要多于应用序，这是因为函数参数并非在调用时估值，而是

;; 在使用时，因此如果同一个参数在函数中多次使用就会造成多次估值。

;; 为了简单起见，以n-re表示某个含有n个remainder操作的表达式

;; 另外，原程序中用于表达最大公约数(Greatest Common Divisor)的(\G\C\D)，因与执

;; 政党名称相同，数次提交系统均禁止发表，这里统一用g-c-d和G-C-D代替

;; a.正则序

;;

;; (g-c-d 206 40) ;; 即G-C-D(206,40)

;; ==> (if (= 40 0) 206 (g-c-d 40 1-re))

;; ==> (g-c-d 40 1-re) ;; 即G-C-D(40,6)

;; ==> (if (= 1-re 0) 40 (g-c-d 1-re 2-re)) ;; 条件判断evaluate 1-re (+1)

;; ==> (g-c-d 1-re 2-re) ;; 即G-C-D(6,4)

;; ==> (if (= 2-re 0) 1-re (g-c-d 2-re 4-re)) ;; 条件判断evaluate 2-re (+2)

;; ==> (g-c-d 2-re 4-re) ;; 即G-C-D(4,2)

;; ==> (if (= 4-re 0) 2-re (g-c-d 4-re 7-re)) ;; 条件判断evaluate 4-re (+4)

;; ==> (g-c-d 4-re 7-re) ;; 即G-C-D(2,0)

;; ==> (if (= 7-re 0) 4-re (g-c-d 7-re 12-re));; 条件判断evaluate 7-re (+7)

;; ==> 4-re ;; 条件满足，取4-re

;; ==> 0-re ;; 4次remainder操作， (+4)

;; ;; evaluation得最后结果

;;

;; 正则序下，共有remainder操作1+2+4+7+4=18次

;; b.应用序

;;

;; (g-c-d 206 40) ;; 即G-C-D(206,40)

;; ==> (if (= 40 0) 206 (g-c-d 40 1-re))

;; ==> (g-c-d 40 1-re)

;; ==> (g-c-d 40 6) ;; 参数evaluation (+1)

;; ==> (if (= 6 0) 40 (g-c-d 6 1-re))

;; ==> (g-c-d 6 1-re)

;; ==> (g-c-d 6 4) ;; 参数evaluation (+1)

;; ==> (if (= 4 0) 6 (g-c-d 4 1-re))

;; ==> (g-c-d 4 1-re)

;; ==> (g-c-d 4 2) ;; 参数evaluation (+1)

;; ==> (if (= 2 0) 4 (g-c-d 2 1-re))

;; ==> (g-c-d 2 1-re)

;; ==> (g-c-d 2 0) ;; 参数evaluation (+1)

;; ==> (if (= 0 0) 2 (g-c-d 0 1-re))

;; ==> 2 ;; 条件满足，直接取值

;;

;; 应用序下，共有remainder操作1+1+1+1=4次