0

交差に関する以前の投稿 (スキームで 2 つのリストからペアの交差を取得する方法は? ) の続きとして、同じ行に沿ってユニオンの小さなコードを書きました。出力は (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?2 つの引数がまったく同じ objectである場合にのみ true を返します。を使用するequal?か=、数値のみを比較する場合。

2) 再帰があっても、newlist何をしても常に空です。最後の 2 つのケースでは、空のリストを追加しているだけです。

3) これは実際には労働組合ではありません。'(1 2)と'(1 3)なるときの特別な動作を探しています'(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)、共通の最初の要素と合計された 2 番目の要素を含むリストは、両方のセットの残りを共用体に戻した結果に追加されます。

4) 最後の 2 つのステップは、最初のステップと同様のアクションを実行します。最初の要素が小さい方のセットを取り、(cons)2 つのセットを渡した結果に、抽出したばかりのリストを差し引いて、union に戻します。

繰り返しでローカル定義をバインドして最適化できますが、うまくいけば、これにより問題とどこが間違っているかを理解できるようになります。

于 2013-08-08T19:13:06.947 に答える