Násobenie matice | Rekurzívne
Dané sú dve matice A a B. Úlohou je rekurzívne vynásobiť maticu A a maticu B. Ak matica A a matica B nie sú multiplikatívne kompatibilné, potom vygenerujte výstup „Nie je možné“.
Príklady:
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
Odporúča sa najprv odkázať Iteratívne maticové násobenie .
Najprv skontrolujte, či je násobenie medzi maticami možné alebo nie. Na to skontrolujte, či sa počet stĺpcov prvej matice rovná počtu riadkov druhej matice alebo nie. Ak sú obe rovnaké, pokračujte ďalej, inak vygenerujte výstup „Nie je možné“.
V rekurzívnom maticovom násobení implementujeme tri slučky iterácie prostredníctvom rekurzívnych volaní. Vnútorné najviac rekurzívne volanie multiplyMatrix() je iterovať k (col1 alebo row2). Druhé rekurzívne volanie multiplyMatrix() je zmeniť stĺpce a najvzdialenejšie rekurzívne volanie je zmeniť riadky.
Nižšie je uvedený kód násobenia rekurzívnej matice.
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
Výstup30 36 42 66 81 96 102 126 150Časová zložitosť: O(riadok1 * stĺpec2* stĺpec1)
Pomocný priestor: O(log (max(riadok1col2)) Ako implicitný zásobník sa používa kvôli rekurziiVytvoriť kvíz
