Programme JavaScript pour le sous-ensemble minimum de produits d'un tableau

Le programme JavaScript pour un sous-ensemble minimum de produits d'un tableau est un problème courant qui se pose dans le domaine de l'informatique et de la programmation. L'énoncé du problème nous oblige à trouver le plus petit produit pouvant être obtenu à partir de n'importe quel sous-ensemble des tableaux donnés.

Le sous-ensemble de produit minimum d'un tableau est le sous-ensemble d'éléments du tableau qui donne le plus petit produit possible. Il existe plusieurs algorithmes qui peuvent être utilisés pour identifier ce sous-ensemble, notamment la programmation dynamique, les algorithmes gloutons et le branchement et la liaison. Le choix de l'algorithme dépend des contraintes et spécifications spécifiques du problème à résoudre.

Dans ce tutoriel, nous aborderons différentes façons de résoudre ce problème à l'aide du langage de programmation JavaScript. Nous présenterons les méthodes algorithmiques de base et leur implémentation à l'aide d'extraits de code JavaScript. À la fin de ce didacticiel, les lecteurs auront une compréhension claire de l'énoncé du problème et des différentes manières de le résoudre à l'aide de JavaScript.

Énoncé du problème

Étant donné un tableau d'entiers, nous devons trouver le sous-ensemble de produits minimum du tableau. Le sous-ensemble produit d’un tableau est défini comme le produit de tout sous-ensemble du tableau.

Par exemple,

Considérons le tableau [2, 3, -1, 4, -2].

Le sous-ensemble de produits de ce tableau est

[2], [3], [-1], [4], [-2], [2, 3], [2, -1], [2, 4], [2, -2], [3, -1], [3, 4], [3, -2], [-1, 4], [-1, -2], [4, -2], [2, 3, -1], [2, 3, 4], [2, 3, -2], [2, -1, 4], [2, -1, -2], [2, 4, -2], [3, -1, 4], [3, -1, -2], [3, 4, -2], [-1, 4, -2], and [2, 3, -1, 4, -2]. 

Le sous-ensemble de produits minimum de ce tableau est [-2].

Discutons maintenant des différentes approches algorithmiques pour résoudre cet énoncé de problème et sélectionnons l'algorithme le plus approprié.

Algorithme

Le choix de l'algorithme dépend des contraintes spécifiques et des prérequis du problème.

Algorithme gourmand - L'algorithme glouton est une méthode courante pour trouver le sous-ensemble de produits minimum d'un tableau. Le concept de base est de commencer par un élément initial du tableau et d'ajouter l'élément suivant au sous-ensemble uniquement lorsqu'un produit plus petit est généré. Bien que l’algorithme glouton soit simple et facile à mettre en œuvre, il ne fournit pas nécessairement une solution optimale et ses performances peuvent être considérablement lentes pour les grands tableaux.

Programmation dynamique - La programmation dynamique est un autre algorithme utilisé pour résoudre ce problème. Il divise le problème en sous-problèmes plus petits et résout chaque sous-problème en une seule fois, en utilisant la solution du sous-problème plus petit pour déterminer la solution du sous-problème plus vaste. Cette approche permet d'économiser beaucoup de temps et d'espace. Bien que la programmation dynamique puisse garantir une solution optimale, sa mise en œuvre peut s’avérer plus complexe qu’un algorithme glouton.

Algorithme de branchement et de liaison - Une autre façon d'identifier le sous-ensemble de produits minimum d'un tableau est l'algorithme de branchement et de liaison. Cela nécessite d’explorer de multiples possibilités en ramifiant et en limitant la recherche pour ne considérer que des solutions valables. Cet algorithme garantit une solution optimale et peut être plus rapide que d’autres algorithmes pour des scénarios spécifiques. Néanmoins, sa mise en œuvre peut être plus complexe et nécessiter plus de ressources en temps et en espace que d’autres algorithmes.

