tree - Lisp 抛硬币正面序列

Question

在 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 = heads 的序列

(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 ))))

最后一个函数将这两者结合起来

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

代码不适用于大量的树，任何帮助都会很棒!

Answer 1

有两个问题:

1. 在函数 head-search2 中，cond 的第二个子句，对 head-search2 的第一次递归调用未能传播检查。

2. 相同的子句，第二个递归调用获取(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)))))

为动态规划进一步重写这个留给读者作为练习。 ;)