Program JavaScript untuk matriks dominan pepenjuru
Matriks ialah alat penting dalam sains komputer dan matematik dan boleh digunakan untuk menganggarkan pengiraan yang sukar dengan cepat. Matriks ialah koleksi nombor yang disusun dalam baris dan lajur yang boleh mewakili data atau masalah matematik.
Melalui artikel ini, kita akan belajar tentang matriks dominan pepenjuru. Kami akan mengkaji konsep, algoritma dan contoh matriks dominan pepenjuru, serta pelaksanaannya dalam pelbagai bahasa pengaturcaraan.
Matriks dominan pepenjuru
Jika untuk setiap baris dalam matriks, saiz entri pepenjuru dalam baris adalah lebih besar daripada atau sama dengan jumlah saiz semua entri bukan pepenjuru, kita boleh panggil matriks segi empat sama dominan secara menyerong. Ringkasnya, jika jumlah unsur dalam matriks kecuali unsur pepenjuru adalah kurang daripada matriks pepenjuru.
Jika kita mempunyai matriks segi empat sama a yang mengandungi baris i dan lajur j, kita boleh menggunakan persamaan matematik untuk mewakilinya sebagai matriks dominan pepenjuru -
$$mathrm{|:a_{ii}:|:geq:displaystylesumlimits_{jeq:i}:|:a_{ij} |}$$ dimiliki oleh saya dengan aij mewakili entri dalam lajur i dan j
Contoh
A = [ [6, -2, 0, 0], [2, 8, -3, 0], [1, 2, 9, -4], [0, 1, -2, 7] ]
Matriks ini dominan secara pepenjuru kerana ia memenuhi syarat berikut -
|a11| ≥ |a12| + |a13| + |a14| == |+6| ≥ |+2| + |+1| + |+0| |a22| ≥ |a21| + |a23| + |a24| == |+8| ≥ |+2| + |+3| + |+0| |a33| ≥ |a31| + |a32| + |a34| == |+9| ≥ |+1| + |+2| + |+4| |a44| ≥ |a41| + |a42| + |a43| == |+7| ≥ |+0| + |+1| + |+2|
Pernyataan Masalah
Diberi matriks segi empat sama, tulis program JavaScript untuk menyemak sama ada matriks dominan secara pepenjuru.
Contoh
Mari kita pertimbangkan matriks 3x3 -
| 4 -1 0 | | -1 4 -1| | 0 -1 4 |
Di sini, unsur pepenjuru bagi setiap baris masing-masing ialah 4, 4 dan 4, dan kesemuanya adalah lebih besar daripada jumlah nilai mutlak unsur lain dalam baris itu. Oleh itu, matriks ini dominan secara pepenjuru.
Sekarang mari kita lihat penyelesaian kepada masalah di atas.
Kaedah 1: Brute force cracking
Kaedah brute force terdiri daripada mengulang setiap baris matriks dan menentukan sama ada unsur pepenjuru lebih besar daripada jumlah nilai mutlak elemen lain dalam baris.
Algoritma
Lelaran pada baris matriks.
Kira jumlah nilai mutlak komponen lain dalam setiap baris.
Periksa sama ada unsur pepenjuru baris lebih besar daripada atau sama dengan jumlah yang ditentukan dalam langkah 2.
Jika unsur pepenjuru lebih besar daripada atau sama dengan jumlah, teruskan lelaran ke baris seterusnya.
Jika unsur pepenjuru kurang daripada jumlah, kembalikan palsu, menunjukkan bahawa matriks tidak dominan secara pepenjuru.
Contoh
<!DOCTYPE html>
<html>
<body>
<div id="matrix"></div>
<div id="output"></div>
<script>
function isDiagonallyDominant(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
for(let i = 0; i < rows; i++) {
let sum = 0;
for(let j = 0; j < cols; j++) {
if(i !== j) {
sum += Math.abs(matrix[i][j]);
}
}
if(Math.abs(matrix[i][i]) < sum) {
return false;
}
}
return true;
}
const matrix = [[4, -1, 0], [-1, 4, -1], [0, -1, 4]];
const output = isDiagonallyDominant(matrix) ? 'Matrix is diagonally dominant.' : 'Matrix is not diagonally dominant.';
document.getElementById('matrix').innerHTML = 'Matrix: ' + JSON.stringify(matrix);
document.getElementById('output').innerHTML = 'Output: ' + output;
</script>
</body>
</html>
Kerumitan masa: O(n2), dengan n ialah saiz matriks.
Kaedah 2: Isih
Dalam kaedah ini, kami mengisih nilai mutlak setiap baris dalam tertib menurun. Kami kemudiannya menentukan sama ada unsur pepenjuru baris lebih besar daripada atau sama dengan jumlah terbesar bagi nilai mutlak n-1, dengan n ialah saiz matriks.
Algoritma
Lelaran pada baris matriks.
Isih item baris mengikut nilai mutlak dalam tertib menurun.
Tambahkan nilai mutlak n-1 terbesar, dengan n ialah saiz matriks.
Periksa sama ada unsur pepenjuru baris lebih besar daripada atau sama dengan jumlah yang ditentukan dalam langkah 3.
Jika unsur pepenjuru lebih besar daripada atau sama dengan jumlah, teruskan lelaran ke baris seterusnya.
Jika unsur pepenjuru kurang daripada jumlah, kembalikan palsu, menunjukkan bahawa matriks tidak dominan secara pepenjuru.
Contoh
<!DOCTYPE html>
<html>
<body>
<h2>Diagonally Dominant Matrix</h2>
<p id="matrix"></p>
<p id="output"></p>
<script>
function isDiagonallyDominant(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
for(let i = 0; i < rows; i++) {
const sortedRow = matrix[i].map(Math.abs).sort((a, b) => b - a);
const sum = sortedRow.slice(1, cols).reduce((acc, val) => acc + val, 0);
if(sortedRow[0] < sum) {
return false;
}
}
return true;
}
// Example matrix
const matrix = [[4, -1, 0], [-1, 4, -1], [0, -1, 4]];
// Display input matrix
const matrixElement = document.getElementById("matrix");
matrixElement.innerHTML = "Input Matrix: <br>" + JSON.stringify(matrix);
// Check if the matrix is diagonally dominant
const isDominant = isDiagonallyDominant(matrix);
// Display output
const outputElement = document.getElementById("output");
outputElement.innerHTML = "Is diagonally dominant: " + isDominant;
</script>
</body>
</html>
Kerumitan masa: O(n2 log n), dengan n ialah saiz matriks.
Kaedah 3: Penskalaan baris
Dalam kaedah ini, kita mula-mula menskalakan setiap baris matriks supaya unsur pepenjurunya adalah sama dengan 1. Kami kemudian melihat jika nilai mutlak entri lain dalam baris adalah kurang daripada 1.
Algoritma
Lelaran pada baris matriks.
Kenal pasti baris dengan nilai mutlak tertinggi.
Skalakan baris sehingga elemen pepenjuru sama dengan 1.
Semak sama ada nilai mutlak baki entri dalam baris kurang daripada 1.
Kembalian benar jika semua baris memenuhi kriteria dalam langkah 4, menunjukkan bahawa matriks adalah dominan secara menyerong.
Jika mana-mana baris tidak memenuhi keperluan langkah 4, kembalikan palsu, menunjukkan bahawa matriks tidak dominan secara menyerong.
Contoh
<!DOCTYPE html> <html> <body> <h3>Diagonally Dominant Matrix</h3> <p>Matrix:</p> <pre id="matrix">
Is diagonally dominant:
<script> function isDiagonallyDominant(matrix) { const rows = matrix.length; const cols = matrix[0].length; for(let i = 0; i < rows; i++) { const maxAbsVal = Math.max(...matrix[i].map(Math.abs)); if(maxAbsVal === 0) { return false; } const scale = 1 / maxAbsVal; for(let j = 0; j < cols; j++) { matrix[i][j] *= scale; } const sum = matrix[i].slice(0, i).reduce((acc, val) => acc + Math.abs(val), 0) + matrix[i].slice(i+1, cols).reduce((acc, val) => acc + Math.abs(val), 0); if(sum >= 1) { return false; } } return true; } const matrix = [[4, -1, 0], [-1, 4, -1], [0, -1, 4]]; document.getElementById('matrix').innerHTML = matrix.map(row => row.join(' ')).join(''); document.getElementById('output').innerHTML = isDiagonallyDominant(matrix) ? 'true' : 'false'; </script>