В матрице найти подматрицу, у которой самая высокая сумма все чисел - C (СИ)
Формулировка задачи:
Доброго времени суток, тут такое вот дело, надо написать функция котороая ищет из квадратной матрицы(двойной массив) маленькую квадратную матрицу у которой саммая высокая сумма все чисел.функция выведит на экран данные начала под матрицы и ее сумму.
функция получает массив и его размер.
заранее спасибо)
Решение задачи: «В матрице найти подматрицу, у которой самая высокая сумма все чисел»
textual
Листинг программы
#include <stdio.h> #include <malloc.h> typedef struct { int left, top, right, bottom; } rect; int** matrix_create(int n); void matrix_free(int** mat, int n); int** matrix_input(FILE* _in, int* n); int matrix_subsum(int** mat, int n, rect* pr); int main(void){ int i, j, sum, **mat, n; rect rc; /* ввод из файла FILE* fp = fopen("file.txt", "rt"); mat = matrix_input(fp, &n); fclose(fp); */ mat = matrix_input(stdin, &n); if(mat == NULL) return 1; putchar('\n'); sum = matrix_subsum(mat, n, &rc); for(i = rc.left; i < rc.right; ++i){ for(j = rc.top; j < rc.bottom; ++j) printf("% 3d ", mat[i][j]); putchar('\n'); } printf("sum sub matrix: %d\n", sum); matrix_free(mat, n); getchar(); return 0; } //поиск квадратной под-матрицы с макс. суммой int matrix_subsum(int** mat, int n, rect* pr){ rect r; int i, j, s, m = 0, d = 2; r.left = r.top = r.right = r.bottom = 0; *pr = r; r.right = r.bottom = d; while(d < n){ s = 0; for(i = r.left; i < r.right; ++i){ for(j = r.top; j < r.bottom; ++j) s += mat[i][j]; } if(s > m){ m = s; *pr = r; } ++r.left; if(++r.right > n){ r.left = 0; r.right = d; ++r.top; if(++r.bottom > n){ r.left = r.top = 0; r.right = r.bottom = ++d; } } } return m; } /* ввод матрицы из файла/консоли, пример: 3 1 2 3 2 3 4 3 3 2 */ int** matrix_input(FILE* _in, int* n){ int** mat, i, j; *n = 0; if((_in == NULL) || (fscanf(_in, "%d", n) != 1) || (*n <= 1)) return NULL; if((mat = matrix_create(*n)) == NULL) return NULL; for(i = 0; i < *n; ++i){ for(j = 0; j < *n; ++j){ if((fscanf(_in, "%d", &mat[i][j]) != 1) || (ferror(_in) != 0)){ matrix_free(mat, *n); return NULL; } } } return mat; } //выделение памяти int** matrix_create(int n){ int i; int** mat = (int**)malloc(n * sizeof(int*)); if(mat == NULL) return NULL; for(i = 0; i < n; ++i){ mat[i] = (int*)malloc(n * sizeof(int)); if(mat[i] == NULL){ matrix_free(mat, i); mat = NULL; break; } } return mat; } //освобождение памяти void matrix_free(int** mat, int n){ int i; for(i = 0; i < n; ++i) free(mat[i]); free(mat); }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д