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

谢谢。

最佳答案

如果集合很大,则可能很方便:

  • 预先计算所有元素的乘积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)))
    

    关于algorithm - 查找给定数组的每个(n-1)个子集的乘积,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/2669831/

    10-10 20:34