Праверце, ці аднолькавыя дзве дадзеныя матрыцы


Узровень складанасці Лёгка
Часта пытаюцца ў Пацвердзіце Амеё DiDi Pony.ai
масіў матрыца Школьнае праграмаванне

Пастаноўка праблемы

Улічваючы дзве матрыцы, мы напішам функцыю, каб праверыць, ці ідэнтычныя дзве матрыцы. Гэта значыць, калі ўсе элементы ў адпаведных пазіцыях дзвюх матрыц аднолькавыя, то мы кажам, што яны аднолькавыя.

Уваходны фармат

Першы радок змяшчае чатыры цэлыя значэнні r1, c1, r2, c2. Дзе r1 і c1 абазначаюць колькасць радкоў і слупкоў першай матрыцы. А r2, c2 абазначае колькасць радкоў, слупкоў секунды матрыца.

Наступныя r1 радкі, якія ўтрымліваюць цэлыя значэнні c1.

І наступныя r2 радкі, якія змяшчаюць цэлыя значэнні c2.

Фармат вываду

РаздрукавацьIdentical matrices"Калі матрыцы ідэнтычныя, у адваротным выпадку надрукуйце"Not identical matrices».

Constraints

  • 1 <= r1, c1, r2, c2 <= 5000.
  • 1 <= | m [i] [j] | <= 10 ^ 9, дзе m - матрыца і становішча элемента ў i-м радку і j-м слупку.

Прыклад

4 4 4 4   
1 4 7 9
1 6 7 6
6 3 7 12
4 4 4 4
1 4 7 9
1 6 7 6
6 3 7 12
4 4 4 4
Identical matrices

Тлумачэнне: У прыведзеным прыкладзе ўсе элементы ў матрыцах аднолькавыя, таму ідэнтычныя.

Давайце паглядзім, як праверыць усе элементы ў матрыцах, прытрымліваючыся малюнку ніжэй. Гэта яшчэ адзін прыклад для лепшага разумення.

Алгарытм праверкі, ці аднолькавыя дзве зададзеныя матрыцы

1. Для кожнага радка з дзвюх матрыц параўнайце элементы гэтага радка.

1.1 Калі тое самае, перайдзіце да наступнага радка.

1.2 У іншым выпадку "матрыцы не ідэнтычныя".

2. Калі цыкл не разарваўся, то матрыцы ідэнтычныя.

Рэалізацыя

Праграма 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];
    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];
        }
    }
    if(c1!=c2 || r1!=r2)
    {
        cout<<"Not identical matrices";
    }
    else
    {
    int flag=0;    
    for(int i=0;i<r1;i++)
    {
        for(int j=0;j<c1;j++)
        {
            if(a[i][j]!=b[i][j])
            {
                flag=1;
                break;
            }
        }
    }
    if(flag==1)
    {
        cout<<"Identical matrices";
    }
    }
    return 0;
}

Праграма Java для праверкі аднолькавасці дзвюх дадзеных матрыц

import java.io.*; 
import java.util.Scanner;
class sum
{ 
    // 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();
            }
        }
        if(r1!=r2 && c1!=c2) 
        { 
            System.out.println("\nNot identical matrices"); 
        } 
        else
        {
            for(int i=0;i<r1;i++)
            {
                for(int j=0;j<c1;j++)
                {
                    if(a[i][j]!=b[i][j])
                    {
                        System.out.println("\nNot identical matrices");
                        return;
                    }
                }
            }
            System.out.println("\nIdentical matrices");
        }
    } 
}
2 2 2 2
1 2
3 4
1 2
3 4
Identical matrices

Аналіз складанасці для праверкі, ці аднолькавыя дзве дадзеныя матрыцы

Складанасць часу

O (n ^ 2) дзе n - максімум r1 і c1. Тут мы проста запускаем дзве завесы, першы цыкл запускаецца r1 раз, а другі цыкл - c1 раз.

Касмічная складанасць

O (1) таму што мы не ствараем дадатковай прасторы для пошуку выніку. Тут мы заявілі толькі памер r1 * c1 для ўводу першай матрыцы і памер r2 * c2 для ўводу другой матрыцы.

Спасылка