Поиск подматрицы в матрице - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Способы заполнения массива: 1) заполнение случайными числами в заданном диапазоне; 2) Копирование элементов из другого массива; В матрице размером NхМ определить такую подматрицу размером 3х3,сумма элементов главной диагонали которой максимальна. Заранее спасибо.

Решение задачи: «Поиск подматрицы в матрице»

textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 9
#define M 7
#define K 3
int main()
{
    int A[N][M], i, j, q, l, count = 0, x = 0, y = 0, sum = 0, max;
    srand(time(NULL));
    for(i = 0; i < N; i++, putchar('\n'))
        for(j = 0; j < M; j++)
            printf("%3d", A[i][j] = rand() % 30);
    max = A[0][0] + A[1][1] + A[2][2];
    for(i = 0; i < N - K; i++)
        for(j = 0; j < M - K; j++){
            for(q = i, l = j, count = 0, sum = 0; count < K; count++){
                sum += A[q++][l++];
            }
            printf("sum = %d A[%d][%d] - A[%d][%d]\n", sum, i, j, i + 2, j + 2);
            if(sum > max){
                max = sum;
                x = i;
                y = j;
            }
        }
    printf("\nMax diagonal sum is %d matrix A[%d][%d] - A[%d][%d]", max, x, y, x + 2, y + 2);
    return 0;
}

Объяснение кода листинга программы

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

  1. Объявляются переменные:
    • A[N][M] - матрица размером NxM, заполненная случайными числами от 0 до 29;
    • i, j, q, l, count, x, y, sum, max - вспомогательные переменные для поиска подматрицы.
  2. Выводится содержимое матрицы A.
  3. Вычисляется максимальная сумма подматрицы размером 3x3, расположенной в левом верхнем углу большой матрицы (для диагонали dmax).
  4. Перебираются все подматрицы размером 3x3 в большой матрице (начиная с левого верхнего угла и двигаясь по диагонали, затем по вертикали и горизонтали). Для каждой подматрицы вычисляется ее сумма.
  5. Если сумма подматрицы больше текущей максимальной суммы, то обновляется значение максимальной суммы и запоминаются координаты ячеек подматрицы.
  6. Выводится информация о найденной подматрице с максимальной суммой.
  7. Функция возвращает 0, завершая работу программы.

Оцени полезность:

7   голосов , оценка 3.857 из 5
Похожие ответы