我想生成最长的子列表的长度。例如,由于子列表(2 (3 (4 5)) (6 7) 8)的长度为4,因此对于列表(1 (2 (3 (4 5)) (6 7) 8) 9),结果将是4。
我尝试过这样做:
(defun len(l)
(cond
((null l) 0)
((atom l) 1)
(t (+ (len(cdr l)) 1))
)
)
(defun lun(l)
(cond
((atom l) 1)
(t(apply #'max (mapcar #' len l)))
)
)对于上面的示例,它返回4,但问题是它只分析子列表的第一级。如果我尝试为列表(1 (2 (3 (4 5 a a a a)) (6 7) 8) 9)解析它,它也会返回4,尽管由于列表(4 5 a a a a),它应该是6,但它仍然只接受列表(2 (3 (4 5 a a a a)) (6 7) 8)。
提前谢谢你。
发布于 2019-01-13 03:35:38
您的输入是列表列表(等)的列表,也称为树。您想要计算构成树的列表之一的最长长度。粗略地说,您需要遍历子树,计算它们各自的最长长度,并将这些长度组合成一个新的最大长度。
函数的第一个草图如下所示,基于LOOP宏(您仍然需要一些工作才能将其转换为完全递归的解决方案):
(defun longest-length (tree)
(loop for subtree in tree maximize (longest-length subtree)))正如上面所解释的,您将问题划分为子问题,通过查找每个子树的最长长度来递归地解决它们,并通过返回每个局部最大值的最大值来组合它们。
但是上面的代码遗漏了一些东西。首先,您需要考虑应该计算树本身的长度:
(defun longest-length (tree)
(max (length tree)
(loop for subtree in tree maximize (longest-length subtree))))此外,当代码到达非cons单元格的项时,它也会失败。您现在必须为树不是cons-cell的基本情况添加代码。特别是,nil被视为一个空列表,而不是一个符号:
(defun longest-length (tree)
(typecase tree
(cons (max (length tree)
(loop
for subtree in tree
maximize (longest-length subtree))))
(null 0)
(t 1)))下面是一个测试:
CL-USER> (longest-length '(1 (2 (3 (4 5 a a a a)) (6 7) 8) 9))
6还可以考虑使用reduce,与apply不同,它对列表(call-argument-limit)中的元素数量没有限制:
(reduce #'max (mapcar ... tree) :initial-value (length tree))https://stackoverflow.com/questions/54162838
复制相似问题