Étant donné deux matrices A et B. La tâche consiste à multiplier la matrice A et la matrice B de manière récursive. Si la matrice A et la matrice B ne sont pas compatibles multiplicativement, générez la sortie « Impossible ».
Exemples :
Input: A = 12 56
45 78
B = 2 6
5 8
Output: 304 520
480 894
Input: A = 1 2 3
4 5 6
7 8 9
B = 1 2 3
4 5 6
7 8 9
Output: 30 36 42
66 81 96
102 126 150
Il est recommandé de se référer d'abord Multiplication matricielle itérative .
Vérifiez d’abord si la multiplication entre matrices est possible ou non. Pour cela, vérifiez si le nombre de colonnes de la première matrice est égal ou non au nombre de lignes de la deuxième matrice. Si les deux sont égaux, continuez sinon, générez la sortie « Impossible ».
Dans la multiplication matricielle récursive, nous implémentons trois boucles d'itération via des appels récursifs. L'appel le plus intérieur récursif de multiplierMatrix() est d'itérer k (col1 ou row2). Le deuxième appel récursif de multiplierMatrix() consiste à changer les colonnes et l'appel récursif le plus externe consiste à changer de lignes.
conception unique
Vous trouverez ci-dessous le code de multiplication matricielle récursive.
C++// Recursive code for Matrix Multiplication #include
// Java recursive code for Matrix Multiplication class GFG { public static int MAX = 100; // Note that below variables are static // i and j are used to know current cell of // result matrix C[][]. k is used to know // current column number of A[][] and row // number of B[][] to be multiplied public static int i = 0 j = 0 k = 0; static void multiplyMatrixRec(int row1 int col1 int A[][] int row2 int col2 int B[][] int C[][]) { // If all rows traversed if (i >= row1) return; // If i < row1 if (j < col2) { if (k < col1) { C[i][j] += A[i][k] * B[k][j]; k++; multiplyMatrixRec(row1 col1 A row2 col2 B C); } k = 0; j++; multiplyMatrixRec(row1 col1 A row2 col2 B C); } j = 0; i++; multiplyMatrixRec(row1 col1 A row2 col2 B C); } // Function to multiply two matrices A[][] and B[][] static void multiplyMatrix(int row1 int col1 int A[][] int row2 int col2 int B[][]) { if (row2 != col1) { System.out.println('Not Possiblen'); return; } int[][] C = new int[MAX][MAX]; multiplyMatrixRec(row1 col1 A row2 col2 B C); // Print the result for (int i = 0; i < row1; i++) { for (int j = 0; j < col2; j++) System.out.print(C[i][j]+' '); System.out.println(); } } // driver program public static void main (String[] args) { int row1 = 3 col1 = 3 row2 = 3 col2 = 3; int A[][] = { {1 2 3} {4 5 6} {7 8 9}}; int B[][] = { {1 2 3} {4 5 6} {7 8 9} }; multiplyMatrix(row1 col1 A row2 col2 B); } } // Contributed by Pramod Kumar
# Recursive code for Matrix Multiplication MAX = 100 i = 0 j = 0 k = 0 def multiplyMatrixRec(row1 col1 A row2 col2 B C): # Note that below variables are static # i and j are used to know current cell of # result matrix C[][]. k is used to know # current column number of A[][] and row # number of B[][] to be multiplied global i global j global k # If all rows traversed. if (i >= row1): return # If i < row1 if (j < col2): if (k < col1): C[i][j] += A[i][k] * B[k][j] k += 1 multiplyMatrixRec(row1 col1 A row2 col2B C) k = 0 j += 1 multiplyMatrixRec(row1 col1 A row2 col2 B C) j = 0 i += 1 multiplyMatrixRec(row1 col1 A row2 col2 B C) # Function to multiply two matrices # A[][] and B[][] def multiplyMatrix(row1 col1 A row2 col2 B): if (row2 != col1): print('Not Possible') return C = [[0 for i in range(MAX)] for i in range(MAX)] multiplyMatrixRec(row1 col1 A row2 col2 B C) # Print the result for i in range(row1): for j in range(col2): print( C[i][j] end = ' ') print() # Driver Code A = [[1 2 3] [4 5 6] [7 8 9]] B = [[1 2 3] [4 5 6] [7 8 9]] row1 = 3 col1 = 3 row2 = 3 col2 = 3 multiplyMatrix(row1 col1 A row2 col2 B) # This code is contributed by sahilshelangia
// C# recursive code for // Matrix Multiplication using System; class GFG { public static int MAX = 100; // Note that below variables // are static i and j are used // to know current cell of result // matrix C[][]. k is used to // know current column number of // A[][] and row number of B[][] // to be multiplied public static int i = 0 j = 0 k = 0; static void multiplyMatrixRec(int row1 int col1 int []A int row2 int col2 int []B int []C) { // If all rows traversed if (i >= row1) return; // If i < row1 if (j < col2) { if (k < col1) { C[i j] += A[i k] * B[k j]; k++; multiplyMatrixRec(row1 col1 A row2 col2 B C); } k = 0; j++; multiplyMatrixRec(row1 col1 A row2 col2 B C); } j = 0; i++; multiplyMatrixRec(row1 col1 A row2 col2 B C); } // Function to multiply two // matrices A[][] and B[][] static void multiplyMatrix(int row1 int col1 int []A int row2 int col2 int []B) { if (row2 != col1) { Console.WriteLine('Not Possiblen'); return; } int[]C = new int[MAX MAX]; multiplyMatrixRec(row1 col1 A row2 col2 B C); // Print the result for (int i = 0; i < row1; i++) { for (int j = 0; j < col2; j++) Console.Write(C[i j] + ' '); Console.WriteLine(); } } // Driver Code static public void Main () { int row1 = 3 col1 = 3 row2 = 3 col2 = 3; int []A = {{1 2 3} {4 5 6} {7 8 9}}; int []B = {{1 2 3} {4 5 6} {7 8 9}}; multiplyMatrix(row1 col1 A row2 col2 B); } } // This code is contributed by m_kit
<script> // Javascript recursive code for Matrix Multiplication let MAX = 100; // Note that below variables are static // i and j are used to know current cell of // result matrix C[][]. k is used to know // current column number of A[][] and row // number of B[][] to be multiplied let i = 0 j = 0 k = 0; function multiplyMatrixRec(row1 col1 A row2 col2 B C) { // If all rows traversed if (i >= row1) return; // If i < row1 if (j < col2) { if (k < col1) { C[i][j] += A[i][k] * B[k][j]; k++; multiplyMatrixRec(row1 col1 A row2 col2 B C); } k = 0; j++; multiplyMatrixRec(row1 col1 A row2 col2 B C); } j = 0; i++; multiplyMatrixRec(row1 col1 A row2 col2 B C); } // Function to multiply two matrices A[][] and B[][] function multiplyMatrix(row1 col1 A row2 col2 B) { if (row2 != col1) { document.write('Not Possible' + ''); return; } let C = new Array(MAX); for(let i = 0; i < MAX; i++) { C[i] = new Array(MAX); for(let j = 0; j < MAX; j++) { C[i][j] = 0; } } multiplyMatrixRec(row1 col1 A row2 col2 B C); // Print the result for (let i = 0; i < row1; i++) { for (let j = 0; j < col2; j++) document.write(C[i][j]+' '); document.write(''); } } let row1 = 3 col1 = 3 row2 = 3 col2 = 3; let A = [ [1 2 3] [4 5 6] [7 8 9] ]; let B = [ [1 2 3] [4 5 6] [7 8 9] ]; multiplyMatrix(row1 col1 A row2 col2 B); </script>
Sortir
30 36 42 66 81 96 102 126 150
Complexité temporelle : O(row1 * col2* col1)
Espace auxiliaire : O(log (max(row1col2)) Comme la pile implicite est utilisée en raison de la récursivité
Créer un quiz