मान लीजिए, हमारे पास एक पूर्णांक N है, हमें लंबाई N के सभी संभावित अलग-अलग बाइनरी स्ट्रिंग्स की संख्या खोजनी है, जिनमें कम से कम तीन लगातार 1s हों। तो यदि n = 4, तो संख्याएं 0111, 1110, 1111 होंगी, इसलिए आउटपुट 3 होगा।
इसे हल करने के लिए, हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग कर सकते हैं। तो DP(i, x) लंबाई i के स्ट्रिंग्स की संख्या दर्शाता है जिसमें स्थिति i+1 से i+x में x लगातार 1s हों। फिर पुनरावृत्ति संबंध इस तरह होगा -
DP(i, x) = DP(i – 1, 0) + DP(i – 1, x + 1)।
पुनरावृत्ति इस तथ्य पर आधारित है, कि या तो स्ट्रिंग में स्थिति i पर 0 या 1 मौजूद हो सकता है।
- यदि इसमें ith इंडेक्स पर 0 है, तो (i-1)th स्थिति के लिए x का मान = 0
- यदि इसमें ith इंडेक्स पर 1 है, तो (i-1)th स्थिति के लिए 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
