เมทริกซ์ผลรวมขั้นต่ำในอาร์เรย์ 2D ที่กำหนดใน C++

เราได้รับอาร์เรย์ 2 มิติขององค์ประกอบจำนวนเต็มที่สร้างเมทริกซ์ ภารกิจคือการคำนวณจำนวนผลรวมขั้นต่ำโดยการดึงเมทริกซ์ย่อยจากเมทริกซ์ที่เกิดขึ้น

ให้เราดูสถานการณ์อินพุตเอาต์พุตต่างๆ สำหรับสิ่งนี้ -

ใน - int matrix[ขนาด][ขนาด] ={{2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} } }

ออก − เมทริกซ์ผลรวมขั้นต่ำในอาร์เรย์ 2 มิติที่กำหนดคือ:-9

คำอธิบาย − เราได้รับอาร์เรย์ 2 มิติขนาด 4x4 เช่น 4 แถวและ 4 คอลัมน์ ตอนนี้ เราจะหาเมทริกซ์ย่อยจากเมทริกซ์ที่กำหนด โดยที่ค่าย่อยขั้นต่ำคือ -9

ใน - int matrix[row][column] ={{4, 1, 3}, {-1, -1, -1}, { 6, 2, 3}}

ออก − เมทริกซ์ผลรวมขั้นต่ำในอาร์เรย์ 2 มิติที่กำหนดคือ:-3

คำอธิบาย − เราได้รับอาร์เรย์ 2 มิติขนาด 3x3 เช่น 3 แถวและ 3 คอลัมน์ ตอนนี้ เราจะหาเมทริกซ์ย่อยจากเมทริกซ์ที่กำหนด โดยที่การย่อยขั้นต่ำคือ -3 ซึ่งทำได้ด้วยแถวที่สองในเมทริกซ์ที่กำหนด และเมทริกซ์ย่อยจะมีขนาด 1x3 เช่น 1 แถวและ 3 คอลัมน์

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

• ป้อนอาร์เรย์ 2 มิติจำนวนเต็มแล้วส่งข้อมูลไปยังฟังก์ชัน Minimum_Matrix(matrix) เพื่อการประมวลผลต่อไป

• ภายในฟังก์ชัน Minimum_Matrix(matrix)

  • ประกาศตัวแปรชั่วคราวเป็นผลลัพธ์ int =INT_MAX, int arr[row], int total, int first และ int end

  • เริ่มวนรอบ FOR จาก int ถึง temp จนถึง temp น้อยกว่าคอลัมน์ ภายในลูปกำหนดองค์ประกอบอาร์เรย์เป็น 0 เริ่มลูปอื่น FOR จาก int ถึง temp_2 ถึง temp_2 น้อยกว่าคอลัมน์ ภายในลูป เริ่มการวนซ้ำอีกครั้งจาก int i ถึง 0 จนถึง i น้อยกว่าแถวและตั้งค่า 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 เป็น 0, int ให้ผลลัพธ์เป็น INT_MAX, int temp เป็น 0 และ *end =-1

  • เริ่มวนซ้ำ FOR จาก i ถึง 0 จนถึง i น้อยกว่า max_size ภายในลูป ตั้งค่า Total เป็น Total + arr[i].

  • ตรวจสอบว่าผลรวมมากกว่า 0 แล้วตั้งค่าผลรวมเป็น 0 และอุณหภูมิเป็น i + 1

  • มิฉะนั้น ให้ตรวจสอบผลรวมที่น้อยกว่าผลลัพธ์ จากนั้นตั้งค่าผลลัพธ์เป็นผลรวม *ก่อนไปที่ชั่วคราว และ *สิ้นสุดที่ i

  • ตอนนี้ตรวจสอบ IF *end ไม่เท่ากับ -1 แล้วส่งคืนผลลัพธ์

  • ตั้งค่าผลลัพธ์เป็น arr[0], *first to 0 and *end to 0

  • เริ่มวนซ้ำ FOR จาก i ถึง 1 จนถึง i น้อยกว่า max_size ภายในลูป ให้ตรวจสอบว่า arr[i] น้อยกว่าผลลัพธ์ จากนั้นตั้งค่าผลลัพธ์เป็น arr[i], *first as i และ *end as 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<<"Minimum sum submatrix in a given 2D array is: "<<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;
}

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

Minimum sum submatrix in a given 2D array is: -9