Program JavaScript: Kira bilangan set 1 dan 0 dalam matriks binari

Matriks binari ialah matriks yang terdiri daripada hanya dua nombor, yang, seperti namanya, adalah 1 dan 0. Dalam artikel ini, kami akan meneliti kod dan penjelasan yang betul untuk memahami konsep dengan lebih baik. Dalam tutorial ini, kami akan menulis program JavaScript untuk mengira set 1s dan 0s dalam matriks binari yang diberikan.

Pengenalan kepada masalah

Dalam masalah ini, kita diberikan matriks binari dan kita perlu mencari set baris atau lajur yang mengandungi nilai yang sama. Satu set boleh menjadi satu nilai atau daripada sebarang saiz, dengan syarat ia mengandungi elemen yang sama daripada baris atau lajur. Contohnya,

Kami mempunyai matriks binari dengan dua baris dan tiga lajur yang kelihatan seperti ini -

1 0 1
0 0 1

Bilangan set 1 dan 0 boleh dikira sebagai

• Set saiz 1 − Semua sel matriks adalah set yang berbeza dengan sendirinya dan terdapat sejumlah 6 sel.

• SET SAIZ 2 - Dua lajur pertama baris kedua mempunyai nilai yang sama, nilai lajur kedua dan ketiga juga sama, terdapat 2 set saiz 2 dengan nilai yang sama. Terdapat dua lagi 1 dalam baris pertama yang boleh dianggap sebagai satu set

• Koleksi saiz 3 - Saiz koleksi maksimum yang mungkin dalam matriks ialah saiz maksimum baris dan lajur, ini adalah 3. Walau bagaimanapun, untuk saiz, tiada set yang mengandungi nilai yang sama tersedia.

Jadi kami ada 6, 3 dan 0 set untuk saiz 1, 2 dan 3 masing-masing. Jadi akhirnya jawapan kita ialah 9.

Kaedah

Dalam bahagian sebelumnya, kita telah melihat bahawa kita perlu menumpukan hanya pada baris atau lajur tertentu untuk mendapatkan bilangan elemen yang serupa di dalamnya. Selain itu, kita akan menggunakan konsep matematik untuk mengira bilangan set dengan saiz yang berbeza baris atau lajur tertentu.

Sebagai contoh, jika kita mempunyai jumlah bilangan x 1 berturut-turut, jumlah bilangan set 1 yang berbeza saiz dari 1 hingga x akan datang daripada pilih atur.

Mari beralih kepada pendekatan ini -

• Pertama, kita akan mendapat tatasusunan yang mengandungi sifar dan satu, atau matriks binari yang diberikan.

• Kami akan mencipta fungsi yang secara automatik mengira jawapan yang diperlukan untuk mana-mana matriks yang dihantar kepadanya sebagai parameter dan mengembalikan jawapan sebagai nilai pulangan.

• Dalam fungsi ini, kami akan mengulangi tatasusunan atau matriks binari dua kali, sekali mengikut baris dan kali kedua mengikut lajur.

• Dalam gelung for, kita akan mengekalkan dua pembolehubah, satu untuk menyimpan nombor 1 dan satu lagi untuk menyimpan nombor 0.

• Selepas melelaran melalui satu baris atau lajur, kami akan mengemas kini jawapan menggunakan formula yang dilihat di atas dan menyimpan jawapan dalam pembolehubah kami.

• Akhirnya kami akan mengembalikan jawapan dengan mengalih keluar baris*lajur daripadanya kerana kami telah menambahnya dua kali.

Kami telah mengalih keluar lajur baris * kerana apabila melelaran ke atas baris, set ditambah dengan nilai tunggal dua sifar dan satu dan sekali lagi apabila melelaran ke atas lajur.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Mari kita lihat pelaksanaan langkah-langkah di atas untuk memahami konsep dengan lebih baik -

// given variables
var cols = 3; // no of columns
var rows = 2; // no of rows
// function to solve the problem with passed array 
function fun(arr) {
   // variable to store the final answer 
   var ans = 0;
   // traversing over the rows using for loop 
   for (var i = 0; i < rows; i++) {
      var ones = 0, zeroes = 0;
      for ( var j = 0; j < cols; j++) {
         if (arr[i][j] == 1)
         ones++;
         else
         zeroes++;
      }
      // increasing the answer on the basis of current count based on ones 
      ans = ans + Math.pow(2, ones)-1;
      // based on zeros 
      ans = ans + Math.pow(2, zeroes)-1;
   }
   //traversing over the columns using for loop 
   for (var i = 0; i < cols; i++) {
      var ones = 0, zeroes = 0;
      for ( var j = 0; j < rows; j++) {
         if (arr[j][i] == 1)
         ones++;
         else
         zeroes++;
      }
      //increasing the answer on the basis of current count based on ones 
      ans = ans + Math.pow(2, ones)-1;
      // based on zeros 
      ans = ans + Math.pow(2, zeroes)-1;
   }
   return ans - (rows * cols);
}
var arr = [ [ 1, 0, 1 ], [ 0, 1, 0 ] ];
console.log("Total number of the sets in the given binary matrix is: " + fun(arr));

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N*N), dengan N ialah bilangan maksimum baris dan lajur matriks yang diberikan.

Tiada ruang tambahan digunakan, jadi kerumitan ruang kod ialah O(1).

Kesimpulan

Dalam tutorial ini, kami belajar cara menulis program JavaScript yang mengira bilangan set 1s dan 0s dalam matriks binari tertentu. Matriks binari ialah matriks yang mengandungi hanya dua nombor, yang, seperti namanya, adalah 1 dan 0. Kod yang dimaksudkan mempunyai kerumitan masa O(N*N) dan kerumitan ruang O(1).

Atas ialah kandungan terperinci Program JavaScript: Kira bilangan set 1 dan 0 dalam matriks binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!