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
Producción:
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