Множення матриць | рекурсивний
Дано дві матриці A і B. Завдання полягає в тому, щоб рекурсивно помножити матрицю A і матрицю B. Якщо матриця A та матриця B мультиплікативно не сумісні, тоді згенеруйте результат «Неможливо».
Приклади:
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
Рекомендується спочатку звернутися Ітераційне множення матриць .
Спочатку перевірте, чи можливе множення між матрицями чи ні. Для цього перевірте, чи дорівнює кількість стовпців першої матриці кількості рядків другої матриці чи ні. Якщо обидва рівні, продовжуйте далі, інакше згенеруйте вихід «Неможливо».
У рекурсивному множенні матриць ми реалізуємо три цикли ітерації через рекурсивні виклики. Внутрішній найбільш рекурсивний виклик multiplyMatrix() полягає в ітерації k (стовпець1 або рядок2). Другий рекурсивний виклик multiplyMatrix() це зміна стовпців, а крайній рекурсивний виклик — зміна рядків.
Нижче наведено код рекурсивного множення матриць.
C++Java// Recursive code for Matrix Multiplication #includeconst int MAX = 100 ; void multiplyMatrixRec ( int row1 int col1 int A [][ MAX ] int row2 int col2 int B [][ MAX ] int C [][ MAX ]) { // 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 static int i = 0 j = 0 k = 0 ; // 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[][] void multiplyMatrix ( int row1 int col1 int A [][ MAX ] int row2 int col2 int B [][ MAX ]) { if ( row2 != col1 ) { printf ( 'Not Possible n ' ); return ; } int C [ MAX ][ MAX ] = { 0 }; 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 ++ ) printf ( '%d ' C [ i ][ j ]); printf ( ' n ' ); } } // Driven Program int main () { int A [][ MAX ] = { { 1 2 3 } { 4 5 6 } { 7 8 9 } }; int B [][ MAX ] = { { 1 2 3 } { 4 5 6 } { 7 8 9 } }; int row1 = 3 col1 = 3 row2 = 3 col2 = 3 ; multiplyMatrix ( row1 col1 A row2 col2 B ); return 0 ; } // This code is contributed by Aarti_Rathi Python3// 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 KumarC## 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 col2 B 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 sahilshelangiaJavaScript// 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
Вихід30 36 42 66 81 96 102 126 150Часова складність: O(рядок1 * стовпець2* стовпець1)
Допоміжний простір: O(log (max(row1col2)) Як неявний стек використовується через рекурсіюСтворіть вікторину
