C++中给定二维数组中的最小和子矩阵

我们得到了一个由整数元素组成的二维数组,构成了矩阵。任务是通过从如此形成的矩阵中提取子矩阵来计算最小和的计数。

让我们看看这个的各种输入输出场景 -

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

猜你喜欢