閱讀739 返回首頁    go 阿裏雲 go 技術社區[雲棲]

sicp 4.3.2部分習題

4.38，謎題就有翻譯錯誤，問題更是錯的離譜。原題是這樣的：
Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house
that contains only five floors. Baker does not live on the top floor. Cooper does not live on
the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on
a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's.
Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?

其中說Miller住的比Cooper高，卻翻譯成了Miller住的比Cooper高一層，如果按照這個翻譯來謎題是沒有答案的。
回到4.38，題目是這樣的：
Modify the multiple-dwelling procedure to omit the requirement that Smith and Fletcher do
not live on adjacent floors. How many solutions are there to this modified puzzle?

翻譯卻成了增加Smith和Fletcher不住在相鄰層這個條件，謎題本來就是如此，何來的增加？錯將omit翻譯成了“增加”。
這道題很簡單咯，將
(require (not (= (abs (- smith fletcher)) 1)))
注釋掉即可，答案增加到5個：
> (multiple-dwelling)
((baker 1) (cooper 2) (fletcher 4) (miller 3) (smith 5))
> (amb)
((baker 1) (cooper 2) (fletcher 4) (miller 5) (smith 3))
>  (amb)
((baker 1) (cooper 4) (fletcher 2) (miller 5) (smith 3))
>  (amb)
((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
>  (amb)
((baker 3) (cooper 4) (fletcher 2) (miller 5) (smith 1))

4.39，約束條件的順序肯定是有影響的，能縮小搜索範圍的強約束條件排在前麵，弱約束條件排在後麵，可以減少整體的判斷次數。在DrScheme中，可以啟用profile來分析順序帶來的影響，打開language->R5RS->Show Details，選擇Debugging and Profiling 即可。運行scheme程序，然後在View->Show Profile中查看具體分析結果,在該視圖中將詳細列出各個函數調用的時間和次數。
在沒有調整順序前：
Msec      Calls      Function
40            1               multiple-dwelling
0              1716         require
4              2524          distinct?

說明multiple-dwelling調用了一次，花費了40毫秒，而require和distinct?函數分別被調用了1716次和2524次。
然後我將
(require
     (distinct? (list baker cooper fletcher miller smith)))

這個我認為弱約束條件放到了最後，測試的結果並不讓人滿意：
Msec      Calls      Function
44            1               multiple-dwelling
4              6035         require
0              129          distinct?

並沒有大的提高，甚至反而所下降。猜測問題在於我使用的amb實現是call/cc、宏實現的，待俺完成amb求值器再測試一下。

4.40，題目都提示咯，嵌套let語句,我的解答：
(define (multiple-dwelling2)
  (let ((baker   (amb 1 2 3 4 5)))
     (require (not (= baker 5)))
      (let ((cooper  (amb 1 2 3 4 5)))
        (require (not (= cooper 1)))
        (let ((fletcher (amb 1 2 3 4 5)))
          (require (not (= fletcher 5))) 
          (require (not (= fletcher 1)))
          (require (not (= (abs (- fletcher cooper)) 1)))
          (let ((miller (amb 1 2 3 4 5)))
             (require (> miller cooper))
             (let ((smith   (amb 1 2 3 4 5)))
                (require (not (= (abs (- smith fletcher)) 1)))
                (require (distinct? (list baker cooper fletcher miller smith)))
                (list (list 'baker baker)
                      (list 'cooper cooper)
                      (list 'fletcher fletcher)
                      (list 'miller miller)
                      (list 'smith smith))))))))

profile一下，multiple-dwelling2的調用時間縮小到8毫秒，require和distinct?的調用次數分別降低到了404和129次。


4.42，說謊者謎題，
五個女生參加一個考試，她們的家長對考試結果過分關注。為此她們約定，在給家裏寫信談到考試的時候，每個姑娘都要寫一句真話和一句假話。下麵是從她們的信裏摘抄出來的句子：
Betty : kitty考第二，我隻考了第三
Ethel : 你們應該很高興聽到我考了第一，joan第二
joan :   我考第三，可憐的Ethel墊底
kitty:  我第二，marry隻考了第四
marry: 我是第四，Betty的成績最高。
這五個姑娘的實際排名是什麼？

將題目翻譯成代碼就OK了，說明性編程真是舒坦：
(define (liars-puzzle)
  (let ((betty (amb 1 2 3 4 5))
        (ethel (amb 1 2 3 4 5))
        (joan (amb 1 2 3 4 5))
        (kitty (amb 1 2 3 4 5))
        (marry (amb 1 2 3 4 5)))
    (require
       (distinct? (list betty ethel joan kitty marry)))
    (require (or (= kitty 2) (= betty 3)))
    (require (not (and (= kitty 2) (= betty 3))))
    (require (or (= ethel 1) (= joan 2)))
    (require (not (and (= ethel 1) (= joan 2))))
    (require (or (= joan 3) (= ethel 5)))
    (require (not (and (= joan 3) (= ethel 5))))
    (require (or (= kitty 2) (= marry 4)))
    (require (not (and (= kitty 2) (= marry 4))))
    (require (or (= marry 4) (= betty 1)))
    (require (not (and (= marry 4) (= betty 1))))
    (list (list 'betty betty)
          (list 'ethel ethel)
          (list 'joan joan)
          (list 'kitty kitty)
          (list 'marry marry))))

答案是：
((betty 3) (ethel 5) (joan 2) (kitty 1) (marry 4))

4.43.也很有趣的題目，遊艇迷題，
   Mary Ann Moore的父親有一條遊艇，他的四個朋友Colonel Dowing、Mr.Hall、Sir Barnacle Hood和Dr.Parker也各有一條。這五個人都有一個女兒，每個人都用另一個人的女兒的名字來為自己的遊艇命名。Sir Barnacle的遊艇叫Gabrielle，Mr.Moore擁有Lorna，Mr.Hall的遊艇叫Rosalind，Melissa屬於Colonel Downing（取自Sir Barnacle的女兒的名字），Garielle的父親的遊艇取的是Dr.Parker的女兒的名字。請問，誰是Lorna的父親。

先說下結果，Lorna的父親是Downing。
具體解答如下,先定義輔助過程：
(define (father yacht daughter)
     (cons yacht daughter))
(define (yacht father)
  (car father))
(define (daughter father)
  (cdr father))

然後翻譯題目為代碼即可，暫不考慮效率問題：
(define (yacht-puzzle)
  (let ((moore (father 'lorna 'mary))  ;;Mr.Moore
        (downing (father 'melissa (amb 'mary 'melissa 'gabrielle 'rosalind 'lorna))))  ;;Colonel Downing
    (require (not (equal? (yacht downing) (daughter downing))))
    (let ((hall (father 'rosalind (amb 'mary 'melissa 'gabrielle 'rosalind 'lorna))))  ;;Mr.Hall
       (require (not (equal? (yacht hall) (daughter hall))))
       (let ((barnacle (father 'gabrielle 'melissa))   ;;Sir Barnacle Hood
             (parker (father (amb 'mary 'melissa 'gabrielle 'rosalind 'lorna) (amb 'mary 'melissa 'gabrielle 'rosalind 'lorna))))         ;;Dr.Parker
         (require (not (equal? (yacht parker) (daughter parker))))
         (let ((gabrielle-father (amb moore downing hall barnacle parker))) ;;Garielle's Father
           (require (equal? (daughter gabrielle-father) 'gabrielle))   
           (require (equal? (yacht gabrielle-father) (daughter parker)))
           (require (distinct? (map daughter (list moore downing hall barnacle parker))))
           (require (distinct? (map yacht (list moore downing hall barnacle parker))))
           (list 
              (list 'moore (yacht moore) (daughter moore))
              (list 'downing (yacht downing) (daughter downing))
              (list 'hall (yacht hall) (daughter hall))
              (list 'barnacle (yacht barnacle) (daughter barnacle))
              (list 'parker (yacht parker) (daughter parker))))))))


運行(yacht-puzzle)的結果為：
((moore lorna mary) (downing melissa lorna) (hall rosalind gabrielle) (barnacle gabrielle melissa) (parker mary rosalind))

三元組：父親名、遊艇名、女兒名，因此lorna的父親是Downing。Garielle的父親是Mr.Hall，Mr.Hall的遊艇名叫做Rosalind，正是Dr.Parker的女兒名字。

延伸題目，如果沒有Mary Ann姓Moore這個條件，答案將有三個，分別是：
((moore lorna mary) (downing melissa lorna) (hall rosalind gabrielle) (barnacle gabrielle melissa) (parker mary rosalind))
((moore lorna gabrielle) (downing melissa rosalind) (hall rosalind mary) (barnacle gabrielle melissa) (parker mary lorna))
((moore lorna lorna) (downing melissa mary) (hall rosalind gabrielle) (barnacle gabrielle melissa) (parker mary rosalind))

文章轉自莊周夢蝶  ，原文發布時間

最後更新：2017-05-18 11:02:04

  上一篇：go  降低JRuby的內存占用的可能方法
  下一篇：go  Ambari 架構（四）Ambari Agent 架構