इस समस्या में, हमें कुछ बाइनरी संख्याएं ढूंढनी हैं जिनमें लगातार 1 नहीं हैं। एक 3-बिट बाइनरी स्ट्रिंग में, तीन बाइनरी संख्याएं 011, 110, 111 हैं, जिनमें लगातार 1 हैं, और पांच संख्याएं हैं जिनमें लगातार 1 नहीं हैं। तो इस एल्गोरिदम को 3-बिट संख्याओं पर लागू करने के बाद, उत्तर 5 होगा।
यदि a[i] बाइनरी संख्याओं का समुच्चय है, जिनके बिट्स की संख्या i है, और जिनमें कोई लगातार 1 नहीं है, और b[i] बाइनरी संख्या का समुच्चय है, जहां बिट्स की संख्या i है, और जिनमें लगातार 1 हैं, तो पुनरावर्ती संबंध हैं:
a[i] := a[i - 1] + b[i - 1] b[i] := a[i - 1]
इनपुट और आउटपुट
इनपुट: यह एल्गोरिदम बाइनरी संख्या के लिए बिट्स की संख्या लेता है। मान लें इनपुट 4 है। आउटपुट: यह उन बाइनरी स्ट्रिंग्स की संख्या लौटाता है जिनमें लगातार 1 नहीं हैं। यहाँ परिणाम है: 8। (ऐसी 8 बाइनरी स्ट्रिंग्स हैं जिनमें लगातार 1 नहीं हैं)
एल्गोरिदम
countBinNums(n)
इनपुट: n बिट्स की संख्या है।
आउटपुट: गिनें कि कितनी संख्याएं मौजूद हैं जिनमें लगातार 1 नहीं हैं।
शुरू 0 से समाप्त होने वाली स्ट्रिंग्स और 1 से समाप्त होने वाली स्ट्रिंग्स की सूचियां परिभाषित करें endWithZero[0] := 1 endWithOne[0] := 1 i := 1 से n-1 तक, करें endWithZero[i] := endWithZero[i-1] + endWithOne[i-1] endWithOne[i] := endWithZero[i-1] किया endWithZero[n-1] + endWithOne[n-1] वापस करें अंत
उदाहरण
#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
