리스프 동전 던지기가 리스프에서 순서

Question

헤즈, 나는 (링크를 참조하십시오) 다음을 수행하는 프로그램을 만들 수 있습니다

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

코드가 많은 수의 나무와 함께 작동하지 않으면 어떤 도움이 될 수 있습니다!

Answer 1

이 두 가지 문제가 있습니다 : 함수 head-search2에서

1. , 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))))) 

독자들에게 연습 문제로 남겨 동적 프로그래밍이 더 재 작성. ;)