Algorithmes Gloutons

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}
  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.
  2. 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.
  3. 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 Mostafa Sedoki
Professeur d'Informatique dans les CPGE

Cours Similaires :