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

C++ में नॉन-क्रॉसिंग हैंडशेक्स

मान लीजिए हमारे पास लोगों की एक सम संख्या n है जो एक वृत्त के चारों ओर खड़े हैं और प्रत्येक व्यक्ति किसी और से हाथ मिलाता है, ताकि कुल n/2 हैंडशेक हों। हमें उन तरीकों की संख्या ज्ञात करनी है जिनसे ये हैंडशेक हो सकते हैं ताकि कोई भी हैंडशेक क्रॉस न करे। उत्तर बहुत बड़ा हो सकता है इसलिए उत्तर को 10^9 + 7 से मॉड्यूलो करें।

तो, यदि इनपुट n = 2 है, तो आउटपुट 1 होगा।

C++ में नॉन-क्रॉसिंग हैंडशेक्स

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

  • m := 10^9 + 7

  • आकार (n+1) का एक ऐरे dp परिभाषित करें

  • dp[0] := 1

  • i := 0 से शुरू करें, जब i <= n, i := i + 2 से अपडेट करें, करें:

    • j := 0 से शुरू करें, जब j <= i-2, j := j + 2 से अपडेट करें, करें:

      • dp[i] := dp[i] + (dp[j] mod m * dp[i - 2 - j] mod m)

      • dp[i] := dp[i] mod m

  • dp[n] mod m लौटाएं

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

उदाहरण

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

const int m = 1e9+7;
typedef long long int lli;

class Solution {
public:
    int numberOfWays(int n) {
        vector dp(n+1);
        dp[0] = 1;
        for(int i = 0; i <= n; i+=2) {
            for(int j = 0; j <= i-2; j+=2) {
                dp[i] += (dp[j]%m * dp[i-2-j]%m)%m;
                dp[i] %= m;
            }
        }
        return dp[n]%m;
    }
};

int main() {
    Solution ob;
    cout << (ob.numberOfWays(2));
}

इनपुट

2

आउटपुट

1
  1. - C++ में उन जोड़े (A ≤ N, B ≤ N) की गिनती जिनका gcd(A, B) = B हो

    हमें एक इनपुट N दिया गया है। लक्ष्य A, B के उन सभी जोड़े ढूंढना है जैसे कि 1 ≤ A ≤ N और 1 ≤ B ≤ N और GCD(A, B) = B हो। सभी जोड़े का महत्तम समापवर्तक B है। उदाहरण सहित समझ इनपुट - N=5 आउटपुट - जोड़े (A ≤ N, B ≤ N) जिनका gcd(A, B) = B है: 10 व्याख्या जोड़े (A ≤ N, B ≤ N) जिनका gcd(A, B) = B है: (1,

  1. - C++ में सरणी में x < y वाले युग्मों की गणना

    हमें एक पूर्णांक सरणी दी गई है और कार्य दिए गए सरणी मानों का उपयोग करके बनने वाले कुल युग्मों (x, y) की संख्या गिनना है जैसे कि x का पूर्णांक मान y से कम हो। इनपुट - int arr[] = {2, 4, 3, 1} आउटपुट - सरणी में x < y वाले युग्मों (x, y) की संख्या - 6 व्याख्या - XYX < Y 24

  1. C++ में सरणी में क्रॉस लाइन्स की गिनती C++ में सरणी में क्रॉस लाइन्स की गिनती

    हमें विशिष्ट तत्वों की एक असॉर्टेड सरणी दी गई है। लक्ष्य सरणी के क्रमबद्ध होने के बाद क्रॉस लाइन्स ढूंढना है। क्रॉस लाइन्स को नीचे दिखाए अनुसार गिना जाता है - Arr[]={ 1,2,4,3,5 } यहां 3 क्रॉस लाइन्स हैं जैसा कि नीचे दिखाया गया है Arr[]= { 1,2,3,4,5 }. कोई क्रॉस लाइन्स नहीं क्योंकि सरणी पहले से क