Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाइनरी मैट्रिक्स में अधिकतम दशमलव मान पथ


दिया गया कार्य एक दिए गए वर्ग बाइनरी सरणी में ऊपरी बाएं तत्व से निचले दाएं तत्व तक एक पथ में यात्रा करते समय प्राप्त किए जा सकने वाले अधिकतम पूर्णांक मान को ढूंढना है, यानी इंडेक्स [0][0] से इंडेक्स [n - 1][n - 1] से शुरू करना।

पथ को कवर करते समय हम केवल दाईं ओर ([i][j + 1]) या नीचे ([i + 1][j]) जा सकते हैं।

पूर्णांक मान पार किए गए पथ के बिट्स का उपयोग करके गणना की जाएगी।

उदाहरण

इनपुट

m = {
    {1, 1, 1, 1},
    {0, 0, 1, 0},
    {1, 0, 1, 1},
    {0, 1, 1, 1}
}

आउटपुट

127

व्याख्या

हमने जो पथ लिया वह है: [0, 0] → [0, 1] → [0, 2] → [1, 2] → [2, 2] → [3, 2] → [3, 3]

इसलिए दशमलव मान बन जाता है = 1*(2^0) + 1*(2^1) + 1*(2^2) + 1*(2^3) + 1*(2^4) + 1*(2^5) + 1*(2^6)

= 1 + 2 + 4 + 8 + 16 + 32 + 64

= 127

इनपुट

m = {
    {1, 0, 1, 1},
    {0, 0, 1, 0},
    {1, 0, 0, 1},
    {0, 1, 1, 1}
}

आउटपुट

109

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है

  • सबसे पहले #define का उपयोग करके वर्ग मैट्रिक्स के किनारे का आकार शीर्ष पर परिभाषित करें।
  • main() फ़ंक्शन में मैट्रिक्स संग्रहीत करने के लिए एक 2D सरणी int m[][4] बनाएं और Max(m, 0, 0, 0) कॉल करें।
  • max() फ़ंक्शन में पहले जांचें कि क्या (i >= side || j >= side )। यदि हां, तो इसका मतलब है कि हम मैट्रिक्स सीमा से बाहर हैं और 0 वापस करें।
  • एक नया चर int ans बनाएं और ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1)) रखें।
  • फिर जांचें कि क्या (m[i][j] == 1)। यदि हां, तो pow(2, pw) + ans वापस करें।
  • अन्यथा बस ans वापस करें।

कार्यक्रम उदाहरण

#include<bits/stdc++.h>
using namespace std;

#define side 4 // pw 2 की घात है

int Max(int m[][side], int i, int j, int pw){
    // सीमा से बाहर
    if (i >= side || j >= side )
        return 0;
    int ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1));
    if (m[i][j] == 1)
        return pow(2, pw) + ans;
    else
        return ans;
}

// main फ़ंक्शन
int main(){
    int m[][4] = {{1, 1, 1, 1},{0, 0, 1, 0},{1, 0, 1, 1},{0, 1, 1, 1}};
    cout << Max(m, 0, 0, 0);
    return 0;
}

आउटपुट

127
  1. C++ में बाइनरी ट्री की अधिकतम चौड़ाई C++ में बाइनरी ट्री की अधिकतम चौड़ाई

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें ट्री की अधिकतम चौड़ाई ढूंढनी है। एक लेवल की चौड़ाई उस लेवल के सबसे बाएँ और सबसे दाएँ नॉन-नल नोड्स के बीच की दूरी है (बीच के नल नोड्स भी गिने जाते हैं)। उदाहरण: ट्री [1,3,2,5,3,null,9] के लिए अधिकतम चौड़ाई 4 है (अंतिम लेवल [5,3,null,9] की लंबाई 4)। BFS +

  1. C++ में अधिकतम बाइनरी ट्री निर्माण C++ में अधिकतम बाइनरी ट्री निर्माण

    मान लीजिए हमारे पास एक पूर्णांक सरणी है जिसके सभी तत्व अद्वितीय हैं। एक अधिकतम बाइनरी ट्री निम्न नियमों से बनता है: रूट सरणी का अधिकतम तत्व होता है। बायाँ सबट्री अधिकतम तत्व के बाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है। दायाँ सबट्री अधिकतम तत्व के दाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है।

  1. C++ में बाइनरी ट्री में अधिकतम पथ योग C++ में बाइनरी ट्री में अधिकतम पथ योग

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें प्रत्येक नोड एक मान रखता है। हमारा कार्य बाइनरी ट्री के दो पत्तों के बीच अधिकतम पथ योग ढूंढने के लिए एक प्रोग्राम बनाना है। यहां, हमें एक पत्ते नोड से दूसरे पत्ते नोड तक का पथ ढूंढना है जो मानों का अधिकतम योग प्रदान करेगा। यह अधिकतम योग पथ रूट न