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