Матрица внутри другой матрицы - PullRequest
Новая
       8

Матрица внутри другой матрицы

0 голосов
/ 13 декабря 2018

Какой подход я должен использовать, чтобы написать функцию, которая проверяет, содержится ли матрица в другой матрице?Например: 

     matrix A           matrix B
  1   2.  3.  4   5      2  3
  6   7.   8.  9   10    7  8
  11  12. 13. 14  15     12 13
  16  17  18  19  20

Я добавил точки, чтобы указать матрицу B внутри матрицы A.

Я уже написал это: 

#include <stdio.h>

int matrica_sadrzana(int* m1, int v1, int s1, int* m2, int v2, int s2){

    /* What needs to go here? */
    return 0;
}

int main() {
    int i,j,v1,v2,s1,s2,sadrzana;
    int matricaA[100][100],matricaB[100][100];
    printf("Unesite visinu i sirinu matrice A: ");
    scanf("%d %d",&v1,&s1);
    printf("Unesite visinu i sirinu matrice B: ");
    scanf("%d %d",&v2,&s2);
    for(i=0; i<v1; i++){
        for(j=0; j<s1; j++){
            scanf("%d",&matricaA[i][j]);

        }
    }
    for(i=0; i<v2; i++){
        for(j=0; j<s2; j++){
            scanf("%d",&matricaB[i][j]);

        }
    }
    sadrzana=matrica_sadrzana(matricaA,v1,s1,matricaB,v2,s2);

    return 0;
}

Ответы [ 2 ]

0 голосов
/ 13 декабря 2018

Вы можете сделать это, используя массивы фиксированной длины или массивы переменной длины.

Массивы фиксированной длины

Вы начали с массивов фиксированной длины, поэтому первая программа следует вашему примеру.Вы должны указать второе измерение массивов при их передаче - в противном случае код будет обращаться к неверным данным.Ваш компилятор должен был жаловаться на вызов вашей функции.Я использовал инициализированные данные вместо чтения из стандартного ввода.Входной код закомментирован (и не проверен). 

#include <stdio.h>

static int matrica_subset(int m1[][100], int r1, int c1, int m2[][100], int r2, int c2)
{
    for (int m = 0; m < r2; m++)
    {
        for (int n = 0; n < c2; n++)
        {
            printf("ss: m1[%d][%d] = %d; m2[%d][%d] = %d\n", r1+m, c1+n, m1[r1+m][c1+n], m, n, m2[m][n]);
            if (m1[r1+m][c1+n] != m2[m][n])
                return 0;
        }
    }
    return 1;
}

