यहां हम एक दिलचस्प समस्या देखेंगे। मान लीजिए n का एक मान दिया गया है। हमें लंबाई n के सभी तार इस प्रकार ज्ञात करने हैं कि कोई क्रमागत 1 न हो। यदि n =2, तो संख्याएँ {00, 01, 10} हैं, तो आउटपुट 3 है।
हम इसे डायनामिक प्रोग्रामिंग का उपयोग करके हल कर सकते हैं। मान लीजिए कि हमारे पास 'ए' और 'बी' टेबल हैं। जहां arr[i] लंबाई के बाइनरी स्ट्रिंग्स की संख्या संग्रहीत कर रहा है, जहां कोई लगातार 1 मौजूद नहीं है, और 0 के साथ समाप्त होता है। इसी तरह, बी वही रखता है लेकिन संख्या 1 के साथ समाप्त होती है। हम 0 या 1 जोड़ सकते हैं जहां अंतिम एक है 0 है, लेकिन केवल 0 जोड़ें यदि अंतिम 1 है।
आइए इस विचार को प्राप्त करने के लिए एल्गोरिथम देखें।
एल्गोरिदम
noConsecutiveOnes(n) -
Begin define array a and b of size n a[0] := 1 b[0] := 1 for i in range 1 to n, do a[i] := a[i-1] + b[i - 1] b[i] := a[i - 1] done return a[n-1] + b[n-1] End
उदाहरण
#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