[C/C++] Đếm số lần xuất hiện ma trận A trong ma trận B

Yêu cầu:
Cho 2 ma trận số thực A và B.
Đếm số lần xuất hiên ma trận A trong ma trận B

Thuật toán:
Về idea, dịch duyển và so sánh ma trận A và ma trận B như hình vẽ sau:

Giả sử ma trận A có kích thước là aRow x aCol
Giả sử ma trận B có kích thước là bRow x bCol
– Duyệt ma trận B theo hàng và cột (hàng: 0 ~ (bRow – aRow), cột: 0 ~ (bCol – aCol))
– Duyệt ma trận A theo hàng và cột (hàng: 0 ~ aRow, cột: 0 ~ aCol)
+ Compare phần tử tương ứng của 2 ma trận A và B
+ Nếu tất cả các phần tử của 2 ma trận A và B giống nhau, tăng biến đếm cnt
– Kết thúc việc duyệt ma trận B, trả về giá trị biến cnt

Code:

/******Count the number appearance of matrix A in B*********
*Author: vncoding
*Date : 11/05/2019
************************************************************/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define N 100
#define M 100

void ImportData(int[][M], int, int, char*);
void PrintMatrix(int[][M], int, int, char);
int ASubnetBMatrix(int[][M], int[][M], int, int, int, int);


void main()
{
    int aRow, aCol;
    int bRow, bCol;
    float average;
    int A[N][M];
    int B[N][M];
    int res;

    printf("\nNumber of row: ");
    scanf("%d", &aRow);
    printf("\nNumber of column: ");
    scanf("%d", &aCol);

    ImportData(A, aRow, aCol, "A");

    printf("\nNumber of row: ");
    scanf("%d", &bRow);
    printf("\nNumber of column: ");
    scanf("%d", &bCol);

    ImportData(B, bRow, bCol, "B");

    PrintMatrix(A, aRow, aCol, 'A');
    PrintMatrix(B, bRow, bCol, 'B');

    res = ASubnetBMatrix(A, B, aRow, aCol, bRow, bCol);

    if (res)
        printf("\nThe number appearance of matrix A in B: %d", res);
    else
        printf("\nMatrix A is not subnet of matrix B");

    getch();
}

/*************************************************************
* Function      : ASubnetBMatrix()
* Parameter     : A[][M]: input matrix (I)
*               : B[][M]: input matrix (I)
*                 aRow  : row number of matrix A (I)
*                 aCol  : column number of matrix A (I)
*                 bRow  : row number of matrix B (I)
*                 bCol  : column number of matrix B(I)
*
* Return        : the number appearance of matrix A in B
*                 
* Description   : count the number appearance of matrix A in B
*************************************************************/
int ASubnetBMatrix(int A[][M], int B[][M], int aRow, int aCol, int bRow, int bCol)
{
    int iARow, iACol;
    int iBRow, iBCol;
    bool flg;
    int cnt = 0;

    for (iBRow = 0; iBRow <= bRow - aRow; iBRow++)
    {
        for (iBCol = 0; iBCol <= bCol - aCol; iBCol++)
        {
            flg = true;
            for (iARow = 0; iARow < aRow; iARow++)
            {
                for (iACol = 0; iACol < aCol; iACol++)
                {
                    if (A[iARow][iACol] != B[iBRow + iARow][iBCol + iACol])
                    {
                        flg = false;
                        break;
                    }
                }
                if (flg == false)
                {
                    break;
                }
            }
            if (flg == true)
            {
                cnt++;
            }
        }
    }

    return cnt;

}

/*************************************************************
* Function      : ImportData()
* Parameter     : A[][M]: input matrix (I)
                  nRow  : row number   (I)
                  nCol  : column number(I)
                  nameMatrix: matrix name (I)
* Return        : void
* Description   : Import matrix data
*************************************************************/
void ImportData(int Matrix[][M], int nRow, int nCol, char* nameMatrix)
{
    int iRow, iCol;
    for (iRow = 0; iRow < nRow; iRow++)
        for (iCol = 0; iCol < nCol; iCol++)
        {
            printf("\n%s[%d][%d] = ", nameMatrix, iRow, iCol);
            scanf("%d", &Matrix[iRow][iCol]);
        }
}

/*************************************************************
* Function      : PrintMatrix()
* Parameter     : Matrix: input matrix (I)
                  nRow  : row number   (I)
                  nCol  : column number(I)
                  name  : name of matrix (I)
* Return        : void
* Description   : Display matrix data
*************************************************************/
void PrintMatrix(int Matrix[][M], int nRow, int nCol, char name)
{
    int iRow, iCol;
    printf("\n%c = ", name);
    for (iRow = 0; iRow < nRow; iRow++)
    {
        printf("\n");
        for (iCol = 0; iCol < nCol; iCol++)
        {
            printf("\t%d\t", Matrix[iRow][iCol]);
        }
    }
}

Kết quả:

Number of row: 2
Number of column: 3

A[0][0] = 1
A[0][1] = 2
A[0][2] = 3
A[1][0] = 5
A[1][1] = 6
A[1][2] = 7

Number of row: 4
Number of column: 4

B[0][0] = 1
B[0][1] = 2
B[0][2] = 3
B[0][3] = 4
B[1][0] = 5
B[1][1] = 6
B[1][2] = 7
B[1][3] = 8
B[2][0] = 9
B[2][1] = 1
B[2][2] = 2
B[2][3] = 3
B[3][0] = 13
B[3][1] = 5
B[3][2] = 6
B[3][3] = 7

A =
        1               2               3
        5               6               7
B =
        1               2               3               4
        5               6               7               8
        9               1               2               3
        13              5               6               7

The number appearance of matrix A in B: 2

Be the first to comment

Leave a Reply