मान लीजिए, हमारे पास एक पूर्णांक N है, हमें लंबाई N के सभी संभावित अलग-अलग बाइनरी स्ट्रिंग्स की संख्या ज्ञात करनी है, जिनमें कम से कम तीन लगातार 1s हैं। तो अगर n =4 है, तो संख्याएँ 0111, 1110, 1111 होंगी, इसलिए आउटपुट 3 होगा।
इसे हल करने के लिए, हम डायनेमिक प्रोग्रामिंग दृष्टिकोण का उपयोग कर सकते हैं। तो DP(i, x) i + 1 से i + x की स्थिति में x क्रमागत 1s के साथ लंबाई i के स्ट्रिंग्स की संख्या को इंगित करता है। तब पुनरावर्तन संबंध इस प्रकार होगा -
DP(i, x) =DP(i – 1, 0) + DP(i – 1, x + 1)।
पुनरावृत्ति इस तथ्य पर आधारित है कि या तो स्ट्रिंग में 0 या 1 स्थिति i पर मौजूद हो सकती है।
- यदि इसमें 0 है, तो ith इंडेक्स पर तो (i - 1)वें स्थान के लिए x =0
- यदि यह 1 के सूचकांक में है तो (i - 1) के लिए x का मान =1 + स्थिति i पर x का मान
उदाहरण
#include<iostream>
using namespace std;
int n;
int numberCount(int i, int x, int table[][4]) {
if (i < 0)
return x == 3;
if (table[i][x] != -1)
return table[i][x];
table[i][x] = numberCount(i - 1, 0, table);
table[i][x] += numberCount(i - 1, x + 1, table);
return table[i][x];
}
int main() {
n = 4;
int table[n][4];
for (int i = 0; i < n; i++)
for (int j = 0; j < 4; j++)
table[i][j] = -1;
for (int i = 0; i < n; i++) {
table[i][3] = (1 << (i + 1));
}
cout << "The number of binary strings with at least 3 consecutive 1s: " << numberCount(n - 1, 0, table);
} आउटपुट
The number of binary strings with at least 3 consecutive 1s: 3