Chúng ta được cung cấp một mảng 2-D gồm các phần tử nguyên tạo thành ma trận. Nhiệm vụ là tính tổng số tổng nhỏ nhất bằng cách kéo ma trận con từ ma trận được tạo thành như vậy.
Hãy cho chúng tôi xem các tình huống đầu ra đầu vào khác nhau cho việc này -
Trong - int ma trận [size] [size] ={{2, 3, -1, 5}, {-2, 9, -1, 6}, {5, 6, 9, -9}, {-6, 1, 1, 1}}
Hết - Tổng phụ tối thiểu trong một mảng 2D nhất định là:-9
Giải thích - chúng ta được cung cấp một mảng 2-D có kích thước 4x4, tức là 4 hàng và 4 cột. Bây giờ, chúng ta sẽ tìm ra ma trận con từ ma trận đã cho sao cho ma trận con nhỏ nhất là -9.
Trong - int matrix [row] [column] ={{4, 1, 3}, {-1, -1, -1}, {6, 2, 3}}
Hết - Tổng phụ tối thiểu trong một mảng 2D nhất định là:-3
Giải thích - chúng ta được cung cấp một mảng 2-D có kích thước 3x3, tức là 3 hàng và 3 cột. Bây giờ, chúng ta sẽ tìm ra ma trận con từ ma trận đã cho sao cho con nhỏ nhất là -3 đạt được với hàng thứ hai trong ma trận đã cho và ma trận con sẽ có kích thước 1x3, tức là 1 hàng và 3 cột.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
-
Nhập một mảng 2-D số nguyên và chuyển dữ liệu vào hàm Minimum_Matrix (ma trận) để xử lý thêm.
-
Bên trong hàm Minimum_Matrix (ma trận)
-
Khai báo các biến tạm thời là int result =INT_MAX, int arr [row], int total, int first và int end.
-
Bắt đầu vòng lặp FOR từ int đến nhiệt độ cho đến nhiệt độ nhỏ hơn cột. Bên trong vòng lặp đặt các phần tử mảng là 0. Bắt đầu một vòng lặp FOR khác từ int đến temp_2 cho đến khi temp_2 nhỏ hơn cột. Bên trong vòng lặp, bắt đầu một vòng lặp khác từ int i đến 0 cho đến khi tôi nhỏ hơn hàng và đặt arr [i] là ar [i] + matrix [i] [temo_2].
-
Đặt tổng số dưới dạng lệnh gọi đến hàm Algo_Kad (arr, &first, &end, row)
-
Kiểm tra IF tổng nhỏ hơn kết quả rồi đặt kết quả là tổng
-
In kết quả dưới dạng đầu ra cuối cùng.
-
-
Bên trong hàm int Algo_Kad (int * arr, int * first, int * end, int max_size)
-
Khai báo các biến tạm thời là int total thành 0, int result thành INT_MAX, int temp thành 0 và * end =-1
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn max_size. Bên trong vòng lặp, đặt tổng là tổng + arr [i].
-
Kiểm tra IF tổng lớn hơn 0 rồi đặt tổng là 0 và tạm thời là i + 1.
-
ELSE IF, kiểm tra tổng nhỏ hơn kết quả rồi đặt kết quả thành tổng, * đầu tiên đến tạm thời và * kết thúc thành i
-
Bây giờ, hãy kiểm tra IF * end không bằng -1 rồi trả về kết quả.
-
Đặt kết quả thành arr [0], * đầu tiên thành 0 và * kết thúc thành 0
-
Bắt đầu vòng lặp FOR từ tôi đến 1 cho đến khi tôi nhỏ hơn max_size. Bên trong vòng lặp, kiểm tra IF arr [i] nhỏ hơn kết quả, sau đó đặt kết quả là arr [i], * đầu tiên là i và * kết thúc là i
-
Trả về kết quả.
-
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Minimum sum submatrix in a given 2D array is: -9