लगातार 1 के बिना बाइनरी स्ट्रिंग की गणना करें

इस समस्या में, हमें कुछ बाइनरी संख्याएं ढूंढनी होती हैं जिनमें लगातार 1s नहीं होते हैं। 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]

इनपुट और आउटपुट

Input:
This algorithm takes number of bits for a binary number. Let the input is 4.
Output:
It returns the number of binary strings which have no consecutive 1’s.
Here the result is: 8. (There are 8 binary strings which has no consecutive 1’s)

एल्गोरिदम

countBinNums(n)

इनपुट: n बिट्स की संख्या है।
आउटपुट - गिनें कि कितनी संख्याएँ मौजूद हैं जिनमें लगातार 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 consecitive 1's: "<<countBinNums(n) << endl;
   return 0;
}

आउटपुट

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