CG@CPPBLOG

/*=========================================*/
随笔 - 76, 文章 - 39, 评论 - 137, 引用 - 0
数据加载中……

我的SICP习题答案（1.20）

1.20
下面用 % 表示过程 remainder，那么正则序的过程如下：
 (gcd 206 40)
 (if (= 40 0) 206 (gcd 40 (% 206 40)))
 (gcd 40 (% 206 40))
 (if (= (% 206 40) 0) ;<##  1> [6]
     40 
     (gcd (% 206 40) (% 40 (% 206 40))
 (gcd (% 206 40) (% 40 (% 206 40)))
 (if (= (% 40 (% 206 40)) 0)   ;<##  2> [4]
     (% 206 40)
     (gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))
 (gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))
 (if (= (% (% 206 40) (% 40 (% 206 40))) 0) ;<## 4>[2]
     (% 40 (% 206 40))
     (gcd (% (% 206 40) (% 40 (% 206 40)))
          (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))
 (gcd (% (% 206 40) (% 40 (% 206 40)))
      (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))
 (if (= (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))) 0) ;<## 7>[0]
     (% (% 206 40) (% 40 (% 206 40)))
     (gcd ...)
 (% (% 206 40) (% 40 (% 206 40)))  ;<## 4>[2]

可以看出需要调用 remainder 共 1+2+4+7+4 = 18 次。

应用序计算过程如下：
(gcd 206 40)
(if (= 40 0) 206 (gcd 40 (% 206 40))) ;<##>
(gcd 40 6)
(if (= 6 0) 40 (gcd 6 (% 40 6)))      ;<##>
(gcd 6 4)
(if (= 4 0) 6 (gcd 4 (% 6 4)))        ;<##>
(gcd 4 2)
(if (= 2 0) 4 (gcd 2 (% 4 2)))        ;<##>
(gcd 2 0)
(if (= 0 0) 2 (gcd 0 (% 2 0)))
2

可以看出共需 4 次。

posted on 2008-03-27 21:59 cuigang 阅读(1014) 评论(2)  编辑 收藏 引用 所属分类: Lisp/Scheme 、我的SICP答案

评论

# re: 我的SICP习题答案（1.20）  回复  更多评论   

这个地方，练习1.5中说过：无论正则序还是应用序，特殊形式的if的求值规则都一样，都是谓词部分先求值，然后根据其结果确定随后求值的子表达式部分，所以这里遇到了if之后，b总是要先求值才能往下做。

因此正则序和应用序都一样是4次？
2010-03-20 17:12 | Mole

# re: 我的SICP习题答案（1.20）  回复  更多评论   

都是4次吧,像LZ那样无法知道什么时候停止代换
2010-09-12 23:31 | Cao_yuqing

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理