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

C++ में डोमिनोज़ और ट्रोमिनोज़ से क्षेत्र भरने के कॉन्फिगरेशन की संख्या गिनने का प्रोग्राम


परिचय

मान लीजिए हमारे पास दो आकार हैं: डोमिनो (Domino) और ट्रोमिनो (Tromino)। डोमिनो 2×1 आकार के होते हैं और ट्रोमिनो 'L' जैसे आकार के होते हैं। उन्हें नीचे दिखाए अनुसार घुमाया जा सकता है।

C++ में डोमिनोज़ और ट्रोमिनोज़ से क्षेत्र भरने के कॉन्फिगरेशन की संख्या गिनने का प्रोग्राम

यदि हमारे पास एक संख्या n है, तो हमें इन दो प्रकार के टुकड़ों से 2×n बोर्ड भरने के कॉन्फिगरेशन की संख्या ढूंढनी है। टाइलिंग में, हर वर्ग एक टाइल से ढका होना चाहिए।

तो यदि इनपुट 3 है, तो आउटपुट 5 होगा।

समाधान दृष्टिकोण

यह एक डायनामिक प्रोग्रामिंग समस्या है जिसमें पुनरावृत्ति संबंध है:

dp[i] = 2×dp[i-1] + dp[i-3]

आधार मामले: dp[1]=1, dp[2]=2, dp[3]=5

उदाहरण कोड

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

const int MOD = 1e9 + 7;

int add(int a, int b){
    return ((a % MOD) + (b % MOD)) % MOD;
}

class Solution {
public:
    int solve(int N) {
        vector<int> dp(N + 5);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;
        for(int i = 4; i <= N; i++){
            dp[i] = add(2 * dp[i - 1], dp[i - 3]);
        }
        return dp[N];
    }
};

int main(){
    Solution ob;
    cout << (ob.solve(3));
    return 0;
}

इनपुट

3

आउटपुट

5

निष्कर्ष

यह LeetCode "Domino and Tromino Tiling" समस्या (790) का समाधान है। पुनरावृत्ति dp[n] = 2*dp[n-1] + dp[n-3] अंतिम कॉलम में टाइल प्लेसमेंट पैटर्न से आती है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।


  1. - C++ में ऐरे में सम और विषम एलिमेंट्स की गिनती

    इस ट्यूटोरियल में, हम ऐरे में सम और विषम एलिमेंट्स की संख्या खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।इसके लिए हमें एक ऐरे प्रदान किया जाएगा। हमारा कार्य दिए गए ऐरे में सम और विषम एलिमेंट्स की संख्या की गणना करना है।उदाहरण#include<iostream> using namespace std; void CountingEvenOdd(int arr[],

  1. - C++ में संख्या को केवल 3 और 8 अंकों में बदलना

    इस ट्यूटोरियल में, हम एक संख्या को केवल 3 और 8 अंकों वाले में बदलने के लिए एक प्रोग्राम पर चर्चा करेंगे।इसके लिए हमें एक रैंडम संख्या प्रदान की जाएगी। हमारा कार्य संख्या के अंकों को केवल 3 और 8 में बदलना है या तो संख्या से 1 जोड़/घटाकर या संख्या के अंकों को किसी वांछित अंक में बदलकर।उदाहरण#include &

  1. - पायथन में 3 x n बॉक्स को 2 x 1 डोमिनोज से भरने के तरीकों की संख्या गिनने का प्रोग्राम

    मान लीजिए हमारे पास एक संख्या n है, हमें (3 x n) ब्लॉक को 1 x 2 डोमिनोज से भरने के तरीकों की संख्या ढूंढनी है। हम आवश्यकता पड़ने पर डोमिनोज को घुमा सकते हैं। यदि उत्तर बहुत बड़ा है तो इसे 10^9 + 7 से मॉड करें।उदाहरण के लिए, यदि इनपुट n = 4 है, तो आउटपुट 11 होगा।समाधान दृष्टिकोणइस समस्या को हल करने क