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

C++ में दो अलग-अलग सेट्स से एक या अधिक जोड़े चुनने के तरीके

इस समस्या में, हमें दो पॉजिटिव संख्याएं n और m (n <= m) दी गई हैं जो क्रमशः दो सेट्स के कुल आइटम्स की संख्या हैं। हमारा कार्य इन सेट्स के आइटम्स से जोड़े (एक या अधिक) चुनने के कुल तरीकों की संख्या ज्ञात करना है।

उदाहरण

इनपुट

2 2

आउटपुट

6

व्याख्या

हमारे पास दो सेट्स हैं दोनों में दो एलिमेंट्स हैं

Set A = {1, 2}
Set B = {3, 4}

एक समय में एक जोड़ा व्यवस्थित करने के तरीके: (1..3), (1...4), (2..3), (2...4)

एक समय में दो जोड़े व्यवस्थित करने के तरीके: (1...3, 2...4), (1...4, 2...3)

इस समस्या को हल करने के लिए, हम सेट्स के एलिमेंट्स के कॉम्बिनेशन का उपयोग करेंगे। निम्नलिखित एक साधारण कॉम्बिनेशन सूत्र है जो गिनती ज्ञात कर सकता है।

Ways = Σ^n i=1 nCi * mCi * i! = Σ^n i=1 ( nPi * mPi ) / i

हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम:

उदाहरण

#include <iostream>
using namespace std;

int* fact, *inverseMod;
const int mod = 1e9 + 7;

int power(int x, int y, int p) {
    int res = 1;
    x = x % p;
    while (y) {
        if (y & 1)
            res = (1LL * res * x) % p;
        y = y >> 1;
        x = (1LL * x * x) % p;
    }
    return res;
}

void calculate(int n) {
    fact[0] = inverseMod[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (1LL * fact[i - 1] * i) % mod;
        inverseMod[i] = power(fact[i], mod - 2, mod);
    }
}

int nPr(int a, int b) {
    return (1LL * fact[a] * inverseMod[a - b]) % mod;
}

int selectPairCount(int n, int m) {
    fact = new int[m + 1];
    inverseMod = new int[m + 1];
    calculate(m);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += (1LL * ((1LL * nPr(n, i) * nPr(m, i)) % mod) * inverseMod[i]) % mod;
        if (ans >= mod)
            ans %= mod;
    }
    return ans;
}

int main() {
    int n = 2, m = 2;
    cout << "जोड़े चुनने के तरीकों की संख्या: " << selectPairCount(n, m);
    return 0;
}

आउटपुट

जोड़े चुनने के तरीकों की संख्या: 6
  1. C++ में स्रोत से k लंबाई से अधिक का पथ मौजूद है या नहीं खोजें C++ में स्रोत से k लंबाई से अधिक का पथ मौजूद है या नहीं खोजें

    अवधारणाएक दिए गए ग्राफ के संबंध में, ग्राफ में एक स्रोत शीर्ष और एक संख्या k (यहां k स्रोत शीर्ष और गंतव्य शीर्ष के बीच ग्राफ के पथ की लंबाई को इंगित करता है), हमारा कार्य यह निर्धारित करना है कि क्या दिया गया स्रोत से शुरू होकर किसी अन्य शीर्ष (यानी गंतव्य) पर समाप्त होने वाला एक सरल पथ (बिना किसी

  1. - C++ में दो से अधिक (या सरणी) संख्याओं का GCD प्रोग्राम

    दो संख्याओं के सामान्य भाजक वे संख्याएं हैं जो उन दोनों के भाजक हैं। उदाहरण के लिए, 12 के भाजक 1, 2, 3, 4, 6, 12 हैं। 18 के भाजक 1, 2, 3, 6, 9, 18 हैं। इस प्रकार, 12 और 18 के सामान्य भाजक 1, 2, 3, 6 हैं। इनमें सबसे बड़ा, शायद आश्चर्यजनक रूप से, 12 और 18 का महत्तम समापवर्तक (GCD) कहलाता है। दो पूर्ण

  1. - C++ में दो से अधिक (या सरणी) संख्याओं का GCD प्रोग्राम

    यहां हम देखेंगे कि दो से अधिक संख्याओं का GCD कैसे प्राप्त किया जा सकता है। दो संख्याओं का GCD खोजना आसान है। जब हम दो से अधिक संख्याओं का GCD खोजना चाहते हैं, तो हमें GCD के साहचर्य नियम का पालन करना होगा। उदाहरण के लिए, यदि हम {w, x, y, z} का GCD खोजना चाहते हैं, तो यह {gcd(w,x), y, z} होगा, फिर