C/C++ में लगातार 1 के बिना बाइनरी स्ट्रिंग्स की संख्या गिनने का प्रोग्राम

समस्या विवरण

यहां हम एक दिलचस्प समस्या देखेंगे। मान लीजिए n का एक मान दिया गया है। हमें लंबाई n के सभी स्ट्रिंग्स ढूंढने हैं, जैसे कि कोई लगातार 1 न हों। यदि n = 2, तो संख्याएं {00, 01, 10} हैं, तो आउटपुट 3 है।

हम इसे डायनामिक प्रोग्रामिंग का उपयोग करके हल कर सकते हैं। मान लीजिए हमारे पास 'a' और 'b' टेबल हैं। जहां a[i] लंबाई i की बाइनरी स्ट्रिंग्स की संख्या संग्रहीत कर रहा है, जहां कोई लगातार 1 नहीं हैं, और 0 से समाप्त होती हैं। इसी तरह, b वही रखता है लेकिन संख्याएं 1 से समाप्त होती हैं। हम वहां 0 या 1 जोड़ सकते हैं जहां अंतिम 0 है, लेकिन केवल 0 जोड़ें यदि अंतिम 1 है।

एल्गोरिदम

noConsecutiveOnes(n)
शुरुआत
    आकार n के ऐरे a और b परिभाषित करें
    a[0] := 1
    b[0] := 1
    i को 1 से n तक लूप
        a[i] := a[i-1] + b[i-1]
        b[i] := a[i-1]
    अंत लूप
    वापस a[n-1] + b[n-1]
अंत

C++ प्रोग्राम उदाहरण

#include <iostream>
using namespace std;

int noConsecutiveOnes(int n) {
    int a[n], b[n];
    a[0] = 1;
    b[0] = 1;
    for (int i = 1; i < n; i++) {
        a[i] = a[i-1] + b[i-1];
        b[i] = a[i-1];
    }
    return a[n-1] + b[n-1];
}

int main() {
    cout << noConsecutiveOnes(4) << endl;
}

आउटपुट

8