static int matrica_sadrzana(int m1[][100], int r1, int c1, int m2[][100], int r2, int c2)
{
    if (c1 < c2 || r1 < r2)
        return 0;
    int c_max = c1 - c2 + 1;
    int r_max = r1 - r2 + 1;
    for (int r = 0; r < r_max; r++)
    {
        for (int c = 0; c < c_max; c++)
        {
            printf("sa: m1[%d][%d] = %d; m2[0][0] = %d\n", r, c, m1[r][c], m2[0][0]);
            if (m1[r][c] == m2[0][0])
            {
                if (matrica_subset(m1, r, c, m2, r2, c2) != 0)
                {
                    printf("match at m1[%d][%d]\n", r, c);
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main(void)
{
    int sadrzana, c1 = 5, c2 = 2, r1 = 4, r2 = 3;
    int matricaA[100][100] =
    {
        {   1,   2,   3,   4,   5, },
        {   6,   7,   8,   9,  10, },
        {  11,  12,  13,  14,  15, },
        {  16,  17,  18,  19,  20, },
    };
    int matricaB[100][100] =
    {
        {   2,   3, },
        {   7,   8, },
        {  12,  13, },
    };

    //printf("rows and columns for matrix A: ");
    //scanf("%d %d", &r1, &c1);
    //printf("rows and columns for matrix B: ");
    //scanf("%d %d", &r2, &c2);
    //printf("data for matrix A:\n");
    //for (int i = 0; i < r1; i++)
    //{
    //    for (int j = 0; j < c1; j++)
    //    {
    //        scanf("%d", &matricaA[i][j]);
    //    }
    //}
    //printf("data for matrix B:\n");
    //for (int i = 0; i < r2; i++)
    //{
    //    for (int j = 0; j < c2; j++)
    //    {
    //        scanf("%d", &matricaB[i][j]);
    //    }
    //}

    sadrzana = matrica_sadrzana(matricaA, r1, c1, matricaB, r2, c2);
    printf("sadrzana: %d\n", sadrzana);

    return 0;
}

Функция matrica_subset() ищет в m1, начиная со строки r1, столбец c1 для совпадения с m2 с размеромr2 активных строк и c2 активных столбцов (небольшое подмножество матрицы 100x100, определенной в main()).

matrica_sadrzana() координирует поиск, проверяя, находится ли верхний левый угол m2 соответствует текущей позиции в m1 и продолжает поиск с помощью функции matrica_subset() при наличии совпадения.

Пример вывода: 

sa: m1[0][0] = 1; m2[0][0] = 2
sa: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][2] = 3; m2[0][1] = 3
ss: m1[1][1] = 7; m2[1][0] = 7
ss: m1[1][2] = 8; m2[1][1] = 8
ss: m1[2][1] = 12; m2[2][0] = 12
ss: m1[2][2] = 19; m2[2][1] = 13
sa: m1[0][2] = 3; m2[0][0] = 2
sa: m1[0][3] = 4; m2[0][0] = 2
sa: m1[1][0] = 6; m2[0][0] = 2
sa: m1[1][1] = 7; m2[0][0] = 2
sa: m1[1][2] = 8; m2[0][0] = 2
sa: m1[1][3] = 9; m2[0][0] = 2
sadrzana: 0

Массивы переменной длины

Альтернативно использование массивов переменной длины требует дополнительных параметров для функции matrica_subset(), чтобы указать фактический размер массива (r1 и c1), а также позицию поиска в массиве (r0 и c0). 

#include <stdio.h>

static void dump_matrix(const char *tag, int r, int c, int m[r][c])
{
    printf("%s (%dx%d):\n", tag, r, c);
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
            printf(" %3d", m[i][j]);
        putchar('\n');
    }
}

static int matrica_subset(int r1, int c1, int m1[r1][c1], int r0, int c0, int r2, int c2, int m2[r2][c2])
{
    for (int m = 0; m < r2; m++)
    {
        for (int n = 0; n < c2; n++)
        {
            printf("ss: m1[%d][%d] = %d; m2[%d][%d] = %d\n", r0+m, c0+n, m1[r0+m][c0+n], m, n, m2[m][n]);
            if (m1[r0+m][c0+n] != m2[m][n])
                return 0;
        }
    }
    return 1;
}

static int matrica_sadrzana(int r1, int c1, int m1[r1][c1], int r2, int c2, int m2[r2][c2])
{
    if (c1 < c2 || r1 < r2)
        return 0;
    int c_max = c1 - c2 + 1;
    int r_max = r1 - r2 + 1;
    for (int r = 0; r < r_max; r++)
    {
        for (int c = 0; c < c_max; c++)
        {
            printf("sa: m1[%d][%d] = %d; m2[0][0] = %d\n", r, c, m1[r][c], m2[0][0]);
            if (m1[r][c] == m2[0][0])
            {
                if (matrica_subset(r1, c1, m1, r, c, r2, c2, m2) != 0)
                {
                    printf("match at m1[%d][%d]\n", r, c);
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main(void)
{
    int sadrzana, c1 = 5, c2 = 2, r1 = 4, r2 = 3;
    int matricaA[4][5] =
    {
        {   1,   2,   3,   4,   5, },
        {   6,   7,   8,   9,  10, },
        {  11,  12,  13,  14,  15, },
        {  16,  17,  18,  19,  20, },
    };
    int matricaB[3][2] =
    {
        {   2,   3, },
        {   7,   8, },
        {  12,  13, },
    };

    //printf("rows and columns for matrix A: ");
    //scanf("%d %d", &r1, &c1);
    //printf("rows and columns for matrix B: ");
    //scanf("%d %d", &r2, &c2);
    //printf("data for matrix A:\n");
    //for (int i = 0; i < r1; i++)
    //{
    //    for (int j = 0; j < c1; j++)
    //    {
    //        scanf("%d", &matricaA[i][j]);
    //    }
    //}
    //printf("data for matrix B:\n");
    //for (int i = 0; i < r2; i++)
    //{
    //    for (int j = 0; j < c2; j++)
    //    {
    //        scanf("%d", &matricaB[i][j]);
    //    }
    //}
    dump_matrix("Matrix A", r1, c1, matricaA);
    dump_matrix("Matrix B", r2, c2, matricaB);

    sadrzana = matrica_sadrzana(r1, c1, matricaA, r2, c2, matricaB);
    printf("sadrzana: %d\n", sadrzana);

    return 0;
}

Пример вывода: 

Matrix A (4x5):
   1   2   3   4   5
   6   7   8   9  10
  11  12  13  14  15
  16  17  18  19  20
Matrix B (3x2):
   2   3
   7   8
  12  13
sa: m1[0][0] = 1; m2[0][0] = 2
sa: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][2] = 3; m2[0][1] = 3
ss: m1[1][1] = 7; m2[1][0] = 7
ss: m1[1][2] = 8; m2[1][1] = 8
ss: m1[2][1] = 12; m2[2][0] = 12
ss: m1[2][2] = 13; m2[2][1] = 13
match at m1[0][1]
sadrzana: 1

Сюрприз, сюрприз - он возвращает тот же результат.Функции поиска работают с массивами переменной длины;данные по-прежнему хранятся в массивах фиксированного размера (поскольку вы не можете использовать инициализатор для VLA), но размеры значительно меньше, чем в исходном коде.

Код VLA также сбрасывает входные матрицы;код FLA нет.Довольно просто добавить код дампа в первую программу, но функция печати не такая общая.Можно было бы организовать вывод подсегмента NxM матрицы RxC;это немного неудобно для кода, но очень универсально и может использоваться в обеих программах - но программа VLA просто установит N и R равными, а M и C равными.

0 голосов
/ 13 декабря 2018

Вы можете создать функцию findNum (), которая возвращает логическое значение true или false и принимает размер строки, размер столбца, массив 2d (со вторым измерением, указанным в передаваемом размере столбца) и числоВы хотели бы проверить.Таким образом, в вашем случае вы могли бы пройти через Матрицу A, вызывая findNum () для каждого элемента в Матрице A, чтобы проверить и проверить, содержится ли в нем матрица B.findNum () вернет true при первом обнаружении числа, которое он проверяет.Если число там отсутствует, оно вернет false.

Например: 

_Bool findNum(int row, int col, int arr2d[][col], int chk) {
    for(int i = 0; i < row; ++i) {
        for(int j = 0; j < col; ++j) {
            if(arr2d[i][j] == chk)
                return 1;
        }
    }

    return 0;
}

Используя его (это должно вывести «Match!» Три раза, так как 0 содержится в arr2d2, но5 нет): 

int arr2d1[2][2] = {0};
int arr2d2[2][3] = {0};

/* Change a value in arr2d1 so they're not identical */
arr2d1[0][0] = 5;

/* Element we're sending to findNum() */
int element = 0;

/* Traverse through arr2d1 */
for(int i = 0; i < 2; ++i) {
    for(int j = 0; j < 2; ++j) {
        element = arr2d1[i][j];
        /* Check if the current element is contained
         * in arr2d2; do whatever if so */
        if(findNum(2, 3, arr2d2, element)) {
            printf("Match!\n");
        }
    }
}
...