SICP 习题 1.20 又回去讲正则序和应用序了,题目主要是考察书中提到的求最大公约数的过程gcd,问正则序中(gcd 206 40)调用了几次remainder,而应用序中(gcd 206 40)又调用了几次remainder。
gcd过程的定义如下:
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
对于(gcd 206 40)来讲,如果是正则序,展开应该是这样的:
(if (= 40 0)
206
(gcd 40 (remainder 206 40)))
现在的关键在于对(gcd 40 (remainder 206 40))的展开。
从过程调用我们知道:
a = 40
b = (remainder 206 40)
再看过程gcd的定义:
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
每次gcd的调用如果展开的话会包含三次使用b的过程,将(remainder 206 40)代入b中就得到第二次展开的gcd过程。
结果是:
(if (= (remainder 206 40) 0)
40
(gcd (remainder 206 40)
(remainder a (remainder 206 40))))
通过这样的方法不断展开就可以得到正则序下(gcd 206 40)到底调用了几次remainder过程。
而应用序就很简单了,因为(gcd 206 40)展开成:
(if (= 40 0)
206
(gcd 40 (remainder 206 40)))
对(remainder 206 40)先求值再代入,变成:
(if (= 40 0)
206
(gcd 40 6))
然后继续对(gcd 40 6)进行展开,每次展开只调用了一次remainder。
这个题目再次说明应用序在一般情况下其效率都优于正则序。
分享到:
相关推荐
SICP 习题答案 计算机程序的构造和解释 1-3章 习题答案
SICP习题解答,主要第一章的内容习题答案
NULL 博文链接:https://pengpeng.iteye.com/blog/1344689
SICP 解题集
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 !!!download>>>https://github.com/wizardforcel/sicp-py-zh
SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版
SICP-Python版本
SICP 使用的scheme解释器 以前叫DrScheme
sicp 2.2.4节图形语言的racket程序包,配置路径,C:\Users\Administrator\AppData\Roaming\Racket
Python SICP epub版本,很适合学习抽象的思想,用Python版本比lisp更实用
SICP CHINESE ENGLISH THE SECOND EDITION SICP CHINESE ENGLISH THE SECOND EDITION
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 download : https://github.com/wizardforcel/sicp-py-zh
资源来自pypi官网。 资源全名:sicp-0.0.1b102.dev4.tar.gz
sicp 2ed高清pdf,以及相对应的mit课程资料及习题答案打包,中文版的视频在这里http://i.youku.com/i/UNTcxODk3ODQw/videos?spm=a2hzp.8244740.0.0
SICP 解题集《计算机程序的构造和解释》练习题解集。安装 MIT/GNU Scheme(macOS)下载:下载后运行 .dmg 文件,把 MIT/GNU Scheme.app 拖入 Applications 文件夹在 Applications/应用程序 文件夹中找到 MIT/GNU ...
sicp-in-python(中文版+英文版)PDF 背景. SICP 全称Structure and Interpretation of Computer Programs,翻译过来叫《计算机程序的构造和解释》使用python
资源名称:sicp 和 操作系统:精髓与设计原理第七版资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
经典书籍《计算机程序的构造与解释》,UCB热门课程CS61a的官方教材
#SICP SICP解决方案