很抱歉删除了原来的问题,这里是:
我们有一个包含 n 个整数的包或数组,我们需要找到每个 (n-1) 个子集的乘积。例如:
S = {1,0,3,6}
ps[1] = 0*3*6 = 0;
ps[2] = 1*3*6 = 18; ETC。
经过讨论,我们需要处理三种情况,如下所示:
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];
Thanks.
如果集合非常大,可能会方便:
- 预先计算所有元素的乘积 P,然后
- 对于每个元素 x,获得 (n-1) 个乘积作为 P/x
如果集合包含零(即 P=0,x=0),则必须将其作为特殊情况处理。
EDIT。这是Scheme中的一个解决方案,考虑到andand的答案。我是一个完全的初学者 - 有人可以帮助我改进以下代码(使其更高效、更易读、更 lisp)吗? (随意编辑我的答案。)
#!/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)))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)