Programme JavaScript pour les requêtes de plage LCM

LCM signifie Least Common Multiple, le LCM d'un ensemble de nombres est le plus petit nombre parmi tous les nombres divisible par tous les nombres présents dans l'ensemble donné. Nous verrons le code complet ainsi que l'explication du problème donné. Dans cet article, nous allons implémenter un programme JavaScript pour une série de requêtes LCM.

Introduction au problème

Dans ce problème, nous recevons un tableau contenant des entiers et une autre requête de tableau contenant des paires de nombres représentant une plage de tableau donnée et nous devons calculer le LCM de tous les éléments de cette plage donnée. Par exemple -

Si le tableau donné est : [1, 2, 3, 4, 5, 6] et que le tableau de requête est : [[1,3], [2,5]], alors le premier élément de requête est [2, 3 , 4] et 12 sont des LCM.

Pour le deuxième élément de requête est [3, 4, 5, 6], le LCM est de 60.

Relation mathématique entre LCM et GCD

Pour trouver le PGCD, nous avons une formule euclidienne à l'aide de laquelle nous pouvons trouver le PGCD de deux nombres de complexité logarithmique et il existe une telle relation entre LCM et PGCD -

LCM and GCD of a given set A {a1, a2, a3 …. , an} is:
LCM(A) * GCD(A) = (a1 * a2 * a3* … * an)
OR
LCM(A) = (a1 * a2 * a3 … * an) / GCD(A)

Ainsi, nous trouverons le GCD et le produit de tous les nombres, puis à partir de là, nous pourrons trouver le LCM de ce nombre en opération O(1).

Méthode naïve

Le moyen le plus simple consiste à parcourir le tableau de requêtes et à trouver le produit des éléments dans la plage donnée et le GCD pour chaque requête. Trouvez le LCM à partir de ces deux valeurs et renvoyez-le. Implémentons-le dans le code -

Exemple

// function to find the gcd of the given number 
function gcd(a,b){
   if (a == 0) {
      return b;
   }
   else {
      return gcd(b%a,a);
   }
}

// function to find the lcm 
function lcmRange(arr, l, r){

   // taking gcd as zero because gcd of 0 with any number is that same number 
   var cur_gcd = 0
   var product = 1
   var cur_lcm = arr[l]
   for(var i = l+1 ;i <= r; i++) {
      product = cur_lcm * arr[i];
      cur_gcd = gcd(cur_lcm, arr[i])
      cur_lcm = product/cur_gcd
   }
   console.log("The LCM of the element in the given range from " + l + " to " + r + " is: " + cur_lcm);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]

// defining the queries array 
var queries = [[1,3], [2,5]]

// traversing over the array 
for(var i = 0; i< queries.length; i++){
   lcmRange(arr,queries[i][0], queries[i][1])
}

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(Q*N*log(D)), où Q est le nombre de requêtes, N est le nombre d'éléments dans le tableau et D est le nombre maximum de tableaux présents dans le tableau.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire.

Dans le programme ci-dessus, si le nombre de requêtes est égal à N, alors sa complexité temporelle sera supérieure à N², ce qui rend cette méthode inefficace. Voyons, c'est une autre façon &miinus;

Méthode d'arborescence de segments de ligne

Un arbre de segments est une structure de données de haut niveau utilisée pour diviser un problème en segments puis les connecter par puissances de 2. Cela nécessite un peu d'espace pour les requêtes de plage et produit des résultats en temps logarithmique. Voyons son code -

Exemple

// defining maximum size
var MAX = 1000

// makking tree 
var tree = new Array(4*MAX);

// declaring new array 
var arr = new Array(MAX);

// function for lcm
function lcm(a, b){
   return a*b/gcd(a,b);
}

// function for gcd
function gcd(a, b){
   if (a == 0)	{
      return b
   }
   else{
      return gcd(b%a,a);
   }
}

// Function to creata a segment tree 
function build(first, last, cur_node){

   // base condition 
   if (first == last){
      tree[cur_node] = arr[first];
      return;
   }
   var mid = (first + last)/2
   mid = Math.floor(mid);
   
   // creating left and right segments
   build(first, mid, 2*cur_node);
   build(mid+1, last, 2*cur_node + 1);
   
   // build the parent for current 
   var lcm_l = tree[2*cur_node];
   var lcm_r = tree[2*cur_node+1];
   tree[cur_node] = lcm(lcm_l, lcm_r);
}

// Function to make queries for array range 
function query(first, last, l, r, cur_node){

   // section out of current range
   
   // 1 is safe to return 
   if (last < l || first > r){
      return 1;
   }
   
   // complete inside the current segment
   if (l <= first  && r >= last)
   return tree[cur_node];
   
   // partially inside the current segment 
   var mid = (first+last)/2;
   mid = Math.floor(mid)
   var lcm_l = query(first, mid, l, r, 2*cur_node);
   var lcm_r = query(mid+1, last, l, r, 2*cur_node+1);
   return lcm(lcm_l, lcm_r);
}

// defining the array 
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;
arr[5] = 6;

// build the segment tree
build(0, 5, 1);

// defining query array 
var queries = [[1,3], [2,5]]

// traversing over the array 
for(var i = 0; i< queries.length; i++){
   console.log("The LCM of the element in the given range from " + queries[i][0] + " to " + queries[i][1] + " is: " + query(0,5,queries[i][0],queries[i][1],1) );
}

Conclusion

Dans ce tutoriel, nous avons implémenté un article JavaScript pour trouver une requête de plage lcm. Nous avons vu deux méthodes, l'une est la méthode naïve avec une complexité temporelle O(Q*N*log(D)), et l'autre est l'arbre de segments de ligne avec une complexité temporelle O(Q*log(N)) accomplie. p>

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!