資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究JavaScript 對角佔優矩陣程式
矩陣在計算機科學和數學中是用於快速逼近複雜計算的強大工具。矩陣是由按行和列組織的數字集合，可以表示資料或數學問題。
透過本文，我們將學習對角佔優矩陣。我們將探討對角佔優矩陣的概念、演算法和示例，以及它們在各種程式語言中的實現。
對角佔優矩陣
如果對於矩陣中的每一行，該行中對角線元素的絕對值大於或等於所有非對角線元素的絕對值之和，則我們可以稱該方陣為對角佔優矩陣。簡單來說，如果矩陣中除對角線元素外的元素之和小於對角線矩陣。
如果我們有一個具有 i 行和 j 列的方陣 a，我們可以使用數學方程式將其表示為對角佔優矩陣，如下所示：
$$\mathrm{|\:a_{ii}\:|\:\geq\:\displaystyle\sum\limits_{jeq\:i}\:|\:a_{ij}|}$$ 對於所有 i 其中 aij 表示第 i 行和第 j 列中的元素
示例
A = [ [6, -2, 0, 0], [2, 8, -3, 0], [1, 2, 9, -4], [0, 1, -2, 7] ]
此矩陣是對角佔優矩陣，因為它滿足以下條件：
|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|
問題陳述
給定一個方陣，編寫一個 JavaScript 程式來檢查該矩陣是否為對角佔優矩陣。
示例
讓我們考慮一個 3x3 矩陣：
| 4 -1 0 | | -1 4 -1| | 0 -1 4 |
這裡，每一行的對角線元素分別是 4、4 和 4，它們都大於該行中其他元素的絕對值之和。因此，此矩陣是對角佔優矩陣。
現在讓我們看看解決上述問題的方法。
方法 1：暴力法
暴力法包括遍歷矩陣的每一行，並確定對角線元素是否大於該行中其他元素的絕對值之和。
演算法
遍歷矩陣的行。
計算每一行中其他元素的絕對值之和。
檢查該行的對角線元素是否大於或等於步驟 2 中確定的和。
如果對角線元素大於或等於和，則繼續遍歷下一行。
如果對角線元素小於和，則返回 false，表示矩陣不是對角佔優矩陣。
示例
<!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>
時間複雜度：O(n2)，其中 n 是矩陣的大小。
方法 2：排序
在此方法中，我們按降序對每一行的絕對值進行排序。然後，我們確定該行的對角線元素是否大於或等於最大的 n-1 個絕對值之和，其中 n 是矩陣的大小。
演算法
遍歷矩陣的行。
按降序對該行元素的絕對值進行排序。
新增最大的 n-1 個絕對值，其中 n 是矩陣的大小。
檢查該行的對角線元素是否大於或等於步驟 3 中確定的和。
如果對角線元素大於或等於和，則繼續遍歷下一行。
如果對角線元素小於和，則返回 false，表示矩陣不是對角佔優矩陣。
示例
<!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>
時間複雜度：O(n2 log n)，其中 n 是矩陣的大小。
方法 3：行縮放
在此方法中，我們首先縮放矩陣的每一行，使其對角線元素等於 1。然後，我們檢查該行中其他元素的絕對值是否小於 1。
演算法
遍歷矩陣的行。
確定具有最大絕對值的行列。
縮放該行，直到對角線元素等於 1。
檢查該行中其餘元素的絕對值是否小於 1。
如果所有行都滿足步驟 4 中的條件，則返回 true，表示矩陣是對角佔優矩陣。
如果任何一行不滿足步驟 4 中的條件，則返回 false，表示矩陣不是對角佔優矩陣。
示例
<!DOCTYPE html>
<html>
<body>
<h3>Diagonally Dominant Matrix</h3>
<p>Matrix:</p>
<pre id="matrix"></pre>
<p>Is diagonally dominant: <span id="output"></span></p>
<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>
</body>
</html>
時間複雜度：O(n3)，其中 n 是矩陣的大小。
結論
在本博文中，我們討論了使用各種方法來查詢矩陣是否為對角佔優矩陣的程式。其中一些方法使用了迴圈、排序和行縮放方法。希望您發現這些資訊有用。
136 次檢視
