हमें पूर्णांक तत्वों की एक 2-D सरणी दी गई है जो मैट्रिक्स बनाती है। कार्य मैट्रिक्स से उपमैट्रिक्स निकालकर न्यूनतम योग की गणना करना है।
विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:
इनपुट: int matrix[size][size] = { {2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} }
आउटपुट: दी गई 2D सरणी में न्यूनतम योग उपमैट्रिक्स: -9
व्याख्या: हमें 4x4 आकार की एक 2-D सरणी दी गई है यानी 4 पंक्तियां और 4 स्तंभ। अब, हम दिए गए मैट्रिक्स से उप-मैट्रिक्स ढूंढेंगे जैसे कि न्यूनतम योग -9 है।
इनपुट: int matrix[row][column] = { {4, 1, 3}, {-1, -1, -1}, { 6, 2, 3} }
आउटपुट: दी गई 2D सरणी में न्यूनतम योग उपमैट्रिक्स: -3
व्याख्या: हमें 3x3 आकार की एक 2-D सरणी दी गई है यानी 3 पंक्तियां और 3 स्तंभ। अब, हम दिए गए मैट्रिक्स से उप-मैट्रिक्स ढूंढेंगे जैसे कि न्यूनतम योग -3 है जो दी गई मैट्रिक्स में दूसरी पंक्ति के साथ प्राप्त होता है और उप-मैट्रिक्स 1x3 आकार का होगा यानी 1 पंक्ति और 3 स्तंभ।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण:
- एक पूर्णांक 2-D सरणी इनपुट करें और डेटा को आगे की प्रोसेसिंग के लिए फंक्शन Minimum_Matrix(matrix) में पास करें।
- फंक्शन Minimum_Matrix(matrix) के अंदर:
- result = INT_MAX, int arr[row], int total, int first और int end के रूप में अस्थायी वेरिएबल्स घोषित करें।
- int को temp से temp < column तक लूप चलाएं। अंदर सरणी तत्वों को 0 पर सेट करें। temp_2 को temp से temp_2 < column तक एक और लूप शुरू करें। अंदर, i को 0 से row से कम तक एक और लूप शुरू करें और arr[i] को ar[i] + matrix[i][temp_2] पर सेट करें।
- total को फंक्शन Algo_Kad(arr, &first, &end, row) कॉल पर सेट करें।
- जांचें यदि total, result से कम है तो result को total पर सेट करें।
- परिणाम को अंतिम आउटपुट के रूप में प्रिंट करें।
- फंक्शन int Algo_Kad(int* arr, int* first, int* end, int max_size) के अंदर:
- total को 0, result को INT_MAX, temp को 0 और *end = -1 के रूप में अस्थायी वेरिएबल्स घोषित करें।
- i को 0 से max_size से कम तक लूप चलाएं। अंदर, total को total + arr[i] पर सेट करें।
- जांचें यदि total > 0 तो total को 0 पर सेट करें और temp को i + 1 पर सेट करें।
- अन्यथा यदि, total < result जांचें तो result को total पर, *first को temp पर और *end को i पर सेट करें।
- अब, जांचें यदि *end -1 के बराबर नहीं है तो result लौटाएं।
- result को arr[0] पर, *first को 0 पर और *end को 0 पर सेट करें।
- i को 1 से max_size से कम तक लूप चलाएं। अंदर, जांचें यदि arr[i] < result तो result को arr[i] पर, *first को i पर और *end को i पर सेट करें।
- result लौटाएं।
उदाहरण
#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
