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

ऐरे बनाएं जहाँ अधिकतम तत्व ठीक K तुलनाओं में मिले - C++


मान लीजिए हमारे पास तीन पूर्णांक n, m, और k हैं। यदि हमारे पास एक धनात्मक पूर्णांकों के ऐरे के अधिकतम तत्व को खोजने के लिए निम्नलिखित एल्गोरिदम है −

max_val := -1 max_ind := -1 search_cost := 0 n := size of arr for initialize i := 0, when i < n, update (increase i by 1), do:    if max_val < arr[i], then:       max_val := arr[i]       max_ind := i       (increase search_cost by 1) return max_ind

हमें ऐरे arr बनाना है जिसमें निम्नलिखित मानदंड हों: arr में ठीक n पूर्णांक हों। सभी तत्व arr[i] 1 से m की सीमा में हों (सम्मिलित) (0 <= i < n)। उपरोक्त एल्गोरिदम को arr पर लागू करने के बाद, search_cost का मान k के बराबर हो। हमें उल्लिखित शर्तों के तहत ऐरे arr बनाने के तरीकों की संख्या ढूंढनी है। उत्तर बहुत बड़ा हो सकता है इसलिए इसे मॉड्यूलो 10^9 + 7 पर गणना की जाएगी।

तो, यदि इनपुट n = 2, m = 3, k = 1 है, तो आउटपुट 6 होगा क्योंकि संभावित ऐरे हैं [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

  • m := 10^9 + 7

  • एक फ़ंक्शन add() परिभाषित करें, जो a, b लेगा,

  • ((a mod m) + (b mod m)) mod m लौटाएं

  • आकार 54 x 54 x 105 का एक ऐरे dp परिभाषित करें।

  • एक फ़ंक्शन help() परिभाषित करें, जो idx, m, k, currVal, n लेगा,

  • यदि k < 0, तो −

    • 0 लौटाएं

  • यदि idx, n + 1 के समान है, तो −

    • तब true लौटाएं जब k 0 हो

  • यदि dp[idx, k, currVal + 1], -1 के बराबर नहीं है, तो −

    • dp[idx, k, currVal + 1] लौटाएं

  • ret := 0

  • i := 1 से आरंभ करें, जब i <= m, अद्यतन करें (i को 1 से बढ़ाएं), करें −

    • यदि i > currVal, तो −

      • ret := add(help(idx + 1, m, k - 1, max(currVal,i), n), ret)

    • अन्यथा

      • ret := add(help(idx + 1, m, k, max(currVal,i), n), ret)

  • dp[idx, k, currVal + 1] = ret लौटाएं

  • मुख्य विधि से निम्नलिखित करें −

  • i := 0 से आरंभ करें, जब i < 54, अद्यतन करें (i को 1 से बढ़ाएं), करें −

    • j := 0 से आरंभ करें, जब j < 54, अद्यतन करें (j को 1 से बढ़ाएं), करें −

      • k := 0 से आरंभ करें, जब k < 105, अद्यतन करें (k को 1 से बढ़ाएं), करें −

        • dp[i, j, k] := -1

    • ret := help(1, m, k, -1, n)

  • ret लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

#include <bits/stdc++.h> using namespace std; typedef long long int lli; const lli m = 1e9 + 7; class Solution { public:    lli add(lli a, lli b) {       return ((a % m) + (b % m)) % m;    }    int dp[54][54][105];    int help(int idx, int m, int k, int currVal, int n) {       if (k < 0)          return 0;       if (idx == n + 1) {          return k == 0;       }       if (dp[idx][k][currVal + 1] != -1)          return dp[idx][k][currVal + 1];       int ret = 0;       for (int i = 1; i <= m; i++) {          if (i > currVal) {             ret = add(help(idx + 1, m, k - 1, max(currVal, i), n), ret);          }          else {             ret = add(help(idx + 1, m, k, max(currVal, i), n), ret);          }       }       return dp[idx][k][currVal + 1] = ret;    }    int numOfArrays(int n, int m, int k) {       for (int i = 0; i < 54; i++)          for (int j = 0; j < 54; j++)             for (int k = 0; k < 105; k++)                dp[i][j][k] = -1;       int ret = help(1, m, k, -1, n);       return ret;    } }; main() {    Solution ob;    cout << (ob.numOfArrays(2, 3, 1)); }

इनपुट

2, 3, 1

आउटपुट

6

  1. - C++ में STL का उपयोग करके सरणी के न्यूनतम और अधिकतम तत्व कैसे ज्ञात करें?

    यहां हम देखेंगे कि सरणी से अधिकतम और न्यूनतम तत्व कैसे ज्ञात करें। इसलिए यदि सरणी [12, 45, 74, 32, 66, 96, 21, 32, 27] की तरह है, तो अधिकतम तत्व 96 है, और न्यूनतम तत्व 12 है। हम algorithm.h हेडर फ़ाइल में मौजूद max_element() फ़ंक्शन और min_element() फ़ंक्शन का उपयोग करके क्रमशः अधिकतम और न्यूनतम तत्

  1. - C++ में STL का उपयोग करके सरणी का अधिकतम तत्व कैसे ज्ञात करें?

    यहां हम देखेंगे कि अधिकतम तत्व कैसे ज्ञात करें। इसलिए यदि सरणी [12, 45, 74, 32, 66, 96, 21, 32, 27] की तरह है, तो अधिकतम तत्व 96 है। हम algorithm.h हेडर फ़ाइल में मौजूद max_element() फ़ंक्शन का उपयोग करके अधिकतम तत्व प्राप्त कर सकते हैं। उदाहरण #include<iostream> #include<algorithm> usin

  1. - वर्तमान C या C++ स्टैंडर्ड डॉक्यूमेंट्स कहां मिल सकते हैं?

    आप वर्तमान C स्टैंडर्ड डॉक्यूमेंट्स ANSI वेब स्टोर पर पा सकते हैं। https://webstore.ansi.org/RecordDetail.aspx?sku=INCITS%2FISO%2FIEC+9899-2012 आप वर्तमान C++ स्टैंडर्ड डॉक्यूमेंट्स खरीदने के लिए ISO C++ वेबसाइट पर पा सकते हैं: https://www.iso.org/standard/68564.html ISO C++ स्टैंडर्ड का वर्किंग ड्