En résumé, une approche simple nécessite de générer tous les sous-ensembles, de calculer le produit de chaque sous-ensemble, puis de renvoyer le produit minimum.

Une meilleure solution doit prendre en compte les faits suivants.

• Étape 1 - Dans le cas où il n'y a pas de zéros et que les nombres négatifs sont pairs, le produit de tous les éléments sauf le plus grand nombre négatif donnera le résultat.

• Étape 2 - S'il n'y a pas de zéros et que les nombres négatifs sont impairs, le produit de tous les éléments donnera le résultat.

• Étape 3 - Si zéro existe et est complètement positif, le résultat est 0. Cependant, dans le cas particulier où il n’y a pas de nombres négatifs et où tous les autres éléments sont positifs, la réponse doit être le plus petit nombre positif.

Essayons maintenant de comprendre l'approche ci-dessus avec un exemple d'implémentation de l'énoncé du problème à l'aide de JavaScript.

Exemple

Le programme compte d'abord le produit des nombres négatifs, des zéros, des nombres négatifs maximum, des nombres positifs minimum et des nombres non nuls. Il applique ensuite des règles basées sur le comptage des nombres négatifs et des zéros pour renvoyer le sous-ensemble de produits minimum du tableau. La complexité temporelle du programme est O(n) et l'espace auxiliaire est O(1).

Entrée 1 : a[] = { -1, -1, -2, 4, 3 } ;

Résultat attendu : le sous-ensemble minimum est [-2, 4, 3] et le produit minimum est -24.

Entrée 2 : a[] = { -1, 0 } ; n = 2

Résultat attendu : le sous-ensemble minimum est [-1], le produit minimum est -1.

function minProductSubset(a, n) {
   if (n === 1) {
      return [a[0], a[0]];
   }
   let negmax = Number.NEGATIVE_INFINITY;
   let posmin = Number.POSITIVE_INFINITY;
   let count_neg = 0, count_zero = 0;
   let subsets = [[]];  
   for (let i = 0; i < n; i++) {
      if (a[i] === 0) {
         count_zero++;
         continue;
      }
      if (a[i] < 0) {
         count_neg++;
         negmax = Math.max(negmax, a[i]);
      }
      if (a[i] > 0 && a[i] < posmin) {
         posmin = a[i];
      }
      const subsetsLength = subsets.length;
      for(let j = 0; j < subsetsLength; j++){
         const subset = [...subsets[j], a[i]];
         subsets.push(subset);
      }
   }
   if (count_zero === n || (count_neg === 0 && count_zero > 0)) {
      return [0, 0];
   }
   if (count_neg === 0) {
      return [posmin, posmin];
   }
   const negativeSubsets = subsets.filter(subset => subset.reduce((acc, cur) => acc * cur, 1) < 0);
   let minSubset = negativeSubsets[0];
   let minProduct = minSubset.reduce((acc, cur) => acc * cur, 1);
   for (let i = 1; i < negativeSubsets.length; i++) {
      const product = negativeSubsets[i].reduce((acc, cur) => acc * cur, 1);
      if (product < minProduct) {
         minSubset = negativeSubsets[i];
         minProduct = product;
      }
   }  
   return [minSubset, minProduct];
}
let a = [-1, -1, -2, 4, 3];
let n = 5;
const [minSubset, minProduct] = minProductSubset(a, n);
console.log(`The minimum subset is [ ${minSubset.join(', ')} ] and the minimum product is ${minProduct}.`);

Conclusion

Ainsi, dans ce tutoriel, nous avons appris comment trouver le sous-ensemble de produits minimum d'un tableau en suivant un algorithme simple utilisant JavaScript. La solution implique divers critères tels que le nombre de nombres négatifs, de nombres positifs et de zéros présents dans le tableau. Il utilise des conditions if-else simples pour vérifier ces conditions et renvoyer le sous-ensemble minimum de produits en conséquence. La complexité temporelle du programme est O(n) et l'espace auxiliaire requis est O(1).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!