Program JavaScript untuk pertanyaan LCM julat

LCM bermaksud Gandaan Sepunya Terkecil, LCM bagi set nombor ialah nombor terkecil antara semua nombor yang boleh dibahagi dengan semua nombor yang terdapat dalam set yang diberikan. Kami akan melihat kod lengkap bersama dengan penjelasan masalah yang diberikan. Dalam artikel ini, kami akan melaksanakan program JavaScript untuk satu siri pertanyaan LCM.

Pengenalan kepada masalah

Dalam masalah ini kita diberi tatasusunan yang mengandungi integer dan satu lagi pertanyaan tatasusunan yang mengandungi pasangan nombor yang mewakili julat tatasusunan yang diberikan dan kami perlu mengira LCM semua elemen dalam julat yang diberikan itu. Contohnya -

Jika tatasusunan yang diberikan ialah: [1, 2, 3, 4, 5, 6] dan tatasusunan pertanyaan ialah: [[1,3], [2,5]], maka elemen pertanyaan pertama ialah [2, 3 , 4] dan 12 ialah LCM.

Untuk elemen pertanyaan kedua ialah [3, 4, 5, 6] LCM ialah 60.

Hubungan matematik antara LCM dan GCD

Untuk mencari GCD kita mempunyai formula Euclidean dengan bantuannya kita boleh mencari GCD bagi dua nombor kerumitan logaritma dan terdapat hubungan sedemikian antara LCM dan GCD -

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)

Jadi, kita akan mencari GCD dan hasil darab semua nombor dan kemudian dari situ, kita boleh mencari LCM nombor itu dalam operasi O(1).

Kaedah naif

Cara paling mudah ialah dengan mengulangi tatasusunan pertanyaan dan mencari hasil darab elemen dalam julat dan GCD yang diberikan untuk setiap pertanyaan. Cari LCM daripada dua nilai ini dan kembalikannya. Mari laksanakannya dalam kod -

Contoh

// 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])
}

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(Q*N*log(D)), dengan Q ialah bilangan pertanyaan, N ialah bilangan elemen dalam tatasusunan dan D ialah bilangan maksimum tatasusunan yang terdapat dalam tatasusunan.

Kerumitan ruang kod di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Dalam program di atas, jika bilangan pertanyaan adalah sama dengan N, maka kerumitan masanya akan lebih besar daripada N², yang menjadikan kaedah ini tidak cekap. Mari lihat ini cara lain &miinus;

Kaedah Pokok Segmen Garisan

Pohon segmen ialah struktur data peringkat tinggi yang digunakan untuk membahagikan masalah kepada segmen dan kemudian menyambungkannya dalam kuasa 2. Ini memerlukan sedikit ruang untuk pertanyaan julat dan menghasilkan keputusan dalam masa logaritma. Mari lihat kodnya -

Contoh

// 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) );
}

Kesimpulan

Dalam tutorial ini, kami melaksanakan artikel JavaScript untuk mencari pertanyaan lcm julat. Kami telah melihat dua kaedah, satu ialah kaedah naif dengan kerumitan masa O(Q*N*log(D)), dan satu lagi ialah pokok segmen garisan dengan kerumitan masa O(Q*log(N)) capai. p>

Atas ialah kandungan terperinci Program JavaScript untuk pertanyaan LCM julat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!