LISP练习器

Question

​

​

我试着做这样的练习：

(defconstant *family-tree* 
  '((father Barack Pat) (mother Michelle Pat)
    (father GeorgeW Peter) (mother Laura Peter)
    (father GeogerH James (mother Barbara James) 
    (father Bill Jane) (mother Hillary Jane) 
    (father James Mark) (mother Jane Mark) 
    (father Peter Mary) (mother Pat Mary) 
    (father Mark John) (mother Mary John))))

但我不确定这是不是最好的方法。此外，我不知道如何创造“父母”和“祖父母”的功能。我真的很感谢你的帮助。谢谢

Answer 1

您可能需要从婴儿步开始：

(defun make-person (name &optional father mother)
  (cons name (cons father mother)))

现在，您可以创建您的家谱：

(defconstant *family-tree* 
  (make-person 'john
     (make-person 'mark 
       (make-person 'james
         ...)
       (make-person 'jane
         ...))
     (make-person 'mary
       (make-person ...)
       (make-person ...))))

在树中找到一个人需要递归：

(defun find-person (tree name)
  (if (eq (car tree) name)
      tree
      (or (find-person (cadr tree) name)
          (find-person (cddr tree) name))))

实际上，您可以将cadr替换为father-tree，cddr替换为mother-tree。(还可以定义tree-name来调用car)。

现在找到父母和祖父母应该很容易：

(defun parents (tree name)
   (let ((person (find-person tree name)))
     (list (caadr person) ; or (tree-name (tree-father person))
           (caddr person)))) ; or ...

Answer 2

您已经构造了一个关联记录列表，这是解决此问题的有效方法。这类似于没有索引的数据库表的结构。您可以使用树结构以及回溯搜索，但这是更复杂的实现，对于一小部分结果，效率将不会有很大的提高。

此外，考虑到这个问题不需要你单独查找父母，而只需要找父母，那么像这样把父母双方都记录下来可能会更有效

(defconstant *family-tree*
  '((john mark mary)
    (mark james jane)
    (james georgeh barbara)
    ; and so on ...
   ))

给定这种结构，让我们编写一些访问函数

(defun child (record)
  "This function returns the child in a family tree record. 
    For example (child '(john mark mary)) returns JOHN"
    (car record))

(defun parents (record)
  "This function returns the parents in a family record.
   For example (cdr '(john mark mary)) returns (MARK MARY)"
   (cdr record))

(defun find-record (family-tree person)
  "This function returns the record of which PERSON is the CHILD.
   For example (find-record 'john '((mark james jane) (john mark mary))) 
   returns (JOHN MARK MARY)"
  (find-if (lambda (record) (eql (child record) person)) family-tree))

现在，使用这些访问器，我们可以编写父函数。

(defun parents (family-tree person)
  (parents (find-record family-tree person)))

现在要找到祖父母，你需要为每个父母找到父母。

(defun grandparents (family-tree person)
    (apply #'append
           (mapcar (lambda (parent) (parents family-tree parent)
                   (parents family-tree person))))

最后一个函数有点复杂，让我们来解释一下。为了找到祖父母，你需要先找到你要找的人的父母，这是最底线的(parents family-tree person)。这将导致父母列表，因此对于该列表中的每个家长，我们需要找到他们的父母(父==祖父母的父)，因此我们使用mapcar对每个结果调用(parent family-tree parent)。最后，我们将得到一个由2个列表组成的列表，因此我们需要将它们合并到一个列表中。