В матрице найти подматрицу, у которой самая высокая сумма все чисел - 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);
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

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

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