您当前位置：首页 > 互联网 > SICP 习题（2.5）解题总结

SICP 习题（2.5）解题总结

来源：程序员人生发布时间：2014-10-04 08:00:00 阅读次数：2734次

SICP 习题 2.5 有点像是道数学题，首先要求我们证明可以将a和b的序对表示为2^a * 3^b，然后通过非负整数和算术运算表示序对。最后要求我们实现对应的cons, car 和cdr过程。

这道题的根本就是复合数据的构成方式和解析方式。其实，对于所有复合数据来讲，我们都在处理同样一件事情，就是如何把复合数据的组成部分构建在一起，同时可以通过特定的方法将它们拆解出来。

就好像我们要存放乒乓球和网球，同时可以区分乒乓球和网球，简单的方法就是将乒乓球和网球混合放在一起，需要的时候我们轻松地判别哪个是乒乓球，哪个是网球。我们的操作没有导致信息的丢失，一个球到底是乒乓球还是网球这个信息是跟随球本身而存在的。

相反，如果我们希望存放来自两个学校的乒乓球，同时可以区分不同学校的乒乓球，那就不能简单地将它们混合放在一起了。一旦将两个学校的乒乓球放在一起，我们就丢失一部分信息。混合之前我们知道A框的乒乓球来自某学校，B框的乒乓球来自另一个学校，一旦我们将它们混合放在一个框中，我们就丢失了有关哪个球属于哪个学校的信息。

回到题目，其实我们要搞清楚的就是当2^a * 3^b = x的时候，如果我们拿到数x，能不能倒推回a 和 b 各等于多少。

答案当然是可以的，具体的数学证明大家可以去百度一下，大概的意思就是任何一个大于1的整数都可以分解为唯一的一种素数相乘序列，因为我们的x=2^a * 3^b，而2^a * 3^b就是一种素数相乘的序列，也就是说x只能分解为 a个2相乘＊b个3相乘。这样，我们只需要去看看x里有几个2就可以得到a，同理，只需要看看x里有几个3就可以得到b。

其实，并不一定用2和3，用任意两个素数也是可以的，有兴趣大家可以去试试。

好，既然已经证明可以，我们来看看代码如何实现，说到代码实现，对我们这些码农们来说不就是顺手敲敲键盘而已嘛，看招！

cons过程定义如下，就是通过2^a * 3^b得到x

(define (cons a b) (* (expt 2 a) (expt 3 b)))

car过程定义如下，就是数x里有几个2

(define (car x) (define (iter counter number-left) (if (= (remainder number-left 2) 0) (iter (+ counter 1) (/ number-left 2)) counter)) (iter 0 x))

cdr过程定义如下，就是数x里有几个3

(define (cdr x) (define (iter counter number-left) (if (= (remainder number-left 3) 0) (iter (+ counter 1) (/ number-left 3)) counter)) (iter 0 x))

总之，对于复合数据的实现，我们可以放开思路，只要是可以将复合数据的构成部分分解出来就可以了。

这时候我们再回去看看我们常见的复合数据结构就觉得很简单了，比如c语言的struct，其实就是在内存区域里连续分配一段空间，将struct的元素逐个堆放在一起就可以了，因为我们知道每个元素的数据类型，所以我们知道每个元素占用多少内存空间，这样我们就可以简单地通过位移量获得不同的元素了。

相比之下，本题使用的复合数据构建方式虽然不是那么高效，但是真的是很有想法。

不过，更有想法的在后面，看看SICP 习题 2.6 吧。