Последовательность Бросков Голов Лисп - PullRequest
Новая
       7

Последовательность Бросков Голов Лисп

1 голос
/ 08 марта 2012

В Лиспе мне нужно создать программу, которая выполняет следующее (перейдите по ссылке):

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

и последней функции для объединения этих двух 

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

Код не работает с большим количеством деревьевлюбая помощь будет отличной!

1 Ответ

1 голос
/ 09 марта 2012

Есть две проблемы:

  1. В функции head-search2, второе предложение cond, первый рекурсивный вызов head-search2 не может передать check вниз.

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

Переписать это далее для динамического программирования оставлено в качестве упражнения для читателя. ;)

...