हमें मैट्रिक्स बनाने वाले पूर्णांक तत्वों की 2-डी सरणी दी गई है। कार्य इस प्रकार गठित मैट्रिक्स से सबमैट्रिक्स को खींचकर न्यूनतम योग की गणना करना है।
आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -
इन − इंट मैट्रिक्स [आकार] [आकार] ={{2, 3, -1, 5}, {-2, 9, -1, 6}, {5, 6, 9, -9}, { -6, 1, 1, 1} }
बाहर − किसी दिए गए 2D सरणी में न्यूनतम योग सबमैट्रिक्स है:-9
स्पष्टीकरण - हमें आकार 4x4 यानी 4 पंक्तियों और 4 स्तंभों की 2-डी सरणी दी गई है। अब, हम दिए गए मैट्रिक्स से सब-मैट्रिक्स का पता लगाएंगे कि न्यूनतम सब -9 है।
इन − इंट मैट्रिक्स [पंक्ति] [कॉलम] ={ {4, 1, 3}, {-1, -1, -1}, { 6, 2, 3}}
बाहर − किसी दिए गए 2D सरणी में न्यूनतम योग सबमैट्रिक्स है:-3
स्पष्टीकरण - हमें 3x3 आकार का 2-डी सरणी दिया गया है यानी 3 पंक्तियाँ और 3 कॉलम। अब, हम दिए गए मैट्रिक्स से सब-मैट्रिक्स का पता लगाएंगे जैसे कि न्यूनतम सब -3 है जो किसी दिए गए मैट्रिक्स में दूसरी पंक्ति के साथ प्राप्त किया जाता है और सब-मैट्रिक्स आकार 1x3 यानी 1 पंक्ति और 3 कॉलम का होगा।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है -
-
एक पूर्णांक 2-डी सरणी इनपुट करें और आगे की प्रक्रिया के लिए डेटा को न्यूनतम_मैट्रिक्स (मैट्रिक्स) फ़ंक्शन में पास करें।
-
समारोह के अंदर न्यूनतम_मैट्रिक्स(मैट्रिक्स)
-
अस्थायी चरों को int परिणाम =INT_MAX, int arr[row], int Total, int first और int end के रूप में घोषित करें।
-
कॉलम से कम अस्थायी तक int से अस्थायी के लिए लूप प्रारंभ करें। लूप के अंदर सरणी तत्वों को 0 के रूप में सेट करें। कॉलम से कम temp_2 तक int से 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)
-
अस्थायी चरों को इंट टोटल 0, इंट रिजल्ट को INT_MAX, इंट टेम्प से 0 और *end =-1
के रूप में घोषित करें -
i से 0 तक के लिए लूप प्रारंभ करें जब तक कि i max_size से कम न हो जाए। लूप के अंदर, टोटल को टोटल + arr[i] के रूप में सेट करें।
-
जाँच करें कि IF कुल 0 से अधिक है तो कुल को 0 और अस्थायी को i + 1 के रूप में सेट करें।
-
ELSE IF, परिणाम से कम का कुल चेक करें, फिर परिणाम को कुल पर सेट करें, *पहले से अस्थायी और *अंत से i
-
अब, जांचें कि IF *end बराबर नहीं -1 है तो परिणाम लौटाएं।
-
परिणाम को गिरफ्तारी [0], *पहले से 0 और *अंत से 0
. पर सेट करें -
i से 1 तक के लिए लूप प्रारंभ करें जब तक कि i max_size से कम न हो जाए। लूप के अंदर, IF 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