행렬 곱셈 | 재귀적
두 개의 행렬 A와 B가 주어졌을 때, 작업은 행렬 A와 행렬 B를 재귀적으로 곱하는 것입니다. 행렬 A와 행렬 B가 곱셈 호환이 아닌 경우 'Not Possible' 출력을 생성합니다.
예:
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
먼저 참고하시는 것이 좋습니다 반복 행렬 곱셈 .
먼저 행렬 간의 곱셈이 가능한지 확인하십시오. 이를 위해 첫 번째 행렬의 열 수가 두 번째 행렬의 행 수와 같은지 확인하십시오. 둘 다 동일하면 계속 진행하고, 그렇지 않으면 '불가능' 출력을 생성합니다.
재귀 행렬 곱셈에서는 재귀 호출을 통해 세 가지 반복 루프를 구현합니다. 내부에서 가장 재귀적인 호출 곱셈행렬() k(col1 또는 row2)를 반복하는 것입니다. 두 번째 재귀 호출 곱셈행렬() 열을 변경하는 것이고 가장 바깥쪽 재귀 호출은 행을 변경하는 것입니다.
아래는 재귀 행렬 곱셈 코드입니다.
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(row1 * col2* col1)
보조 공간: O(log (max(row1col2)) 재귀로 인해 암시적 스택이 사용되므로퀴즈 만들기
