Programme JavaScript pour vérifier si la matrice est triangulaire supérieure

Une matrice triangulaire supérieure est une matrice carrée avec le même nombre de lignes et de colonnes et tous les éléments situés en dessous de la diagonale principale depuis la première cellule (située dans le coin supérieur gauche) jusqu'à la dernière cellule (située dans le coin supérieur gauche). coin gauche ) coin inférieur droit) est nul. Le triangle supérieur signifie que les éléments présents dans le triangle inférieur seront nuls. Nous mettrons en œuvre un code approprié et les complexités temporelles et spatiales seront expliquées et discutées.

Exemple

Input1:
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 0, 0, 1]
]
Output1: Yes,

Explication : Nous pouvons voir que la diagonale principale contient les éléments 1, 5, 8 et 1, et que toutes les cellules en dessous de la diagonale principale ont des valeurs nulles.

Input2:
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 1, 0, 1]
]
Output1: No

Explication : On peut voir que la diagonale principale contient les éléments 1, 5, 8 et 1 et que toutes les cellules en dessous de la diagonale principale ont des valeurs non nulles car la deuxième colonne de la dernière ligne contient des valeurs non nulles.

Méthode

Nous avons vu l'exemple ci-dessus, regardons maintenant les étapes pour implémenter le code :

Tout d'abord, nous allons créer une fonction dans laquelle nous transmettons la matrice donnée. Nous ne parcourrons que la partie inférieure de la diagonale principale de la matrice, c'est-à-dire chaque cellule (i,j) où j est inférieur à i. Si nous trouvons une cellule avec une valeur non nulle, nous renverrons false, sinon nous finirons par renvoyer true.

Exemple

// function to traverse over the matrix
function check(mat){

   // getting total number of rows of matrix
   var rows = mat.length
   
   // traversing over the section present above the main diagonal
   for(var i = 0; i < rows; i++){
      for(var j = 0; j < i; j++){
         if(mat[i][j] != 0){
            return false;
         }
      }
   }
   return true;
}

// defining the matrix
var mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 0, 0, 1]
]
   
// given matrix
console.log("The given matrix is: ");
console.log(mat)
if(check(mat)){
   console.log("The given matrix is an upper triangular matrix");
}
else{
   console.log("The given matrix is not an upper triangular matrix");
}

// updating matrix
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 1, 0, 1]
      ]
   
// given matrix
console.log("The given matrix is: ");
console.log(mat)
if(check(mat)){
   console.log("The given matrix is an upper triangular matrix");
}
else{
   console.log("The given matrix is not an upper triangular matrix");
}

Sortie

The given matrix is: 
[ [ 1, 2, 3, 4 ], [ 0, 5, 6, 7 ], [ 0, 0, 8, 9 ], [ 0, 0, 0, 1 ] ]
The given matrix is an upper triangular matrix
The given matrix is: 
[ [ 1, 2, 3, 4 ], [ 0, 5, 6, 7 ], [ 0, 0, 8, 9 ], [ 0, 1, 0, 1 ] ]
The given matrix is not an upper triangular matrix

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*N), où N est le nombre de lignes de la matrice donnée. En effet, nous ne parcourons la matrice qu'une seule fois.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour vérifier si une matrice donnée est une matrice triangulaire supérieure. Le triangle supérieur signifie que les éléments présents dans le triangle inférieur seront nuls. Nous parcourons les cellules de la matrice où le nombre de colonnes est inférieur au nombre de lignes, avec une complexité temporelle O(N*N) et une complexité spatiale O(1).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!