Program JavaScript untuk subset produk minimum tatasusunan

Program JavaScript untuk subset produk minimum tatasusunan ialah masalah biasa yang timbul dalam bidang sains komputer dan pengaturcaraan. Pernyataan masalah memerlukan kita mencari produk terkecil yang boleh diperoleh daripada mana-mana subset tatasusunan yang diberikan.

Subset produk minimum tatasusunan ialah subset elemen tatasusunan yang menghasilkan produk terkecil yang mungkin. Terdapat beberapa algoritma yang boleh digunakan untuk mengenal pasti subset ini, termasuk pengaturcaraan dinamik, algoritma tamak dan cabang-dan-terikat. Pilihan algoritma bergantung pada kekangan dan spesifikasi khusus masalah yang dihadapi.

Dalam tutorial ini, kita akan membincangkan pelbagai cara untuk menyelesaikan masalah ini menggunakan bahasa pengaturcaraan JavaScript. Kami akan memperkenalkan kaedah algoritma asas dan pelaksanaannya menggunakan coretan kod JavaScript. Menjelang akhir tutorial ini, pembaca akan mempunyai pemahaman yang jelas tentang pernyataan masalah dan pelbagai cara untuk menyelesaikannya menggunakan JavaScript.

Pernyataan Masalah

Memandangkan tatasusunan integer, kita perlu mencari subset produk minimum tatasusunan itu. Subset produk tatasusunan ditakrifkan sebagai hasil darab mana-mana subset tatasusunan.

Sebagai contoh,

Mari kita pertimbangkan tatasusunan [2, 3, -1, 4, -2].

Subset produk tatasusunan ini ialah

[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]. 

Subset produk minimum tatasusunan ini ialah [-2].

Sekarang mari kita bincangkan pelbagai pendekatan algoritma untuk menyelesaikan penyataan masalah ini dan pilih algoritma yang paling sesuai.

Algoritma

Pilihan algoritma bergantung pada kekangan khusus dan prasyarat masalah.

Algoritma Greedy - Algoritma tamak ialah kaedah biasa untuk mencari subset produk minimum tatasusunan. Konsep asas adalah bermula dengan elemen tatasusunan awal dan hanya menambah elemen seterusnya pada subset apabila produk yang lebih kecil dijana. Walaupun algoritma tamak mudah dilaksanakan dan ringkas, ia tidak semestinya memberikan penyelesaian yang optimum, dan prestasinya boleh menjadi perlahan dengan ketara untuk tatasusunan yang besar.

Pengaturcaraan Dinamik - Pengaturcaraan dinamik ialah algoritma lain yang digunakan untuk menyelesaikan masalah ini. Ia memecahkan masalah kepada sub-masalah yang lebih kecil dan menyelesaikan setiap sub-masalah sekaligus, menggunakan penyelesaian kepada sub-masalah yang lebih kecil untuk menentukan penyelesaian kepada sub-masalah yang lebih besar. Pendekatan ini menjimatkan banyak masa dan ruang. Walaupun pengaturcaraan dinamik boleh menjamin penyelesaian yang optimum, pelaksanaannya mungkin lebih kompleks daripada algoritma tamak.

Algoritma Cawangan dan Terikat - Satu lagi cara untuk mengenal pasti subset produk minimum tatasusunan ialah algoritma cawangan dan terikat. Ia memerlukan meneroka pelbagai kemungkinan dengan mencabang dan mengehadkan carian untuk mempertimbangkan penyelesaian yang sah sahaja. Algoritma ini menjamin penyelesaian yang optimum dan boleh menjadi lebih pantas daripada algoritma lain untuk senario tertentu. Namun begitu, pelaksanaannya mungkin lebih kompleks dan mungkin memerlukan lebih banyak sumber masa dan ruang berbanding algoritma lain.

Ringkasnya, pendekatan mudah memerlukan menjana semua subset, mengira hasil darab setiap subset, dan kemudian mengembalikan produk minimum.

Penyelesaian yang lebih baik perlu mengambil kira fakta berikut.

• Langkah 1 - Dalam kes di mana tiada sifar dan nombor negatif adalah genap, hasil darab semua unsur kecuali nombor negatif terbesar akan menghasilkan hasilnya.

• Langkah 2 - Sekiranya tiada sifar dan nombor negatif adalah ganjil, hasil darab semua elemen akan memberikan hasilnya.

• Langkah 3 - Jika sifar wujud dan positif sepenuhnya, hasilnya ialah 0. Walau bagaimanapun, dalam kes khas di mana tiada nombor negatif dan semua elemen lain adalah positif, jawapannya hendaklah nombor positif terkecil.

Sekarang mari kita cuba memahami pendekatan di atas dengan contoh melaksanakan pernyataan masalah menggunakan JavaScript.

Contoh

Program ini mula-mula mengira hasil darab nombor negatif, sifar, nombor negatif maksimum, nombor positif minimum dan nombor bukan sifar. Ia kemudian menggunakan peraturan berdasarkan pengiraan nombor negatif dan sifar untuk mengembalikan subset produk minimum tatasusunan. Kerumitan masa program ialah O(n) dan ruang tambahan ialah O(1).

Input 1: a[] = { -1, -1, -2, 4, 3 };

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}.`);

Atas ialah kandungan terperinci Program JavaScript untuk subset produk minimum tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!