0

整数のリスト lst を消費し、lst の他の 2 つの要素の合計である lst の一意の要素のみを (順不同で) 含むリストを生成する関数を作成する必要があります。

元：

(sumfilt '(1 4 7 5 17 11)) => '(11 5)
(sumfilt '(5 4 7 5 9 1 10)) => '(5 9 10)

誰かがこれで私を助けてくれますか? また、これを可能な限り効率的にしたい

4

2 に答える 2

1

これを解決するヒントをお伝えします。最初の単純なアプローチは、入力リストのサイズ 2 の各組み合わせの合計のリストを事前に計算し、入力リストのどの要素が合計のリストに属しているかをテストすることです。最後のステップとして、重複を削除します。

指定されたサイズのリストcombのすべての可能な組み合わせを計算する手順が存在すると仮定すると(それを探すか、自分で実装してください!)、上記で説明した素朴なアルゴリズムを実装して、問題に対する非常に短い答えを示します。これで十分なはずです。 1000 要素程度のリストの場合:lstm

(require srfi/26) ; I like to use `cut`, but `lambda` would serve just as well

(define (comb lst m)
  <???>) ; ToDo: generate all m-size combinations of lst

(define (sumfilt lst)
  (let ((sums (map (cut apply + <>) (comb lst 2))))
    (remove-duplicates (filter (cut member <> sums) lst))))

または同等にcute、事前計算された合計のリストを 1 回だけ評価するために使用します。

(define (sumfilt lst)
  (remove-duplicates
   (filter (cute member <> (map (cut apply + <>) (comb lst 2))) lst)))

より効率的なアプローチには、サブセット合計問題のいくつかのバリエーションが含まれ、動的計画法によって解決されます。ただし、そのような解決策は、書くのがより複雑になります。いずれにせよ、答えをテストすることを忘れないでください。

(sumfilt '(1 4 7 5 17 11)) 
=> '(5 11)

(sumfilt '(5 4 7 5 9 1 10)) 
=> '(5 9 10)
于 2013-07-03T13:46:54.803 に答える