0

继续我之前关于交集的帖子（如何从方案中的两个列表中获取对的交集？），我已经按照相同的思路编写了一个用于联合的小代码。输出应该类似于：(union '((1 2)(2 1)) '((1 3)(3 4))) -- '((1 5)(2 1)(3 4))。但是，我的程序的输出并不完全是我想要的。我认为我的递归或条件需要一些指导。请帮忙。谢谢。

(define union
  (lambda (set1 set2)
    (let ((newlist '()))
      (cond ((null? set1) set2)
            ((null? set2) set1)
            ((eq? (caar set1) (caar set2))
             (append newlist (cons (caar set1) (+ (cadr (car set1))(cadr (car set2))))))
            (else 
             (if (> (caar set1) (caar set2))(append newlist (car set1)) (union (cdr set1) set2))
             (union set1 (cdr set2)))))))
4

1 回答 1

1

1)eq?仅当两个参数是完全相同的 object时才返回 true 。你会想要使用equal?，或者=如果你只是比较数字。

2）即使你的递归，newlist无论你做什么，它都是空的。您只是在最后两种情况下附加了一个空列表。

3）这实际上不是工会。您正在寻找一些特殊的行为 when'(1 2)和'(1 3)become '(1 5)。

然而，这正是你想要的。我们的操作基于您的列表已预先排序的假设，考虑到您已投入，<并且>各个集合中没有重复项（例如'((1 2) (1 2) (3 4))：

(define (union set1 set2)
  (cond [(empty? set1) set2]
        [(empty? set2) set1]
        [(equal? (car set1) (car set2)) (cons (car set1) 
                                              (union (cdr set1) (cdr set2)))]
        [(= (caar set1) (caar set2)) (cons (list (caar set1)
                                                 (+ (cadar set1)
                                                    (cadar set2)))
                                           (union (cdr set1) (cdr set2)))]
        [(< (caar set1) (caar set2)) (cons (car set1) (union (cdr set1)
                                                             set2))]
        [else (cons (car set2) (union set1
                                      (cdr set2)))]))

逻辑：

1）一个或另一个是空的吗？如果是，则返回适当的集合。

2) 一个集合中的第一个列表是否等于另一个集合中的第一个列表？如果是这样，(cons)则共享列表将两个集合的其余部分传递回联合的结果。

3) 两个集合的第一个列表中的第一个元素是否相等？如果是这样，(cons)则将包含公共第一个元素和第二个元素之和的列表放在将其余两个集合传递回联合的结果中。

4) 最后两步执行与第一步类似的操作。将具有较小第一个元素的集合(cons)放在传递两个集合的结果上，减去您刚刚提取的列表，然后返回并集。

您可以通过在重复上绑定本地定义进行优化，但希望这可以让您了解您的问题以及您可能出错的地方。

于 2013-08-08T19:13:06.947 回答