Lisp的擲硬幣對決序列

在Lisp，我要創建一個程序，執行以下操作（請訪問鏈接）：Lisp的擲硬幣對決序列

http://uva.onlinejudge.org/external/103/10328.html

我有一些代碼來創建樹

(defun head-tail (n &optional (total 0)) 
    (if (< total n) 
     (list(cons 'H (head-tail n (1+ total))) 
      (cons 'T (head-tail n (1+ total)))) 
    nil))

然後編碼以檢查H =頭的序列

(defun head-search2 (tree n &optional (total 0) (check 0)) 
    (cond ((null tree) 
     check) 
     ((listp (first tree)) 
     (+ (head-search2 (first tree) n total) 
      (head-search2 (rest tree) n total check))) 
     ((and (eq (first tree) 'H) 
       (>= (1+ total) n)) 
     (head-search2 (rest tree) n (1+ total) 1)) 
     ((and (eq (first tree) 'H) 
       (< (1+ total) n)) 
     (head-search2 (rest tree) n (1+ total) check)) 
     ((eq (first tree) 'T) 
     (head-search2 (rest tree) n 0 check))))

和最後一個函數t o結合這兩個

(defun head-check (m n) 
    (head-search2(head-tail m) n))

該代碼不適用於大量的樹木，任何幫助將是偉大的！

來源

2012-03-08 Drakoumel

「不適用於大量樹木」是什麼意思？ – zmccord 2012-03-08 13:48:25

就像當我用它爲3的樹尋找2的序列它有一個正確的結果，但對於樹= 4和序列= 2不工作它輸出7當它應該輸出8和樹= 6 n = 2給出31未讀的43. @zmccord – Drakoumel 2012-03-08 13:50:07

您指向的網頁沒有說清楚。你實際上沒有進行硬幣投擲實驗（就像使用僞隨機數發生器一樣）。你正在處理所有的'（expt 2 n）'頭部和尾部的可能組合，並尋找H的序列。這純粹是一個組合問題，類似於：從0到2^N的許多N位二進制數包含至少K個零位的連續序列。對？ – Kaz 2012-03-08 18:41:50

有兩個問題：

在功能head-search2的cond秒條款，以head-search2第一遞歸調用失敗來傳播check下來。
同子句，第二次遞歸調用獲得(rest tree)作爲第一個參數，這會導致額外的列表層;應該是(second tree)。

這就是說，你遍歷樹的兩次：第一次在構造時，然後計算它。隨着一點點的思維縝密，可以節省大量的工作遍歷它只有一次，沒有明確構建它：

(defun count-n-runs (m n &optional (k n)) 
    "Count all possible binary sequences with n consecutive 1s." 
    (cond ((= 0 n) (expt 2 m)) 
     ((= 0 m) 0) 
     ((+ (count-n-runs (1- m) k k) 
      (count-n-runs (1- m) (1- n) k)))))

重寫此進一步進行動態編程就留給讀者自己練習。 ;）

來源

2012-03-08 21:35:30 huaiyuan

生病看看它，非常感謝：D @ huaiyuan – Drakoumel 2012-03-09 15:01:45

Lisp的擲硬幣對決序列

回答

相關問題