हमें पूर्णांक N और K दिए गए हैं। हमारे पास लंबाई N के द्विआधारी तार हैं, जिनमें केवल 0 और 1 हैं। लक्ष्य लंबाई N के ऐसे तारों की संख्या ज्ञात करना है जिनमें K लगातार 1 है। यानी, अगर N=3, और K=2, तो उन सभी 3-अंकीय बाइनरी स्ट्रिंग्स को गिनें, जिनमें लगातार 2 1 हों।
उदाहरण -111, यहाँ आसन्न 1 दो बार ( K बार ) दिखाई देता है।
011 और 110 में आसन्न 1 केवल एक बार दिखाई दिया।
हम पिछले मानों के परिणामों को संग्रहीत करके इसका समाधान करेंगे।
3D सरणी गणना [x] [y] [z] लेना। जहाँ x N है, y K है और z स्ट्रिंग का अंतिम अंक है ( 0 या 1 )
- N=1 के लिए, स्ट्रिंग्स "0" और "1" होंगी। आसन्न 1 की संख्या=0.
तो किसी भी K के लिए। यदि N=1, गिनती=0.
गिनती[1][के][0] =गिनती[1][के][1] =0.
- जब अंतिम अंक 0 हो, आसन्न 1 की गिनती को K के रूप में करने के लिए
K वाले के साथ N-1 लंबाई के सभी अंक + अंतिम 0 → नई लंबाई =N
यदि 1 से सटे K की संख्या C थी, तो अंत में 0 जोड़ने से वह संख्या नहीं बदलेगी।
गिनती[N][K][0] =गिनती[N-1][K][0] + count[N-1][K][1]
- जब अंतिम अंक 1 हो, आसन्न 1 की गणना को K के रूप में करने के लिए
लंबाई N-1 के सभी अंक 0 के साथ समाप्त होने वाले K + अंतिम 1 → नई लंबाई =N,
गिनती[N-1][K][0]
लंबाई के सभी अंक N-1, K-1 वाले के साथ 1 से समाप्त होते हैं + अंतिम 1 → नई लंबाई =N,
गिनती[N-1][K-1][1]
गिनती[एन][के][1] =गिनती[एन-1][के][0] + गिनती[एन-1][के-1][1]
कुल ऐसे तार =गिनती [एन] [के] [0] + गिनती [एन] [के] [1]
इनपुट
N=4, K=2
आउटपुट
Count of strings: 2
स्पष्टीकरण − 1110, 0111 लंबाई 4 के एकमात्र तार हैं जहां आसन्न 1 केवल दो बार दिखाई देता है।
1110- “11 10”, then “1 11 0” ( splitting to show which adjacent 1’s are counted ) 0111- “0 11 1”, then “01 11”. K=2, adjacent 1’s= 2 times
इनपुट
N=3, K=1
आउटपुट
Count of strings: 2
स्पष्टीकरण - 110, 011. लंबाई के एकमात्र तार हैं जहां आसन्न 1 एक बार दिखाई देता है।
111 में आसन्न 1 दो बार दिखाई देता है।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक एन और के तार की लंबाई को संग्रहीत करते हैं और नहीं। प्रत्येक में आसन्न 1 बार दिखाई देता है।
-
फ़ंक्शन स्ट्रिंगकाउंट (int n, int k) n और k को पैरामीटर के रूप में लेता है और K के साथ स्ट्रिंग्स की गिनती 1 के आसन्न देता है।
-
ऐरे काउंट [i] [j] [0/1] का उपयोग लंबाई के स्ट्रिंग्स की गिनती को स्टोर करने के लिए किया जाता है I साथ में j आसन्न 1 को 0 या 1 के साथ भेजना।
-
प्रारंभिक स्थिति गिनती है [1] [0] [0] =1; गिनती[1][0][1] =1;
-
अब 2 लंबाई के तार (i=2) से n लंबाई तक शुरू करें। ऐसे प्रत्येक स्ट्रिंग के लिए 1 से सटे Ktimes की संख्या की जाँच करें। j=0;j<=k, पिछली गणनाओं से। वर्तमान गणना [i] [j] [0] और गिनती [i] [j] [1] अपडेट करें।
-
अगर j-1>=0, आसन्न 1 की संख्या 1 से अधिक है। फिर 1 के साथ समाप्त होने वाले स्ट्रिंग्स की गिनती को गिनती के रूप में अपडेट करें [i] [j] [1] + गिनती [i - 1] [j - 1] [1] ];
-
अंत में गिनती [एन] [के] [0] और गिनती [एन] [के] [1] जोड़ें। परिणामस्वरूप इसे स्टोर करें।
- इच्छित गणना के रूप में परिणाम लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
//count of strings with length=n and adajcent 1's=k
int count[n + 1][k + 1][2]={0};
//count[n][k][0] -- strings with length=n and adajcent 1's=k last character is 0
//count[n][k][1] -- strings with length=n and adajcent 1's=k last character is 1
// If n = 1 and k = 0.
count[1][0][0] = 1;
count[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
// number of adjacent 1's can not exceed 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 <<"Strings of length 6 and 3 adjacent 1's in each :"<< stringcount(N,K);
return 0;
} आउटपुट
Strings of length 6 and 3 adjacent 1's in each :7