हमें पूर्णांक 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