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

C++ में K बार आने वाले आसन्न दो सेट बिट्स वाले बाइनरी स्ट्रिंग्स की गणना करें


हमें पूर्णांक N और K दिए गए हैं। हमारे पास लंबाई N के बाइनरी स्ट्रिंग्स हैं, जिनमें केवल 0 और 1 हैं। लक्ष्य ऐसे स्ट्रिंग्स की संख्या ढूंढना है जिनकी लंबाई N हो और जिनमें K लगातार 1 हों। यानी, यदि N=3, और K=2, तो उन सभी 3-अंकीय बाइनरी स्ट्रिंग्स की गणना करें जिनमें 2 लगातार 1 हों।

उदाहरण: 111, यहां आसन्न 1 दो बार आते हैं (K बार)।

011 और 110 में आसन्न 1 केवल एक बार आए।

हम पिछले मानों के परिणामों को संग्रहीत करके इसे हल करेंगे।

3D सरणी count[x][y][z] लेते हैं। जहां x N है, y K है और z स्ट्रिंग का अंतिम अंक है (0 या 1)।

  • N=1 के लिए, स्ट्रिंग्स "0" और "1" होंगी। आसन्न 1 की गणना = 0।

इसलिए किसी भी K के लिए। यदि N=1, count=0।

count[1][K][0] = count[1][K][1] = 0।

  • जब अंतिम अंक 0 हो, आसन्न 1 की गणना K बनाने के लिए

लंबाई N-1 के सभी अंक जिनमें K 1 हों + अंत में 0 → नई लंबाई = N

यदि K आसन्न 1 की गणना C थी तो अंत में 0 जोड़ने से वह गणना नहीं बदलेगी।

count[N][K][0] = count[N-1][K][0] + count[N-1][K][1]

  • जब अंतिम अंक 1 हो, आसन्न 1 की गणना K बनाने के लिए

लंबाई N-1 के सभी अंक जो 0 पर समाप्त होते हैं जिनमें K 1 हों + अंत में 1 → नई लंबाई = N,

count[N-1][K][0]

लंबाई N-1 के सभी अंक जो 1 पर समाप्त होते हैं जिनमें K-1 1 हों + अंत में 1 → नई लंबाई = N,

count[N-1][K-1][1]

count[N][K][1] = count[N-1][K][0] + count[N-1][K-1][1]

ऐसे कुल स्ट्रिंग्स = count[N][K][0] + count[N][K][1]

इनपुट

N=4, K=2

आउटपुट

स्ट्रिंग्स की संख्या: 2

व्याख्या: 1110, 0111 लंबाई 4 के केवल स्ट्रिंग्स हैं जहां आसन्न 1 केवल दो बार आते हैं।

1110- "11 10", फिर "1 11 0" (आसन्न 1 दिखाने के लिए विभाजित) 0111- "0 11 1", फिर "01 11"। K=2, आसन्न 1= 2 बार

इनपुट

N=3, K=1

आउटपुट

स्ट्रिंग्स की संख्या: 2

व्याख्या: 110, 011। लंबाई 3 के केवल स्ट्रिंग्स जहां आसन्न 1 एक बार आते हैं।

111 में आसन्न 1 दो बार आते हैं।

प्रयुक्त दृष्टिकोण

  • पूर्णांक N और K स्ट्रिंग्स की लंबाई और प्रत्येक में आसन्न 1 की संख्या संग्रहीत करते हैं।
  • फ़ंक्शन stringcount(int n, int k) n और k को पैरामीटर के रूप में लेता है और K बार आसन्न 1 वाले स्ट्रिंग्स की संख्या लौटाता है।
  • सरणी count[i][j][0/1] का उपयोग लंबाई i के स्ट्रिंग्स की गणना संग्रहीत करने के लिए किया जाता है जिनमें j आसन्न 1 हों और जो 0 या 1 पर समाप्त होते हों।
  • प्रारंभिक स्थिति है count[1][0][0] = 1; count[1][0][1] = 1;
  • अब 2 लंबाई के स्ट्रिंग्स (i=2) से n लंबाई तक शुरू करें। प्रत्येक ऐसे स्ट्रिंग के लिए पिछली गणनाओं से K बार आसन्न 1 की गणना जांचें। j=0;j<=k, वर्तमान count[i][j][0] और count[i][j][1] को अपडेट करें।
  • यदि j-1>=0, आसन्न 1 की गणना 1 से अधिक है। फिर 1 पर समाप्त होने वाले स्ट्रिंग्स की गणना को count[i][j][1] + count[i - 1][j - 1][1] के रूप में अपडेट करें;
  • अंत में count[n][k][0] और count[n][k][1] जोड़ें। इसे परिणाम के रूप में संग्रहीत करें।
  • वांछित गणना के रूप में परिणाम लौटाएं।

उदाहरण कोड

#include <bits/stdc++.h> using namespace std; int stringcount(int n, int k){ // लंबाई=n और आसन्न 1=k वाले स्ट्रिंग्स की संख्या int count[n + 1][k + 1][2]={0}; //count[n][k][0] -- लंबाई=n और आसन्न 1=k वाले स्ट्रिंग्स अंतिम अंक 0 है //count[n][k][1] -- लंबाई=n और आसन्न 1=k वाले स्ट्रिंग्स अंतिम अंक 1 है // यदि n = 1 और k = 0. count[1][0][0] = 1; count[1][0][1] = 1; for (int i = 2; i <= n; i++) { // आसन्न 1 की संख्या i-1 से अधिक नहीं हो सकती for (int j = 0; j <= k; j++) { count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1]; count[i][j][1] = count[i - 1][j][0]; if (j - 1 >= 0) count[i][j][1] =count[i][j][1] + count[i - 1][j - 1][1]; } } int result=count[n][k][0]+count[n][k][1]; return result; } int main(){ int N = 6, K = 3; cout <<"लंबाई 6 के स्ट्रिंग्स और प्रत्येक में 3 आसन्न 1: "<< stringcount(N,K); return 0; }

आउटपुट

लंबाई 6 के स्ट्रिंग्स और प्रत्येक में 3 आसन्न 1: 7

  1. C++ में दो बाइनरी स्ट्रिंग्स को जोड़ें C++ में दो बाइनरी स्ट्रिंग्स को जोड़ें

    दो बाइनरी संख्या वाली स्ट्रिंग्स दी गई हैं, हमें उन दो बाइनरी स्ट्रिंग्स को जोड़कर प्राप्त परिणाम ढूंढना है और परिणाम को बाइनरी स्ट्रिंग के रूप में लौटाना है। बाइनरी संख्याएं वे संख्याएं हैं जिन्हें या तो 0 या 1 के रूप में व्यक्त किया जाता है। 2 बाइनरी संख्याओं को जोड़ते समय बाइनरी जोड़ का नियम हो

  1. - C++ में k सेट बिट्स के साथ नंबर को अधिकतम करने के लिए न्यूनतम फ्लिप्स

    समस्या कथनदो नंबर n और k दिए गए हैं, हमें दिए गए नंबर को उसके बिट्स फ्लिप करके अधिकतम करने के लिए आवश्यक न्यूनतम फ्लिप्स की संख्या ढूंढनी है जैसे कि परिणामी नंबर में ठीक k सेट बिट्स हों। कृपया ध्यान दें कि इनपुट को कंडीशन पूरी करनी चाहिए कि k, n में बिट्स की संख्या से कम हो।उदाहरणमान लीजिए n = 9 और

  1. - C++ में n बाइनरी स्ट्रिंग्स जोड़ना

    यहां हम देखेंगे कि n बाइनरी संख्याओं को स्ट्रिंग के रूप में जोड़ने वाला प्रोग्राम कैसे लिखें। आसान तरीका है बाइनरी स्ट्रिंग को उसके दशमलव समतुल्य में बदलना, फिर उन्हें जोड़ना और वापस बाइनरी में बदलना। यहां हम मैन्युअली जोड़ करेंगे। एल्गोरिदम addTwoBinary(bin1, bin2) = 0 then s := s + bi