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