Dadas dos arrays cuadradas A y B de tamaño nxn cada una, encuentre su array de multiplicación.
Método ingenuo : a continuación se muestra una forma sencilla de multiplicar dos arrays.
C++
void multiply(int A[][N], int B[][N], int C[][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
C[i][j] = 0;
for (int k = 0; k < N; k++)
{
C[i][j] += A[i][k]*B[k][j];
}
}
}
}
// This code is contributed by noob2000.
C
void multiply(int A[][N], int B[][N], int C[][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
C[i][j] = 0;
for (int k = 0; k < N; k++)
{
C[i][j] += A[i][k]*B[k][j];
}
}
}
}
Java
// java code
static int multiply(int A[][N], int B[][N], int C[][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
C[i][j] = 0;
for (int k = 0; k < N; k++)
{
C[i][j] += A[i][k]*B[k][j];
}
}
}
}
// This code is contributed by shivanisinghss2110
Python3
def multiply(A, B, C): for i in range(N): for j in range( N): C[i][j] = 0 for k in range(N): C[i][j] += A[i][k]*B[k][j] # this code is contributed by shivanisinghss2110
C#
// C# code
static int multiply(int A[,N], int B[,N], int C[,N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
C[i,j] = 0;
for (int k = 0; k < N; k++)
{
C[i,j] += A[i,k]*B[k,j];
}
}
}
}
// This code is contributed by rutvik_56.
Javascript
<script>
function multiply(A, B, C)
{
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
C[i][j] = 0;
for (var k = 0; k < N; k++)
{
C[i][j] += A[i][k]*B[k][j];
}
}
}
}
</script>
C++
#include <bits/stdc++.h>
using namespace std;
#define ROW_1 4
#define COL_1 4
#define ROW_2 4
#define COL_2 4
void print(string display, vector<vector<int> > matrix,
int start_row, int start_column, int end_row,
int end_column)
{
cout << endl << display << " =>" << endl;
for (int i = start_row; i <= end_row; i++) {
for (int j = start_column; j <= end_column; j++) {
cout << setw(10);
cout << matrix[i][j];
}
cout << endl;
}
cout << endl;
return;
}
void add_matrix(vector<vector<int> > matrix_A,
vector<vector<int> > matrix_B,
vector<vector<int> >& matrix_C,
int split_index)
{
for (auto i = 0; i < split_index; i++)
for (auto j = 0; j < split_index; j++)
matrix_C[i][j]
= matrix_A[i][j] + matrix_B[i][j];
}
vector<vector<int> >
multiply_matrix(vector<vector<int> > matrix_A,
vector<vector<int> > matrix_B)
{
int col_1 = matrix_A[0].size();
int row_1 = matrix_A.size();
int col_2 = matrix_B[0].size();
int row_2 = matrix_B.size();
if (col_1 != row_2) {
cout << "\nError: The number of columns in Matrix "
"A must be equal to the number of rows in "
"Matrix B\n";
return {};
}
vector<int> result_matrix_row(col_2, 0);
vector<vector<int> > result_matrix(row_1,
result_matrix_row);
if (col_1 == 1)
result_matrix[0][0]
= matrix_A[0][0] * matrix_B[0][0];
else {
int split_index = col_1 / 2;
vector<int> row_vector(split_index, 0);
vector<vector<int> > result_matrix_00(split_index,
row_vector);
vector<vector<int> > result_matrix_01(split_index,
row_vector);
vector<vector<int> > result_matrix_10(split_index,
row_vector);
vector<vector<int> > result_matrix_11(split_index,
row_vector);
vector<vector<int> > a00(split_index, row_vector);
vector<vector<int> > a01(split_index, row_vector);
vector<vector<int> > a10(split_index, row_vector);
vector<vector<int> > a11(split_index, row_vector);
vector<vector<int> > b00(split_index, row_vector);
vector<vector<int> > b01(split_index, row_vector);
vector<vector<int> > b10(split_index, row_vector);
vector<vector<int> > b11(split_index, row_vector);
for (auto i = 0; i < split_index; i++)
for (auto j = 0; j < split_index; j++) {
a00[i][j] = matrix_A[i][j];
a01[i][j] = matrix_A[i][j + split_index];
a10[i][j] = matrix_A[split_index + i][j];
a11[i][j] = matrix_A[i + split_index]
[j + split_index];
b00[i][j] = matrix_B[i][j];
b01[i][j] = matrix_B[i][j + split_index];
b10[i][j] = matrix_B[split_index + i][j];
b11[i][j] = matrix_B[i + split_index]
[j + split_index];
}
add_matrix(multiply_matrix(a00, b00),
multiply_matrix(a01, b10),
result_matrix_00, split_index);
add_matrix(multiply_matrix(a00, b01),
multiply_matrix(a01, b11),
result_matrix_01, split_index);
add_matrix(multiply_matrix(a10, b00),
multiply_matrix(a11, b10),
result_matrix_10, split_index);
add_matrix(multiply_matrix(a10, b01),
multiply_matrix(a11, b11),
result_matrix_11, split_index);
for (auto i = 0; i < split_index; i++)
for (auto j = 0; j < split_index; j++) {
result_matrix[i][j]
= result_matrix_00[i][j];
result_matrix[i][j + split_index]
= result_matrix_01[i][j];
result_matrix[split_index + i][j]
= result_matrix_10[i][j];
result_matrix[i + split_index]
[j + split_index]
= result_matrix_11[i][j];
}
result_matrix_00.clear();
result_matrix_01.clear();
result_matrix_10.clear();
result_matrix_11.clear();
a00.clear();
a01.clear();
a10.clear();
a11.clear();
b00.clear();
b01.clear();
b10.clear();
b11.clear();
}
return result_matrix;
}
int main()
{
vector<vector<int> > matrix_A = { { 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 2, 2, 2, 2 } };
print("Array A", matrix_A, 0, 0, ROW_1 - 1, COL_1 - 1);
vector<vector<int> > matrix_B = { { 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 2, 2, 2, 2 } };
print("Array B", matrix_B, 0, 0, ROW_2 - 1, COL_2 - 1);
vector<vector<int> > result_matrix(
multiply_matrix(matrix_A, matrix_B));
print("Result Array", result_matrix, 0, 0, ROW_1 - 1,
COL_2 - 1);
}
// Time Complexity: O(n^3)
// Code Contributed By: lucasletum
Java
//Java program to find the resultant
//product matrix for a given pair of matrices
//using Divide and Conquer Approach
import java.io.*;
import java.util.*;
class GFG {
static int ROW_1 = 4,COL_1 = 4, ROW_2 = 4, COL_2 = 4;
public static void printMat(int[][] a, int r, int c){
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
System.out.print(a[i][j]+" ");
}
System.out.println("");
}
System.out.println("");
}
public static void print(String display, int[][] matrix,int start_row, int start_column, int end_row,int end_column)
{
System.out.println(display + " =>\n");
for (int i = start_row; i <= end_row; i++) {
for (int j = start_column; j <= end_column; j++) {
//cout << setw(10);
System.out.print(matrix[i][j]+" ");
}
System.out.println("");
}
System.out.println("");
}
public static void add_matrix(int[][] matrix_A,int[][] matrix_B,int[][] matrix_C, int split_index)
{
for (int i = 0; i < split_index; i++){
for (int j = 0; j < split_index; j++){
matrix_C[i][j] = matrix_A[i][j] + matrix_B[i][j];
}
}
}
public static void initWithZeros(int a[][], int r, int c){
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
a[i][j]=0;
}
}
}
public static int[][] multiply_matrix(int[][] matrix_A,int[][] matrix_B)
{
int col_1 = matrix_A[0].length;
int row_1 = matrix_A.length;
int col_2 = matrix_B[0].length;
int row_2 = matrix_B.length;
if (col_1 != row_2) {
System.out.println("\nError: The number of columns in Matrix A must be equal to the number of rows in Matrix B\n");
int temp[][] = new int[1][1];
temp[0][0]=0;
return temp;
}
int[] result_matrix_row = new int[col_2];
Arrays.fill(result_matrix_row,0);
int[][] result_matrix = new int[row_1][col_2];
initWithZeros(result_matrix,row_1,col_2);
if (col_1 == 1){
result_matrix[0][0] = matrix_A[0][0] * matrix_B[0][0];
}else {
int split_index = col_1 / 2;
int[] row_vector = new int[split_index];
Arrays.fill(row_vector,0);
int[][] result_matrix_00 = new int[split_index][split_index];
int[][] result_matrix_01 = new int[split_index][split_index];
int[][] result_matrix_10 = new int[split_index][split_index];
int[][] result_matrix_11 = new int[split_index][split_index];
initWithZeros(result_matrix_00,split_index,split_index);
initWithZeros(result_matrix_01,split_index,split_index);
initWithZeros(result_matrix_10,split_index,split_index);
initWithZeros(result_matrix_11,split_index,split_index);
int[][] a00 = new int[split_index][split_index];
int[][] a01 = new int[split_index][split_index];
int[][] a10 = new int[split_index][split_index];
int[][] a11 = new int[split_index][split_index];
int[][] b00 = new int[split_index][split_index];
int[][] b01 = new int[split_index][split_index];
int[][] b10 = new int[split_index][split_index];
int[][] b11 = new int[split_index][split_index];
initWithZeros(a00,split_index,split_index);
initWithZeros(a01,split_index,split_index);
initWithZeros(a10,split_index,split_index);
initWithZeros(a11,split_index,split_index);
initWithZeros(b00,split_index,split_index);
initWithZeros(b01,split_index,split_index);
initWithZeros(b10,split_index,split_index);
initWithZeros(b11,split_index,split_index);
for (int i = 0; i < split_index; i++){
for (int j = 0; j < split_index; j++) {
a00[i][j] = matrix_A[i][j];
a01[i][j] = matrix_A[i][j + split_index];
a10[i][j] = matrix_A[split_index + i][j];
a11[i][j] = matrix_A[i + split_index][j + split_index];
b00[i][j] = matrix_B[i][j];
b01[i][j] = matrix_B[i][j + split_index];
b10[i][j] = matrix_B[split_index + i][j];
b11[i][j] = matrix_B[i + split_index][j + split_index];
}
}
add_matrix(multiply_matrix(a00, b00),multiply_matrix(a01, b10),result_matrix_00, split_index);
add_matrix(multiply_matrix(a00, b01),multiply_matrix(a01, b11),result_matrix_01, split_index);
add_matrix(multiply_matrix(a10, b00),multiply_matrix(a11, b10),result_matrix_10, split_index);
add_matrix(multiply_matrix(a10, b01),multiply_matrix(a11, b11),result_matrix_11, split_index);
for (int i = 0; i < split_index; i++){
for (int j = 0; j < split_index; j++) {
result_matrix[i][j] = result_matrix_00[i][j];
result_matrix[i][j + split_index] = result_matrix_01[i][j];
result_matrix[split_index + i][j] = result_matrix_10[i][j];
result_matrix[i + split_index] [j + split_index] = result_matrix_11[i][j];
}
}
}
return result_matrix;
}
public static void main (String[] args) {
int[][] matrix_A = { { 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 2, 2, 2, 2 } };
System.out.println("Array A =>");
printMat(matrix_A,4,4);
int[][] matrix_B = { { 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 2, 2, 2, 2 } };
System.out.println("Array B =>");
printMat(matrix_B,4,4);
int[][] result_matrix = multiply_matrix(matrix_A, matrix_B);
System.out.println("Result Array =>");
printMat(result_matrix,4,4);
}
}
// Time Complexity: O(n^3)
//This code is contributed by shruti456rawal
C++
#include <bits/stdc++.h>
using namespace std;
#define ROW_1 4
#define COL_1 4
#define ROW_2 4
#define COL_2 4
void print(string display, vector<vector<int> > matrix,
int start_row, int start_column, int end_row,
int end_column)
{
cout << endl << display << " =>" << endl;
for (int i = start_row; i <= end_row; i++) {
for (int j = start_column; j <= end_column; j++) {
cout << setw(10);
cout << matrix[i][j];
}
cout << endl;
}
cout << endl;
return;
}
vector<vector<int> >
add_matrix(vector<vector<int> > matrix_A,
vector<vector<int> > matrix_B, int split_index,
int multiplier = 1)
{
for (auto i = 0; i < split_index; i++)
for (auto j = 0; j < split_index; j++)
matrix_A[i][j]
= matrix_A[i][j]
+ (multiplier * matrix_B[i][j]);
return matrix_A;
}
vector<vector<int> >
multiply_matrix(vector<vector<int> > matrix_A,
vector<vector<int> > matrix_B)
{
int col_1 = matrix_A[0].size();
int row_1 = matrix_A.size();
int col_2 = matrix_B[0].size();
int row_2 = matrix_B.size();
if (col_1 != row_2) {
cout << "\nError: The number of columns in Matrix "
"A must be equal to the number of rows in "
"Matrix B\n";
return {};
}
vector<int> result_matrix_row(col_2, 0);
vector<vector<int> > result_matrix(row_1,
result_matrix_row);
if (col_1 == 1)
result_matrix[0][0]
= matrix_A[0][0] * matrix_B[0][0];
else {
int split_index = col_1 / 2;
vector<int> row_vector(split_index, 0);
vector<vector<int> > a00(split_index, row_vector);
vector<vector<int> > a01(split_index, row_vector);
vector<vector<int> > a10(split_index, row_vector);
vector<vector<int> > a11(split_index, row_vector);
vector<vector<int> > b00(split_index, row_vector);
vector<vector<int> > b01(split_index, row_vector);
vector<vector<int> > b10(split_index, row_vector);
vector<vector<int> > b11(split_index, row_vector);
for (auto i = 0; i < split_index; i++)
for (auto j = 0; j < split_index; j++) {
a00[i][j] = matrix_A[i][j];
a01[i][j] = matrix_A[i][j + split_index];
a10[i][j] = matrix_A[split_index + i][j];
a11[i][j] = matrix_A[i + split_index]
[j + split_index];
b00[i][j] = matrix_B[i][j];
b01[i][j] = matrix_B[i][j + split_index];
b10[i][j] = matrix_B[split_index + i][j];
b11[i][j] = matrix_B[i + split_index]
[j + split_index];
}
vector<vector<int> > p(multiply_matrix(
a00, add_matrix(b01, b11, split_index, -1)));
vector<vector<int> > q(multiply_matrix(
add_matrix(a00, a01, split_index), b11));
vector<vector<int> > r(multiply_matrix(
add_matrix(a10, a11, split_index), b00));
vector<vector<int> > s(multiply_matrix(
a11, add_matrix(b10, b00, split_index, -1)));
vector<vector<int> > t(multiply_matrix(
add_matrix(a00, a11, split_index),
add_matrix(b00, b11, split_index)));
vector<vector<int> > u(multiply_matrix(
add_matrix(a01, a11, split_index, -1),
add_matrix(b10, b11, split_index)));
vector<vector<int> > v(multiply_matrix(
add_matrix(a00, a10, split_index, -1),
add_matrix(b00, b01, split_index)));
vector<vector<int> > result_matrix_00(add_matrix(
add_matrix(add_matrix(t, s, split_index), u,
split_index),
q, split_index, -1));
vector<vector<int> > result_matrix_01(
add_matrix(p, q, split_index));
vector<vector<int> > result_matrix_10(
add_matrix(r, s, split_index));
vector<vector<int> > result_matrix_11(add_matrix(
add_matrix(add_matrix(t, p, split_index), r,
split_index, -1),
v, split_index, -1));
for (auto i = 0; i < split_index; i++)
for (auto j = 0; j < split_index; j++) {
result_matrix[i][j]
= result_matrix_00[i][j];
result_matrix[i][j + split_index]
= result_matrix_01[i][j];
result_matrix[split_index + i][j]
= result_matrix_10[i][j];
result_matrix[i + split_index]
[j + split_index]
= result_matrix_11[i][j];
}
a00.clear();
a01.clear();
a10.clear();
a11.clear();
b00.clear();
b01.clear();
b10.clear();
b11.clear();
p.clear();
q.clear();
r.clear();
s.clear();
t.clear();
u.clear();
v.clear();
result_matrix_00.clear();
result_matrix_01.clear();
result_matrix_10.clear();
result_matrix_11.clear();
}
return result_matrix;
}
int main()
{
vector<vector<int> > matrix_A = { { 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 2, 2, 2, 2 } };
print("Array A", matrix_A, 0, 0, ROW_1 - 1, COL_1 - 1);
vector<vector<int> > matrix_B = { { 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 2, 2, 2, 2 } };
print("Array B", matrix_B, 0, 0, ROW_2 - 1, COL_2 - 1);
vector<vector<int> > result_matrix(
multiply_matrix(matrix_A, matrix_B));
print("Result Array", result_matrix, 0, 0, ROW_1 - 1,
COL_2 - 1);
}
// Time Complexity: T(N) = 7T(N/2) + O(N^2) => O(N^Log7)
// which is approximately O(N^2.8074) Code Contributed By:
// lucasletum
Python3
# Version 3.6 import numpy as np def split(matrix): """ Splits a given matrix into quarters. Input: nxn matrix Output: tuple containing 4 n/2 x n/2 matrices corresponding to a, b, c, d """ row, col = matrix.shape row2, col2 = row//2, col//2 return matrix[:row2, :col2], matrix[:row2, col2:], matrix[row2:, :col2], matrix[row2:, col2:] def strassen(x, y): """ Computes matrix product by divide and conquer approach, recursively. Input: nxn matrices x and y Output: nxn matrix, product of x and y """ # Base case when size of matrices is 1x1 if len(x) == 1: return x * y # Splitting the matrices into quadrants. This will be done recursively # until the base case is reached. a, b, c, d = split(x) e, f, g, h = split(y) # Computing the 7 products, recursively (p1, p2...p7) p1 = strassen(a, f - h) p2 = strassen(a + b, h) p3 = strassen(c + d, e) p4 = strassen(d, g - e) p5 = strassen(a + d, e + h) p6 = strassen(b - d, g + h) p7 = strassen(a - c, e + f) # Computing the values of the 4 quadrants of the final matrix c c11 = p5 + p4 - p2 + p6 c12 = p1 + p2 c21 = p3 + p4 c22 = p1 + p5 - p3 - p7 # Combining the 4 quadrants into a single matrix by stacking horizontally and vertically. c = np.vstack((np.hstack((c11, c12)), np.hstack((c21, c22)))) return c
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA