Sous-ensemble de produits minimum d'un tableau
Problème ! Étant donné un tableau a, nous devons trouver le produit minimum possible avec le sous-ensemble d'éléments présents dans le tableau. Le produit minimum peut être un seul élément aussi.
Exemple :
a[] = { -1, 1, -2, -2, 3}
-12 ( -1 * 1 * -2 * -2 * 3 )
a[] = { -1, 0 }
-1 {-1}
-12 ( -1 * 1 * -2 * -2 * 3 )
a[] = { -1, 0 }
-1 {-1}
- S'il y a un nombre pair de nombres négatifs et pas de zéros, le résultat est le produit de tous sauf le plus grand nombre négatif de valeur.
- S'il y a un nombre impair de nombres négatifs et pas de zéros, le résultat est simplement le produit de tous.
- S'il y a des zéros et des positifs, pas de négatifs, le résultat est 0. Le cas exceptionnel est quand il n'y a pas de nombre négatif et tous les autres éléments positifs alors notre résultat devrait être le premier nombre minimum positif.
import math
def minProduit(a, n):
if (n == 1):
return a[0]
max_neg = -math.inf
min_pos = math.inf
cpt_neg = 0
cpt_zero = 0
prod = 1
for i in range(0, n):
# Ignorer si zero
if (a[i] == 0):
cpt_zero = cpt_zero + 1
continue
# compter le nombre des valeurs négatives et calcluer le max
if (a[i] < 0):
cpt_neg = cpt_neg + 1
max_neg = max(max_neg, a[i])
# stocker le nombre postif minimum du tableau
if (a[i] > 0):
min_pos = min(min_pos, a[i])
prod = prod * a[i]
# tous zero ou négatifs
if (cpt_zero == n or (cpt_neg == 0 and cpt_zero > 0)):
return 0
# tous positifs
if (cpt_neg == 0):
return min_pos
# S'il y a un nombre pair de nombres négatifs et que cpt_neg n'est pas 0
if ((cpt_neg & 1) == 0 and cpt_neg != 0):
# Sinon, le résultat est le produit de tous
# les non-zéros divisé par la valeur maximale négative.
prod = int(prod / max_neg)
return prod
# Tester la fonction
a = [-1, 1, -2, -2, 3]
n = len(a)
print(minProduit(a, n))
-12
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.
