0

我正在尝试创建一个函数，该函数将返回列表中的偶数元素。

例如：

(evens '(a b c d))

应该返回

(b d)

下面的代码似乎适用于包含奇数个元素的列表，但如果我给它一个包含偶数个元素的列表，那就不正确了。

例如：

(evens '(a b c d e))

将返回

(b d)

但：

(evens '(a b c d))

将返回

(a c)

有什么想法吗？

将我的代码更改为：

(DEFINE (evens lis)
(cond
    ((null? lis) '())   
    (else (cons (cadr lis) (evens (cdr lis))))
    ))

得到一个错误，说传递给安全车的对象不是一对？

4

4 回答 4

0

您的代码几乎没有遗漏检查和一些不正确的逻辑。

(define (evens lis)
(cond
    ((null? lis) '())   
    ((eq? (cdr lis) '()) '()) ;missing condition
    (else (cons (cadr lis) (evens (cddr lis)))))) ; it is cddr not cdr
于 2012-11-14T09:47:05.590 回答
0

问题是，如果您的列表有偶数个元素，则modulo分支匹配并且您从列表cons的开始car...因此在您的示例中，您得到a，依此类推。

更重要的是，你不需要使用length这个函数......而且你不应该：因为length在列表的长度上需要线性时间，evens现在需要二次时间。

建议：您的程序应该“记住”它在每个递归步骤中是否位于“奇数”或“偶数”位置......你怎么能这样做（有几种方法）？

于 2012-11-14T05:49:12.567 回答
0

在过去的几天里，同样的问题被一次又一次地问到。这次我会直接回答，直截了当：

(define (evens lst)
  (if (or (null? lst)             ; if the list is empty 
          (null? (cdr lst)))      ; or the list has a single element
      '()                         ; then return the empty list
      (cons (cadr lst)            ; otherwise `cons` the second element
            (evens (cddr lst))))) ; and recursively advance two elements

这是首先进行一些错误检查的方法：

(define (find-evens lst)
  (if (list? lst)
      (evens lst)
      (error "USAGE: (find-evens [LIST])")))
于 2012-11-14T11:11:38.197 回答
0

我将通过注释示例回答您的问题，希望您能真正学到一些东西，而不是仅仅获得有效的代码。实际上，假设您不熟悉方案，那么查看几段代码可能会更有启发性。

您的原始定义如下所示：

(define (evens lis)
  (cond (;; Check: Recursion stop condition
         (null? lis)
         '())
        (;; Wrong: Calling length at each step => O(n^2)
         ;; Wrong: Assuming even element if list has even number of elements
         (= (modulo (length lis) 2) 0) 
         ;; Wrong: Recursing with the rest of the list, you'll get odds
         (cons (car lis) (evens (cdr lis)))) 
        (else
         ;; Wrong: Recursing with the rest of the list with cdr, you'll get odds
         (evens (cdr lis)))))

之后，您已编辑问题以将其更新为如下内容：

(define (evens lis)
  (cond (;; Check: Recursion stop condition
         (null? lis)
         '())   
        (else
         ;; Check: Building list with second element
         ;; Wrong: If lis only has 1 element,
         ;;        (cdr lis) is null and (car (cdr list)) is an error.
         (cons (cadr lis)
               ;; Wrong: Recursing with cdr, you'll get odds
               (evens (cdr lis))))))

一个解决方案是检查列表是否至少有第二个元素：

(define (evens lis)
  (cond (;; Check: Recursion stop condition 1
         (null? lis)
         '())
        (;; Check: Recursion stop condition 2: list of length = 1
         (null? (cdr lis))
         '())
        (else
         ;; Check: Building list with second element
         ;; The previous cond clauses have already sorted out
         ;; that lis and (cdr lis) are not null.
         (cons (cadr lis)
               ;; Check: Recurse "the rest of the rest" of lis with cddr
               (evens (cddr lis)))))

练习：使用if和or简化此解决方案，使其只有 2 个分支。

于 2012-11-14T11:16:11.277 回答