Dada una array cuadrada mat[][] y un número entero N , la tarea es imprimir la array después de multiplicar la array N veces .
Ejemplos:
Entrada: mat[][] = {{1, 2, 3}, {3, 4, 5}, {6, 7, 9}}, N = 2
Salida:
25 31 40
45 57 74
81 103 134Entrada: mat[][] = {{1, 2}, {3, 4}}, N = 3
Salida:
37 54
81 118
Planteamiento: La idea es utilizar la array identidad de Multiplicación de arrays . es decir, A = IA y A = AI , donde A es una array de N * M dimensiones de orden e I es la array identidad de dimensiones M * N , donde N es el número total de filas y M es el número total de columnas en una array
La idea es iterar sobre el rango [1, N] y actualizar la Array de Identidad con AI para que después de calcular el valor de A 2 = AA , A 3 pueda calcularse como AA 2 y así sucesivamente hasta AN .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function for matrix multiplication void power(vector<vector<int>>& I, vector<vector<int>>& a, int rows, int cols) { // Stores the resultant matrix // after multiplying a[][] by I[][] vector<vector<int>> res(rows, vector<int>(cols)); // Matrix multiplication for(int i = 0; i < rows; ++i) { for(int j = 0; j < cols; ++j) { for(int k = 0; k < rows; ++k) { res[i][j] += a[i][k] * I[k][j]; } } } // Updating identity element // of a matrix for(int i = 0; i < rows; ++i) { for(int j = 0; j < cols; ++j) { I[i][j] = res[i][j]; } } } // Function to print the given matrix void print(vector<vector<int> >& a) { // Traverse the row for(int i = 0; i < a.size(); ++i) { // Traverse the column for(int j = 0; j < a[0].size(); ++j) { cout << a[i][j] << " "; } cout << "\n"; } } // Function to multiply the given // matrix N times void multiply(vector<vector<int> >& arr, int N) { // Identity element of matrix vector<vector<int>> I(arr.size(), vector<int>(arr[0].size())); // Update the Identity Matrix for(int i = 0; i < arr.size(); ++i) { for(int j = 0; j < arr[0].size(); ++j) { // For the diagonal element if (i == j) { I[i][j] = 1; } else { I[i][j] = 0; } } } // Multiply the matrix N times for(int i = 1; i <= N; ++i) { power(I, arr, arr.size(), arr[0].size()); } // Update the matrix arr[i] to // to identity matrix for(int i = 0; i < arr.size(); ++i) { for(int j = 0; j < arr[0].size(); ++j) { arr[i][j] = I[i][j]; } } // Print the matrix print(arr); } // Driver Code int main() { // Given 2d array vector<vector<int>> arr = { { 1, 2, 3 }, { 3, 4, 5 }, { 6, 7, 9 } }; // Given N int N = 2; // Function Call multiply(arr, N); return 0; } // This code is contributed by akhilsaini
Java
// Java program for the above approach import java.io.*; class GFG { // Function for matrix multiplication static void power(int I[][], int a[][], int rows, int cols) { // Stores the resultant matrix // after multiplying a[][] by I[][] int res[][] = new int[rows][cols]; // Matrix multiplication for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { for (int k = 0; k < rows; ++k) { res[i][j] += a[i][k] * I[k][j]; } } } // Updating identity element // of a matrix for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { I[i][j] = res[i][j]; } } } // Function to print the given matrix static void print(int a[][]) { // Traverse the row for (int i = 0; i < a.length; ++i) { // Traverse the column for (int j = 0; j < a[0].length; ++j) { System.out.print(a[i][j] + " "); } System.out.println(); } } // Function to multiply the given // matrix N times public static void multiply( int arr[][], int N) { // Identity element of matrix int I[][] = new int[arr.length][arr[0].length]; // Update the Identity Matrix for (int i = 0; i < arr.length; ++i) { for (int j = 0; j < arr[0].length; ++j) { // For the diagonal element if (i == j) { I[i][j] = 1; } else { I[i][j] = 0; } } } // Multiply the matrix N times for (int i = 1; i <= N; ++i) { power(I, arr, arr.length, arr[0].length); } // Update the matrix arr[i] to // to identity matrix for (int i = 0; i < arr.length; ++i) { for (int j = 0; j < arr[0].length; ++j) { arr[i][j] = I[i][j]; } } // Print the matrix print(arr); } // Driver Code public static void main(String[] args) { // Given 2d array int arr[][] = { { 1, 2, 3 }, { 3, 4, 5 }, { 6, 7, 9 } }; // Given N int N = 2; // Function Call multiply(arr, N); } }
Python3
# Python3 program for the above approach # Function for matrix multiplication def power(I, a, rows, cols): # Stores the resultant matrix # after multiplying a[][] by I[][] res = [[0 for i in range(cols)] for j in range(rows)] # Matrix multiplication for i in range(0, rows): for j in range(0, cols): for k in range(0, rows): res[i][j] += a[i][k] * I[k][j] # Updating identity element # of a matrix for i in range(0, rows): for j in range(0, cols): I[i][j] = res[i][j] # Function to print the given matrix def prints(a): # Traverse the row for i in range(0, len(a)): # Traverse the column for j in range(0, len(a[0])): print(a[i][j], end = ' ') print() # Function to multiply the given # matrix N times def multiply(arr, N): # Identity element of matrix I = [[1 if i == j else 0 for i in range( len(arr))] for j in range( len(arr[0]))] # Multiply the matrix N times for i in range(1, N + 1): power(I, arr, len(arr), len(arr[0])) # Update the matrix arr[i] to # to identity matrix for i in range(0, len(arr)): for j in range(0, len(arr[0])): arr[i][j] = I[i][j] # Print the matrix prints(arr) # Driver Code if __name__ == '__main__': # Given 2d array arr = [ [ 1, 2, 3 ], [ 3, 4, 5 ], [ 6, 7, 9 ] ] # Given N N = 2 # Function Call multiply(arr, N) # This code is contributed by akhilsaini
C#
// C# program for the above approach using System; class GFG{ // Function for matrix multiplication static void power(int[,] I, int[,] a, int rows, int cols) { // Stores the resultant matrix // after multiplying a[][] by I[][] int[,] res = new int[rows, cols]; // Matrix multiplication for(int i = 0; i < rows; ++i) { for(int j = 0; j < cols; ++j) { for(int k = 0; k < rows; ++k) { res[i, j] += a[i, k] * I[k, j]; } } } // Updating identity element // of a matrix for(int i = 0; i < rows; ++i) { for(int j = 0; j < cols; ++j) { I[i, j] = res[i, j]; } } } // Function to print the given matrix static void print(int[, ] a) { // Traverse the row for(int i = 0; i < a.GetLength(0); ++i) { // Traverse the column for(int j = 0; j < a.GetLength(1); ++j) { Console.Write(a[i, j] + " "); } Console.WriteLine(); } } // Function to multiply the given // matrix N times public static void multiply(int[, ] arr, int N) { // Identity element of matrix int[, ] I = new int[arr.GetLength(0), arr.GetLength(1)]; // Update the Identity Matrix for(int i = 0; i < arr.GetLength(0); ++i) { for(int j = 0; j < arr.GetLength(1); ++j) { // For the diagonal element if (i == j) { I[i, j] = 1; } else { I[i, j] = 0; } } } // Multiply the matrix N times for(int i = 1; i <= N; ++i) { power(I, arr, arr.GetLength(0), arr.GetLength(1)); } // Update the matrix arr[i] to // to identity matrix for(int i = 0; i < arr.GetLength(0); ++i) { for(int j = 0; j < arr.GetLength(1); ++j) { arr[i, j] = I[i, j]; } } // Print the matrix print(arr); } // Driver Code public static void Main() { // Given 2d array int[, ] arr = { { 1, 2, 3 }, { 3, 4, 5 }, { 6, 7, 9 } }; // Given N int N = 2; // Function Call multiply(arr, N); } } // This code is contributed by akhilsaini
25 31 40 45 57 74 81 103 134
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA