查找给定数组的每个(n-1)个子集的乘积

Question

我很抱歉删除了原来的问题,这里是:我们有一个包或一组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];

谢谢.

Answer 1

如果该集非常大,则可能方便:

• 事先计算所有元素的乘积P,然后
• 对于每个元素x,获得(n-1)乘积为P/x

如果集合包含零(即P = 0,x = 0),则必须将其作为特殊情况处理.

编辑.这是Scheme中的解决方案,考虑到和答案.我是一个完全的初学者 - 有人可以帮助我改进以下代码(使其更有效,更可读,更多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)))

Answer 2

您需要明确考虑这三种情况:

1)无零:预先计算所有元素的乘积,并从该乘积中划分出所需的集合元素.

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

3)不止一个零: 答案总是0.

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

对于实际实现,始终预先计算非零元素的乘积,并跟踪有多少个零.如果"set"是动态的(其值发生变化),则需要更新产品和零计数.当被要求提供特定的子集产品时,请考虑各种情况并采取相应措施.

Answer 3

Set product = 1;
for item in set:
   if item index == argument index
      ignore
   else
      product *= item

如果我理解你的问题，这就是一个简单的解决方案。它应该很容易用任何编程语言实现。