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

C++ में स्वर (Vowel) क्रमपरिवर्तन की गिनती (Count Vowels Permutation)


समस्या विवरण

एक संख्या n दी गई है। लंबाई n के ऐसे स्ट्रिंग्स की गिनती करनी है जो निम्न नियमों का पालन करते हैं:

  • प्रत्येक अक्षर लोअरकेस स्वर (a, e, i, o, u) है।
  • 'a' के बाद केवल 'e' आ सकता है।
  • 'e' के बाद केवल 'a' या 'i' आ सकता है।
  • 'i' के बाद 'i' नहीं आ सकता (अन्य सभी स्वर आ सकते हैं)।
  • 'o' के बाद केवल 'i' या 'u' आ सकता है।
  • 'u' के बाद केवल 'a' आ सकता है।

उत्तर मॉड्यूलो 10^9 + 7 में लौटाएं।

उदाहरण

इनपुट: n = 2

आउटपुट: 10

संभावित स्ट्रिंग्स: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua"

समाधान दृष्टिकोण (मैट्रिक्स एक्सपोनेंशिएशन / DP)

संक्रमण मैट्रिक्स (Transition Matrix) 5×5 बनाएं जहां M[i][j] = 1 यदि स्वर i के बाद स्वर j आ सकता है।

तब M^(n-1) की सभी प्रविष्टियों का योग उत्तर है।

स्वर क्रम: a=0, e=1, i=2, o=3, u=4

M = {{0,1,0,0,0},
     {1,0,1,0,0},
     {1,1,0,1,1},
     {0,0,1,0,1},
     {1,0,0,0,0}}

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const lli MOD = 1e9+7;

lli add(lli a, lli b) { return (a%MOD + b%MOD)%MOD; }
lli mul(lli a, lli b) { return (a%MOD * b%MOD)%MOD; }

class Solution {
public:
    void multiply(lli A[5][5], lli B[5][5]) {
        lli C[5][5] = {};
        for (int i=0;i<5;i++)
            for (int j=0;j<5;j++)
                for (int k=0;k<5;k++)
                    C[i][j] = add(C[i][j], mul(A[i][k], B[k][j]));
        for (int i=0;i<5;i++)
            for (int j=0;j<5;j++)
                A[i][j] = C[i][j];
    }
    
    lli solve(lli n) {
        lli A[5][5] = {{0,1,0,0,0},{1,0,1,0,0},{1,1,0,1,1},{0,0,1,0,1},{1,0,0,0,0}};
        lli res[5][5] = {};
        for (int i=0;i<5;i++) res[i][i] = 1; // पहचान मैट्रिक्स
        
        n--;
        for (int i=1; i<=n; i++) multiply(res, A);
        
        lli sum = 0;
        for (int i=0;i<5;i++)
            for (int j=0;j<5;j++)
                sum = add(sum, res[i][j]);
        return sum;
    }
    
    int countVowelPermutation(int n) { return solve(n); }
};

int main() {
    Solution ob;
    cout << ob.countVowelPermutation(2);
    return 0;
}

आउटपुट

10
  1. - C++ में पॉइंटर का उपयोग करके स्ट्रिंग में वॉवेल्स गिनना

    समस्या विवरण पॉइंटर का उपयोग करके स्ट्रिंग में वॉवेल्स की संख्या ढूंढने के लिए आपको स्ट्रिंग, वॉवेल्स और स्ट्रिंग के साथ पॉइंटर का उपयोग कैसे करना है, यह समझने की आवश्यकता है। स्ट्रिंग कैरेक्टर्स की एक सरणी है। और वॉवेल्स {a, e, i, o, u} सेट के कैरेक्टर्स हैं। पॉइंटर एक वेरिएबल है जो किसी वेरिएबल

  1. - C++ में पॉइंटर का उपयोग करके स्ट्रिंग में स्वरों (Vowels) की गणना करें

    स्ट्रिंग से स्वरों को प्राप्त करने के लिए, हमें स्ट्रिंग के प्रत्येक वर्ण के माध्यम से पुनरावृति करनी होगी। यहां हमें स्ट्रिंग के माध्यम से आगे बढ़ने के लिए पॉइंटर्स का उपयोग करना होगा। इसके लिए हमें C-शैली की स्ट्रिंग्स की आवश्यकता है। यदि स्ट्रिंग str द्वारा इंगित की जाती है, तो *str शुरुआत में प

  1. - C++ में लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन

    लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन यहां हम देखेंगे कि C++ में स्ट्रिंग के लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन को कैसे जनरेट करें। लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन मूल रूप से बड़ा पर्मुटेशन है। उदाहरण के लिए, ACB का नेक्स्ट BAC होगा। कुछ मामलों में, लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन मौजूद नहीं