C/C++ প্রোগ্রামে সবটে সংলগ্ন ১ না থাকা বাইনারি স্ট্রিং গণনা

ভূমিকা

একটি দৈর্ঘ্য n দেওয়া থাকলে, কতগুলো বাইনারি স্ট্রিং সম্ভব যাতে কোনো দুটি ১ সংলগ্ন (consecutive) না থাকে। ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায়।

এলগরিদম

noConsecutiveOnes(n)
শুরু
  a[n], b[n] // a[i] = ০-এ শেষ হওয়া স্ট্রিং, b[i] = ১-এ শেষ হওয়া স্ট্রিং
  a[0]=1, b[0]=1
  i=1 থেকে n-1:
    a[i] = a[i-1] + b[i-1]  // ০ যোগ করলে দুটোটিই হয়
    b[i] = a[i-1]           // ১ যোগ করলে শুধু ০-এ শেষ হওয়া থেকে
  রিটার্ন a[n-1] + b[n-1]
শেষ

C++ প্রোগ্রাম উদাহরণ

#include 
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
    return 0;
}

আউটপুট

8