最长的公共子列表

Question

在尝试编写Scheme中最长的公共子列表问题的解决方案时，我很难弄清楚到目前为止我有什么问题。我认为这是正确的想法，在担心多项式时间之前，我只是试图找到一个可以工作的人。我之前没有写过功能语言，句法上的差异可能会让事情变得更加困难。

(define (lcs lst1 lst2) 
(if (or (null? lst1) (null? lst2)) '() 
     (if (not (null? lcs)) lcs 
      (if (equal? (car lst1) (car lst2)) 
       (cons (car lst1))(lcs (cdr lst1) (cdr lst2))) 
      (let ((a (lcs (cdr lst1) lst2)) 
       (b (lcs lst1 (cdr lst2)))) 
      (if (> (cadr a) (cadr b)) a b))))) 

这是正确的轨道吗？它出什么问题了？ 任何帮助表示赞赏，谢谢。

Answer 1

(if (not (null? lcs)) lcs 

在这里，我们检查lcs（这是一个功能）是否是空列表。如果不是（总是这样，因为一个函数不是一个列表），你可以返回函数本身。

我假设你的意思是调用函数lcs并检查结果是否为空列表。要调用函数，您需要将函数放在括号中。此外，如果该函数使用参数（其中lcs确实），则需要在调用该函数时指定这些参数。

我不清楚这if应该完成什么，据我所知，没有必要这样做，所以只需将其删除即可。

(if (> (cadr a) (cadr b)) a b) 

cadr返回一个列表的第二个元素，所以在这里你返回第二个元素是更大的名单。鉴于你的目标是找到最长的子列表，这是没有意义的。您应该返回长度更长的列表。与

(> (length a) (length b)) 

除了这些逻辑错误做这个替换的条件下，你有一个小的语法错误：

(cons (car lst1)) (lcs (cdr lst1) (cdr lst2))) 

在这里，我们有一个说法叫cons（这是一个错误）然后调用(lcs (cdr lst1) (cdr lst2))作为列表的其他部分。由于您明显打算将(lcs (cdr lst1) (cdr lst2))作为cons的第二个参数，只需在car lst1之后删除第二个关闭参数即可。