लगातार 1's के बिना 1 से n बिट बाइनरी संख्याएं

इस समस्या में हमें उन बाइनरी संख्याओं को ढूंढना है जिनमें लगातार 1's नहीं हैं। 3-बिट बाइनरी स्ट्रिंग में, तीन बाइनरी संख्याएं 011, 110, 111 हैं जिनमें लगातार 1's हैं, और पांच संख्याएं ऐसी हैं जिनमें लगातार 1's नहीं हैं। इसलिए 3-बिट संख्याओं के लिए इस एल्गोरिदम को लागू करने पर उत्तर 5 होगा।

यदि a[i] i बिट्स वाली उन बाइनरी संख्याओं का समुच्चय है जिनमें कोई लगातार 1's नहीं हैं, और b[i] i बिट्स वाली उन बाइनरी संख्याओं का समुच्चय है जिनमें लगातार 1's हैं, तो निम्न पुनरावृत्ति संबंध हैं:

a[i] := a[i - 1] + b[i - 1]

b[i] := a[i - 1]

इनपुट

यह एल्गोरिदम बाइनरी संख्या के लिए बिट्स की संख्या लेता है। मान लीजिए इनपुट 4 है।

आउटपुट

यह उन बाइनरी स्ट्रिंग्स की संख्या लौटाता है जिनमें लगातार 1's नहीं हैं।

यहां परिणाम 8 है। (8 बाइनरी स्ट्रिंग्स हैं जिनमें लगातार 1's नहीं हैं)

एल्गोरिदम

countBinNums(n)

Input: n बिट्स की संख्या है। Output: गिनें कि कितनी संख्याएं मौजूद हैं जिनमें लगातार 1 नहीं हैं।
Begin
    0 से समाप्त होने वाली और 1 से समाप्त होने वाली स्ट्रिंग्स के साथ सूचियों को परिभाषित करें
    endWithZero[0] := 1
    endWithOne[0] := 1
    for i := 1 to n-1, do
        endWithZero[i] := endWithZero[i-1] + endWithOne[i-1]
        endWithOne[i] := endWithZero[i-1]
    done
    return endWithZero[n-1] + endWithOne[n-1]
End

उदाहरण

#include <iostream>
using namespace std;

int countBinNums(int n) {
    int endWithZero[n], endWithOne[n];
    endWithZero[0] = endWithOne[0] = 1;
    for (int i = 1; i < n; i++) {
        endWithZero[i] = endWithZero[i-1] + endWithOne[i-1];
        endWithOne[i] = endWithZero[i-1];
    }
    return endWithZero[n-1] + endWithOne[n-1];
}

int main() {
    int n;
    cout << "बिट्स की संख्या दर्ज करें: "; cin >> n;
    cout << "लगातार 1's के बिना बाइनरी संख्याओं की संख्या: " << countBinNums(n) << endl;
    return 0;
}

आउटपुट

बिट्स की संख्या दर्ज करें: 4
लगातार 1's के बिना बाइनरी संख्याओं की संख्या: 8