最长的公共子列表 [英] Longest common sublist

问题描述

在尝试编写Scheme中最长的公共子列表问题的解决方案时，我很难弄清楚到目前为止发生了什么问题。我认为这是正确的想法，在担心多项式时间之前，我只是试图找到一个可以工作的人。

While trying to write a solution to the longest common sublist problem in Scheme, I'm having trouble figuring out what is wrong with what I have so far. I think it's the right idea and before worrying about polynomial time I'm just trying to get one that works at all. I haven't written in a functional language before and the syntactic differences can make things a little harder at first.

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

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

Is this on the right track? What's wrong with it? Any help is appreciated, thank you.

推荐答案

(if (not (null? lcs)) lcs

检查 lcs （这是一个函数）是空列表，如果不是（总是这样，因为函数不是一个列表），你返回函数本身。

Here you're checking whether lcs (which is a function) is the empty list. If it isn't (which is always the case because a function is not a list), you return the function itself.

我假定你的意思是调用函数 lcs 并检查结果是否为空列表。如果函数需要参数（ lcs ），则需要在调用该函数时指定这些参数。

I assume what you meant to do was to call the function lcs and check whether the result was the empty list. To call a function, you need to surround the function in parentheses. Further if the function takes arguments (which lcs does), you need to specify those arguments when calling the function.

我不清楚这个如果应该完成，并且据我所知，没有必要这样做，所以只要将它删除即可。

It is not clear to me what this if is supposed to accomplish and as far as I can tell, there's no need for it, so just remove it.

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

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

cadr returns the second element of a list, so here you're returning the list whose second element is greater. Given that your goal is to find the longest sublist, this makes no sense. You should be returning the list whose length is greater. To do this replace the condition with

(> (length a) (length b))

除了这些逻辑错误之外，您还有一个小的语法错误：

In addition to those logic errors, you have a small syntax error:

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

这里你用一个参数（这是一个错误）调用 cons ，然后调用（lcs（cdr lst1 ）（cdr lst2））作为列表的其他部分。因为你显然希望（lcs（cdr lst1）（cdr lst2））成为 cons 的第二个参数，只是在 car lst1 后移除第二个结束符。

Here you're calling cons with one argument (which is an error) and then calling (lcs (cdr lst1) (cdr lst2)) as the else-part of the list. Since you obviously intended (lcs (cdr lst1) (cdr lst2)) to be the second argument to cons, just remove the second closing paren after car lst1.

这篇关于最长的公共子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！