您當前位置：首頁 > 互聯網 > SICP 習題（2.5）解題總結

SICP 習題（2.5）解題總結

來源：程序員人生發布時間：2014-10-04 08:00:00 閱讀次數：2901次

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 吧。