sicp 2.3小结习题尝试解答-阿里云开发者社区

开发者社区> boxti> 正文

sicp 2.3小结习题尝试解答

简介:
+关注继续查看
 习题2.2没有全部做,我读书的速度远远超过做习题的进度,没办法,时间有限,晚上的时间基本用来看书了,习题也都是在工作间隙做的,慢慢来了,前两章读完再总结下。回到2.3节,这一节在前几节介绍数值型符号数据的基础上引入了符号数据,将任意符号作为数据的能力非常有趣,并给出了一个符号求导的例子,实在是太漂亮了。

习题2.53,直接看结果:
> (list '''c)
(a b c)
> (list (list 'george))
((george))
> (cdr '((x1 x2) (y1 y2)))
((y1 y2))
> (cadr '((x1 x2) (y1 y2)))
(y1 y2)
> (pair? (car '(a short list)))
#f
> (memq? 'red '((red shoes) (blue socks)))
#f
> (memq? 'red '(red shoes blue socks))
(red shoes blue socks)

习题2.54,equal?过程的定义,递归定义,很容易
(define (equal? a b)
  (cond ((
and (not (pair? a)) (not (pair? b)) (eq? a b)) #t)
        ((and (pair? a) (pair? b))
         (
and (equal? (car a) (car b)) (equal? (cdr a) (cdr b))))
        (
else
          (display 
"a and b are not equal"))))
注意,在DrScheme实现中,eq?可以用于比较数值,比如(eq? 1 1)也是返回真

习题2.55,表达式(car ''abracadabra)其实就是
(car (quote (quote abracadabra))),也就是(car '(quote abracadabra)),显然将返回quote

习题2.56,求幂表达式的导数,学着书中的代码写,也很容易了,先写出constructor和selector:
(define (make-exponentiation base e)
  (cond ((
= e 0) 1)
        ((
= e 1) base)
        (
else
          (list 
'** base e))))
(define (base x) (cadr x))
(define (exponent x) (caddr x))
(define (exponentiation? x)
  (
and (pair? x) (eq? (car x) '**)))
用**表示幂运算,因此(make-exponentiation x 3)表示的就是x的3次方。
修改deriv过程,增加一个条件分支:
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (
if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make
-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make
-sum
            (make
-product (multiplier exp)
                          (deriv (multiplicand exp) var))
            (make
-product (multiplicand exp)
                          (deriv (multiplier exp) var))))
        ((exponentiation? exp)
         (let ((n (exponent exp)))
         (make
-product (make-product n (make-exponentiation (base exp) (- n 1))) (deriv (base exp) var))))
        (
else
           error 
"unknown expression type -- Deriv" exp)))
粗体的就是我们增加的部分,两次运用make-product做乘法。
测试下:
> (deriv '(** x 3) 'x)
(
* 3 (** x 2))
> (deriv '(** (+ x 1) 5) 'x)
(
* 5 (** (+ x 14))

习题2.57,只要修改selector函数就够了,如果是多项的和或者积,那么被乘数和被加数也是列表,可以直接表示为符号表达式而不求值
 (define (augend s)
 (let ((rest (cddr s)))
    (
if (null? (cdr rest))
        (car rest) 
        (cons 
'+ rest))))
(define (multiplicand p)
  (let ((rest (cddr p)))
    (
if (null? (cdr rest))
        (car rest) 
        (cons 
'* rest))))

习题2.58,分为a和b,a倒是很容易解答,修改下谓词、选择函数和构造函数就可以了,将运算符号放在列表中间,注意,题目已经提示,假设+和*的参数都是两个,因此
(a)题目:
(define (=number? x y)
  (
and (number? x) (= x y)))
(define (variable? x) (symbol? x))
(define (same
-variable? v1 v2) (and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (sum? x)
  (let ((op (cadr x)))
    (
and (symbol? op) (eq? op '+))))
(define (addend s) (car s))
(define (augend s) (caddr s))
(define (make
-sum a1 a2)
  (cond ((
=number? a1 0) a2)
        ((
=number? a2 0) a1)
        ((
and (number? a1) (number? a2)) (+ a1 a2))
        (
else
         (list a1 
'+ a2))))
(define (product? x)
  (let ((op (cadr x)))
    (
and (symbol? op) (eq? op '*))))
(define (multiplier x) (car x))
(define (multiplicand x) (caddr x))
(define (make
-product a1 a2)
  (cond ((
or (=number? a1 0) (=number? a2 0)) 0)
        ((
=number? a1 1) a2)
        ((
=number? a2 1) a1)
        ((
and (number? a1) (number? a2)) (* a1 a2))
        (
else
          (list a1 
'* a2))))
测试下:
> (deriv '(x + (3 * (x + (y + 2)))) 'x)
4
> (deriv '(x + 3) 'x)
1
> (deriv '((2 * x) + 3) 'x)
2
> (deriv '((2 * x) + (3 * x)) 'x)
5

习题2.59,求集合的交集,遍历集合set1,如果(car set1)不在集合set2中,就将它加入set2,否则继续,当集合set1为空时返回set2。
(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((element
-of-set? (car set1) set2) set2)
        (
else
          (union
-set set1 (cons (car set1) set2))))) 

习题2.60,需要修改的仅仅是adjoin-set:
(define (adjoin-set x set)
  (cons x set))
效率由原来的n变成常量。其他操作的效率与原来的一样。有重复元素的集合,比如成绩单、钱币等等。


习题2.61,关键点就是在于插入元素后要保持集合仍然是排序的,如果x小于(car set),那么最小的就应该排在前面了,如果大于(car set),那么将(car set)保留下来,继续往下找:
(define (adjoin-set x set)
  (cond ((null
? set) (list x))
        ((
= x (car set)) set)
        ((
< x (car set)) (cons x set))
        (
else
           (cons (car set) (adjoin
-set x (cdr set))))))

习题2.62,与求交集类似:
(define (union-set set1 set2)
  (cond ((null
? set1) set2)
        ((null
? set2) set1)
        (
else
         (let ((x1 (car set1))
               (x2 (car set2)))
           (cond ((
= x1 x2)
                  (cons x1
                        (union
-set (cdr set1) (cdr set2))))
                 ((
< x1 x2)
                  (cons x1
                        (union
-set (cdr set1) set2)))
                 ((
> x1 x2)
                  (cons x2
                        (union
-set set1 (cdr set2)))))))))

测试下:
> (define set1 (list 2 3 4 5 9 20))
> (define set2 (list 1 2 3 5 6 8))
> (union-set set1 set2)
(
1 2 3 4 5 6 8 9 20)

习题2.63,其实两个变换过程都可以看成是对树的遍历
a)通过测试可以得知,产生一样的结果,两者都是中序遍历二叉树,书中图的那些树结果都是(1 3 5 7 9 11)
b)对于tree->list-1过程来说,考虑append过程,并且每一步并没有改变搜索规模,而append的增长阶是O(n),因此tree->list-1的增长阶应该是O(n2),n的二次方
而对于tree-list-2过程,增长阶显然是O(n)

习题2.64,这题非常有趣,用一个数组构造一棵平衡的树,显然,方法就是将数组对半拆分,并分别对两个部分进行构造,这两个部分还可以拆分直到遇到数组元素(左右子树都是'()),中间元素作为entry。这个过程可以一直递归下去。这里采用的正是这种方式
a)解释如上,(1 3 5 7 9 11)将形成下列的二叉树:
        5
       /  \
      1    9
       \  /  \
        3 7   11
显然,列表的对半拆分,以5作为根节点,然后左列表是(1 3),右列表是(7 9 11),左列表拆分就以1为节点,右列表拆分以9为节点,其他两个为子树。

b)仍然是O(n)

习题2.65,很简单了,转过来转过去就是了:
(define (union-set-1 tree1 tree2)
  (list->tree (union-set (tree->list-2 tree1)
                         (tree->list-2 tree2))))
(define (intersection-set-1 tree1 tree2)
  (list->tree (intersection-set (tree->list-2 tree1)
                                (tree->list-2 tree2))))

 习题2.66,与element-of-set?类似:
(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) #f)
        ((= given-key (key (entry set-of-records))) (entry set-of-records))
        ((
< given-key (key (entry set-of-records))) 
           (lookup given-key (left-branch set-of-records)))
        ((
> given-key (key (entry set-of-records))) 
           (lookup given-key (right-branch set-of-records)))))

习题2.67,结果是(a d a b b c a) ,DrScheme字母符号是小写
习题2.68,使用到memq过程用于判断符号是否在列表中:
(define (encode-symbol symbol tree)
  (define (iter branch)
    (if (leaf? branch)
        '()
        (if (memq symbol (symbols (left-branch branch)))
            (cons 0 (iter (left-branch branch)))
            (cons 1 (iter (right-branch branch))))
        ))
  (if (memq symbol (symbols tree))
      (iter tree)
      (display "bad symbol -- UNKNOWN SYMBOL")))
习题2.69,因为make-leaf-set产生的已经排序的集合,因此从小到大两两合并即可:
(define (generate-huffman-tree pairs)
  (successive
-merge (make-leaf-set pairs)))
(define (successive-merge set)
  (if (= 1 (length set))
(car set)
(successive-merge
(adjoin-set (make-code-tree (car set) (cadr set)) (cddr set)))))

习题2.70,利用generate-huffman-tree和encode过程得到消息,使用length测量下消息长度就知道多少位了:
(define roll-tree (generate-huffman-tree '((A 2) (NA 16) (BOOM 1) (SHA 3) (GET 2) (YIP 9) (JOB 2) (WAH 1))))
(define message (encode
         
'(Get a job Sha na na na na na na na na Get a job Sha na na na na na na na na Wah yip yip yip yip yip yip yip yip yip Sha boom)
         roll
-tree))

> (length message)
84

  通过huffman编码后的位数是84位,如果采用定长编码,因为需要表示8个不同符号,因此需要log2(8)=3位二进制,总位数至少是36*3=108位,压缩比为22.22%

习题2.71,很显然,最频繁出现的符号肯定在根节点下来的子树,位数是1,而最不频繁的符号是n-1位

文章转自庄周梦蝶  ,原文发布时间2007-07-03

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
8643 0
使用NAT网关轻松为单台云服务器设置多个公网IP
在应用中,有时会遇到用户询问如何使单台云服务器具备多个公网IP的问题。 具体如何操作呢,有了NAT网关这个也不是难题。
26538 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2840 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
11013 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
2294 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
8802 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
7340 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
21735 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
6629 0
+关注
boxti
12535
10037
文章
1327
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载