बाइनरी प्रतिनिधित्व में लगातार 1s के साथ 1 से n बिट संख्याएं?

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

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

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

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

इनपुट

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

आउटपुट

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

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

एल्गोरिदम

गिनतीBinNums(n)

Input: n is the number of bits.
Output: Count how many numbers are present which have no consecutive 1.
Begin
   define lists with strings ending with 0 and ending with 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 << "Enter number of bits: "; cin >> n;
   cout << "Number of binary numbers without consecutive 1's: "<<countBinNums(n) << endl;
   return 0;
}

आउटपुट

Enter number of bits: 4
Number of binary numbers without consecutive 1's: 8