7

很抱歉删除了原来的问题，这里是：我们有一个包或一个包含 n 个整数的数组，我们需要找到每个 (n-1) 个子集的乘积。例如：

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

经过讨论，我们需要处理这三种情况，如下所示：

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），则必须将其作为特例处理。

编辑。这是Scheme中的一个解决方案，考虑到andand的答案。我是一个完整的初学者 - 有人可以帮助我改进以下代码（使其更高效、更易读、更 lisp-ish）吗？（随时编辑我的答案。）

#!/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

您需要明确考虑以下三种情况：

1）无零：预先计算所有元素的乘积，并从该乘积中划分出所需的集合元素。

2）一零：预先计算非零元素的乘积。答案始终为 0，除非您删除单个零元素，在这种情况下，它是预先计算的产品。

3) 多于一个零： 答案总是 0。

这假设您有一个可以包含产品的数据类型......也就是说，您需要注意您的产品不超过您用于存储它的类型的最大值。

对于实际实现，始终预先计算非零元素的乘积并跟踪有多少个零。如果“集合”是动态的（其值发生变化），您需要更新产品和零计数。当被要求提供特定的子产品时，请考虑各种情况并采取相应的行动。

于 2010-04-19T19:14:53.460 回答
2 
Set product = 1;
for item in set:
   if item index == argument index
      ignore
   else
      product *= item

如果我理解你的问题，这是微不足道的解决方案。它应该很容易用任何编程语言实现。

于 2010-04-19T18:27:09.473 回答
2

您可以在 中解决这个问题O(N)，使用O(1)额外的空间（不计算O(N)输出数组），甚至不使用除法。这是Java中的算法。

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 回答
0

假设您可以使用 Python：

您可以使用模块中的combinations方法itertools懒惰地生成相关集合的各种子集。一旦你有了它，你就可以使用reduce和operator.mul生成每一个的产品。

于 2010-04-19T18:46:57.300 回答