7

元の質問を削除して申し訳ありません。ここにあります: n 個の整数のバッグまたは配列があります。(n-1) 個のサブセットのそれぞれの積を見つける必要があります。例えば：

S = {1, 0, 3, 6}
ps[1] = 0*3*6 = 0;
ps[2] = 1*3*6 = 18; 等

話し合いの後、3 つのケースに対処する必要があり、それらを以下に示します。

1. S is a set (contains one zero element)
  for i=1 to n
    if s[i]=0
      sp[i] = s[1] * s[2] * ...* s[i-1] * s[i+1] *.....*s[n]
    else
      sp[i] = 0;

2. S is a bag (contains more than one zero element) 
  for i=1 to n
      sp[i] = 0;

3. S is a set (contains no zero elements)
   product = 1
   for i=1 to n
     product *= s[i];
   for i=1 to n
     sp[i] = product / s[i];

ありがとう。

4

5 に答える 5

13

セットが非常に大きい場合は、次の方法が便利な場合があります。

  • すべての要素の積 P を事前に計算してから、
  • 各要素 x について、(n-1) 積を P/x として取得します。

セットにゼロが含まれている場合 (つまり、P=0、x=0)、特別なケースとして処理する必要があります。

編集。これは、andandの答えを考慮したSchemeのソリューションです。私は完全な初心者です - 誰かが次のコードを改善するのを手伝ってくれませんか? （私の答えを自由に編集してください。）

#!/usr/bin/env guile !#
(use-modules (ice-9 pretty-print))

(define (count-zeros l)
    (cond ((null? l) 0)
          ((= 0 (car l)) (+ 1 (count-zeros (cdr l))))
          (else (count-zeros (cdr l)))))

(define (non-zero-product l)
    (define (non-zero-product-loop l product)
        (cond ((null? l) product)
              ((= 0 (car l)) (non-zero-product-loop (cdr l) product))
              (else (non-zero-product-loop (cdr l) (* (car l) product)))))
    (non-zero-product-loop l 1))

(define (n-1-products l)
    (let ((nzeros (count-zeros l)))
         (cond ((> nzeros 1)
                   (map (lambda (x) 0) l))
               ((= 1 nzeros)
                   (map (lambda (x) (if (= 0 x) (non-zero-product l) 0)) l))
               (else 
                   (map (lambda (x) (/ (non-zero-product l) x)) l)))))

(pretty-print (n-1-products '(1 2 3 4 5)))
(pretty-print (n-1-products '(0 1 2 3 4)))
(pretty-print (n-1-products '(0 1 2 3 0)))
于 2010-04-19T18:27:55.610 に答える
11

次の 3 つのケースを明示的に考慮する必要があります。

1) ゼロなし:すべての要素の積を事前に計算し、その積から目的のセット要素を除算します。

2) 1 つのゼロ: 非ゼロ要素の積を事前に計算します。単一のゼロ要素を削除する場合を除いて、答えは常に 0 です。この場合、それは事前計算された積です。

3) 複数のゼロ: 答えは常に 0 です。

これは、製品を含むことができるデータ型があることを前提としています...つまり、製品を保存するために使用している型の最大値を製品が超えないように注意する必要があります。

実際の実装では、常にゼロ以外の要素の積を事前に計算し、ゼロの数を追跡します。「セット」が動的である (値が変化する) 場合は、製品とゼロ カウントを更新する必要があります。特定のサブセット製品を求められた場合は、さまざまなケースを考慮してそれに応じて行動してください。

于 2010-04-19T19:14:53.460 に答える
2

除算を使用しなくても、追加のスペース (出力配列を数えない)O(N)を使用して、これを で解決できます。これがJavaのアルゴリズムです。O(1)O(N)

static int[] products(int... nums) {
    final int N = nums.length;
    int[] prods = new int[N];
    int pi = 1;
    for (int i = 0; i < N; i++) {
        prods[i] = pi;
        pi *= nums[i];
    }
    int pj = 1;
    for (int j = N-1; j >= 0; j--) {
        prods[j] *= pj;
        pj *= nums[j];
    }
    return prods;
}

//...
System.out.println(
   Arrays.toString(products(1, 2, 3, 4, 5))
); // prints "[120, 60, 40, 30, 24]"

こちらもご覧ください

于 2010-04-22T08:37:53.857 に答える
2 
Set product = 1;
for item in set:
   if item index == argument index
      ignore
   else
      product *= item

あなたの質問を理解できれば、これは簡単な解決策です。どのプログラミング言語でも簡単に実装できるはずです。

于 2010-04-19T18:27:09.473 に答える
0

Python を使用できると仮定します。

モジュールのcombinationsメソッドitertoolsを使用して、問題のセットのさまざまなサブセットを遅延生成できます。それができたら、 と を使用reduceしoperator.mulて、それぞれの製品を生成できます。

于 2010-04-19T18:46:57.300 に答える