Екі матрицаны көбейту  


Күрделілік дәрежесі оңай
Жиі кіреді Amazon алма Facebook тілек
Array Matrix

Проблемалық мәлімдеме  

«Екі матрицаны көбейту» есебінде біз екі матрица келтірдік. Біз осы матрицаларды көбейтіп, нәтижені немесе соңғы нұсқаны шығаруымыз керек Матрица. Мұндағы қажетті және жеткілікті шарт - А бағанының саны В матрицасындағы жолдар санына тең болуы керек. Егер бұл шарт дұрыс болмаса, онда біз бұл матрицаларды көбейте алмаймыз.

Кіріс форматы  

R1, c1, r2, c2 төрт бүтін мәні бар бірінші жол. Мұндағы r1 және c1 бірінші матрицаның жолдары мен бағандарының санын білдіреді. Ал r2, c2 екінші матрицаның жолдарының, бағандарының санын білдіреді.

Келесі r1 жолында c1 бүтін мәндері бар.

Келесі r2 жолында с2 бүтін мәндері бар.

Шығу форматы  

Көбейткеннен кейін соңғы матрицаны әр жол жаңа жолдан басталатындай етіп шығарыңыз және әр элемент әр жолда бос орынмен бөлінеді.

Шектеу  

  • 1 <= r1, c1, r2, c2 <= 2000.
  • 1 <= | m [i] [j] | <= 10 ^ 9, мұндағы m - матрица және ith жол мен j бағандағы элементтің орны.

мысал  

4 4 4 4
1 1 1 1
1 6 7 6
6 3 7 12
4 4 4 4
1 1 1 1
2 2 2 2
3 3 3 3
4 9 1 7
10 15 7 13
58 88 40 76
81 141 45 117
40 60 28 52

Түсіндіру: Жоғарыда келтірілген мысалда біз А матрицасының бірінші қатарындағы барлық сәйкес элементтерді В матрицасының бірінші бағанындағы элементтермен көбейтіп, оларды қосу арқылы алғашқы элементті алдық. Сол сияқты шығудың бірінші жолындағы екінші элемент үшін біз А матрицасының бірінші қатарын және В матрицасының екінші бағанын алуымыз керек. Осылайша, біз шығыс матрицасындағы барлық элементтерді алдық.

Сондай-ақ, қараңыз
Динамикалық бағдарламалауды қолдана отырып, матрицалық тізбекті көбейту

Төменде матрицаны көбейтудің кездейсоқ мысалы келтірілген.

Екі матрицаны көбейту  

Екі матрицаны көбейту алгоритмі  

1. Жай үш циклды іске қосыңыз.
2. А матрицасындағы i айнымалысы бар әр жол үшін цикл.
3. Жоғарыдағы цикл ішінде, j матасы айнымалы В матрицасындағы әрбір бағанға арналған цикл.
4. Жоғарыда аталған екі цикл ішінде k матрицасы бар А матрицасындағы әр жол элементіне және B матрицасындағы баған элементінің әрқайсысына k, яғни A [i] [k] және B [k] [j].
5. әр жол элементінің көбейтіндісін A-дағы баған элементтерімен, яғни A [i] [k] * B [k] [j] және барлық өнімдерді қосып, жаңа C матрицасында сақтаймыз, яғни C [i] [j].
6. С матрицасы - көбейтудің нәтижесі.

Іске асыру  

Екі матрицаны көбейтуге арналған C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;
    int a[r1][c1];
    int b[r2][c2];
    if(c1!=r2)
    {
        cout<<"We can’t multiply these matrices.";
    }
    else
    {
    for(int i=0;i<r1;i++)
    {
        for(int j=0;j<c1;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=0;i<r2;i++)
    {
        for(int j=0;j<c2;j++)
        {
            cin>>b[i][j];
        }
    }
    int c[r1][c2];
    for(int i=0; i <r1; i++)
    {
        for(int j=0; j<c2; j++)
        {
            int sum = 0;
            for(int k=0;k<c1;k++)
            {
                sum += a[i][k] * b[k][j];
            }
            c[i][j] = sum;
            cout<<c[i][j]<<"  ";
        }
        cout<<endl;
    }
    }
    return 0;
}

Екі матрицаны көбейтуге арналған Java бағдарламасы

import java.io.*; 
import java.util.Scanner;

class TutorialCup
{
    // Function to print Matrix 
    static void print_matrix(int output[][], int r, int c) 
    { 
        for(int i=0;i<r;i++) 
        { 
            for(int j=0;j<c;j++)
            {
                System.out.print(output[i][j] + " "); 
            }
            System.out.println(); 
        } 
    } 
    // Function to multiply two matrices a[][] and b[][] 
    static void multiply(int r1, int c1, int r2, int c2, int a[][], int b[][]) 
    { 
        int i, j, k; 
        // Check if multiplication is Possible 
        if(r2!=c1) 
        { 
            System.out.println("\nWe can’t multiply these matrices."); 
            return; 
        } 
        // Matrix to store the result 
        //The product matrix will be of size row1 x col2 
        int c[][] = new int[r1][c2];  
        // Multiply the two marices 
        for(i=0;i<r1;i++) 
        { 
            for(j=0;j<c2;j++) 
            { 
                for(k=0;k<r2;k++) 
                {
                    c[i][j]+=a[i][k]*b[k][j];
                } 
            } 
        } 
        print_matrix(c,r1,c2); 
    } 
    // Driver code 
    public static void main(String[] args) 
    { 
        int r1,c1,r2,c2;
        Scanner inp = new Scanner(System.in);
        r1 = inp.nextInt();
        c1 = inp.nextInt();
        r2 = inp.nextInt();
        c2 = inp.nextInt();
        int a[][] = new int[r1][c1];
        for(int i=0;i<r1;i++)
        {
            for(int j=0;j<c1;j++)
            {
                a[i][j]=inp.nextInt();
            }
        }
        int b[][] = new int[r2][c2];
        for(int i=0;i<r2;i++)
        {
            for(int j=0;j<c2;j++)
            {
                b[i][j]=inp.nextInt();
            }
        }
        multiply(r1,c1,r2,c2,a,b); 
    } 
}
2 3 3 2
1 2 3
4 5 6
7 8
9 10
11 12
58 64 
139 154

Екі матрицаны көбейтудің күрделілігін талдау  

Уақыттың күрделілігі

O (n ^ 3) мұндағы n - r1, c2 және r2 максимумдары. Мұнда біз жай үш циклды r1 рет, екінші циклды c2 рет, ал соңғы циклды r2 рет орындаймыз.

Сондай-ақ, қараңыз
Минималды жол қосындысы

Ғарыштың күрделілігі

O (м * м) Мұндағы m - максимум r1 және с2. Бұл жерде біз матрицаларды көбейту нәтижесін сақтауға қосымша орын жасаймыз. Мұнда біз бірінші матрицаны қабылдау үшін r1 * c1 өлшемін, ал екінші матрицаны қабылдау үшін r2 * c2 өлшемін жарияладық.

анықтамалық