我们得到了一个由整数元素组成的二维数组,构成了矩阵。任务是通过从如此形成的矩阵中提取子矩阵来计算最小和的计数。
让我们看看这个的各种输入输出场景 -
In − int matrix[size][size] = { {2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} }
Out -给定二维数组中的最小和子矩阵为:-9
说明 -我们给出了一个大小为 4x4 的二维数组,即 4 行和 4 列。现在,我们将从给定的矩阵中找出子矩阵,使得最小子矩阵为 -9。
In − int matrix[row][column] = { {4, 1, 3}, {-1, -1, -1}, { 6, 2, 3}}
Out -给定二维数组中的最小和子矩阵为:-3
说明 -我们给出了一个大小为 3x3 的二维数组,即 3 行和 3 列。现在,我们将从给定矩阵中找出子矩阵,使得最小子矩阵为 -3,这是通过给定矩阵中的第二行实现的,子矩阵的大小为 1x3,即 1 行 3 列。
输入一个整数二维数组并将数据传递给函数Minimum_Matrix(matrix)以进行进一步处理。
函数内部 Minimum_Matrix(matrix)
将临时变量声明为 int result = INT_MAX、int arr[row]、int total、int first 和 int end。
从 int 到 temp 开始循环 FOR,直到 temp 小于列。在循环内将数组元素设置为 0。从 int 到 temp_2 开始另一个循环 FOR,直到 temp_2 小于 column。在循环内部,从 int i 到 0 开始另一个循环,直到 i 小于 row 并将 arr[i] 设置为 ar[i] + matrix[i][temo_2]。
将总计设置为对函数 Algo_Kad(arr, &first, &end, row) 的调用
检查 IF 总数小于结果,然后将结果设置为总数
打印结果作为最终输出。
在函数内部 int Algo_Kad(int* arr, int* first, int* end, int max_size)
将临时变量声明为 int total 为 0,int result 为 INT_MAX,int temp 为 0 和 *end = -1
从 i 到 0 开始循环 FOR,直到 i 小于 max_size。在循环内,将 total 设置为 total + arr[i]。
检查 IF total 大于 0,然后将 total 设置为 0,将 temp 设置为 i + 1。
否则,如果检查总数小于结果,然后将结果设置为总数,*先到临时,*结束到 i
现在,检查 IF *end 不等于 -1 然后返回结果。
将结果设置为 arr[0],*first 为 0,*end 为 0
从 i 到 1 开始循环 FOR,直到 i 小于 max_size。在循环内,检查 IF arr[i] 小于结果,然后将结果设置为 arr[i],*first 为 i 和 *end 为 i
返回结果。
#include <bits/stdc++.h> using namespace std; #define row 4 #define column 4 int Algo_Kad(int* arr, int* first, int* end, int max_size) { int total = 0; int result = INT_MAX; int temp = 0; *end = -1; for(int i = 0; i < max_size; ++i) { total = total + arr[i]; if(total > 0) { total = 0; temp = i + 1; } else if(total < result) { result = total; *first = temp; *end = i; } } if(*end != -1) { return result; } result = arr[0]; *first = 0; *end = 0; for(int i = 1; i < max_size; i++) { if(arr[i] < result) { result = arr[i]; *first = i; *end = i; } } return result; } void Minimum_Matrix(int matrix[][column]) { int result = INT_MAX; int arr[row]; int total; int first; int end; for(int temp = 0; temp < column; ++temp) { memset(arr, 0, sizeof(arr)); for(int temp_2 = temp; temp_2 < column; ++temp_2) { for(int i = 0; i < row; ++i) { arr[i] = arr[i] + matrix[i][temp_2]; } total = Algo_Kad(arr, &first, &end, row); if(total < result) { result = total; } } } cout<<"给定二维数组中的最小和子矩阵为: "<<result; } int main() { int matrix[row][column] = {{2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} }; Minimum_Matrix(matrix); return 0; }输出结果
如果我们运行上面的代码,它将生成以下输出
给定二维数组中的最小和子矩阵为: -9