एक बाइनरी संख्या वह संख्या है जिसमें केवल दो होते हैं यानी 0 या 1। हर बाइनरी संख्या बाइनरी बिट्स की एक धारा है, और हम इसे बाइनरी स्ट्रिंग मानते हैं। इस स्ट्रिंग के लिए, हमें उन बाइनरी स्ट्रिंग्स की संख्या ढूंढनी होगी जिनमें लगातार 1's नहीं हैं जो N बिट्स की हैं।
उदाहरण के लिए, N = 5 के लिए बाइनरी स्ट्रिंग्स जो दिए गए प्रतिबंधों को पूरा करती हैं: 00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101
एक विधि सभी N-अंकीय स्ट्रिंग्स उत्पन्न करना और केवल उन स्ट्रिंग्स को प्रिंट करना है जो दिए गए प्रतिबंधों को पूरा करती हैं। लेकिन यह विधि काम करने के मामले में उतनी कुशल नहीं है।
दूसरी विधि पुनरावृत्ति (recursion) का उपयोग करना है। पुनरावृत्ति में प्रत्येक बिंदु पर, हम आंशिक रूप से बनी संख्या में 0 और 1 जोड़ते हैं और एक कम अंक के साथ पुनरावृत्ति करते हैं। यहां ट्रिक यह है कि हम 1 जोड़ते हैं और केवल तभी पुनरावृत्ति करते हैं जब आंशिक रूप से बनी संख्या का अंतिम अंक 0 हो, इस तरह, आउटपुट स्ट्रिंग में कभी भी लगातार 1's नहीं होंगे।
Input: n = 5 Output: 5-अंकीय बाइनरी स्ट्रिंग्स जिनमें कोई लगातार 1's नहीं हैं, की संख्या 13 है
उदाहरण
#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
if (n == 0)
return 0;
if (n == 1) {
if (last_digit)
return 1;
else
return 2;
}
if (last_digit == 0)
return countStrings(n - 1, 0) + countStrings(n - 1, 1);
else
return countStrings(n - 1, 0);
}
int main() {
int n = 5;
cout << "Number of " << n << "-digit binary strings without any "
"consecutive 1's are " << countStrings(n, 0);
return 0;
}
