Нахождение продукта каждого из (n-1) подмножеств данного массива
Я сожалею об удалении исходного вопроса, здесь это: у Нас есть сумка или массив 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];
Спасибо.
5 ответов
Если набор очень большой, может быть удобно:
- заранее вычислить произведение P всех элементов, а затем
- для каждый элемент x, получить (n-1) произведение как P / x
Если набор содержит ноль (т. е. P = 0, x = 0), вы должны рассматривать его как особый случай.
РЕДАКТИРОВАТЬ . Вот решение на схеме с учетом ответа andand. Я полный новичок - может ли кто-нибудь помочь мне улучшить следующий код (сделать его более эффективным, более читаемым, более лихорадочным)? (Не стесняйтесь редактировать мой ответ.)
#!/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)))
Set product = 1;
for item in set:
if item index == argument index
ignore
else
product *= item
Если я понимаю ваш вопрос, это тривиальное решение. Это должно быть легко реализовать на любом языке программирования.
Вам необходимо явно рассмотреть три случая:
1) Без нулей: Предварительно вычислить произведение всех элементов и разделить желаемый элемент набора из этого продукта.
2) Один ноль : предварительно вычислить произведение ненулевых элементов. Ответ всегда равен 0, за исключением случая, когда вы удаляете единственный нулевой элемент, и в этом случае это предварительно вычисленное произведение.
3) Более одного нуля: Ответ всегда 0.
Предполагается, что у вас есть тип данных, который может содержать продукты ... то есть вы должны быть осторожны, чтобы ваш продукт не не превышает максимальное значение типа, который вы используете для его хранения.
Для фактической реализации всегда предварительно вычисляйте произведение ненулевых элементов и отслеживайте, сколько там нулей. Если «набор» является динамическим (его значения меняются), вам необходимо обновить продукт и нулевой счетчик. Когда вас просят о конкретном подмножестве продуктов, рассмотрите различные случаи и действуйте соответствующим образом.
Предполагая, что вы можете использовать Python:
Вы можете использовать метод комбинаций из модуля itertools , чтобы лениво генерировать различные подмножества рассматриваемого набора. Получив это, вы можете использовать reduce и operator.mul , чтобы сгенерировать произведение каждого из них.
Вы можете решить эту проблему за 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]"