নির্দিষ্ট বিটের বাইনারি সংখ্যা যেগুলোতে কোনো পর egymানোর ১ নেই

এই সমস্যায় আমাদের এমন বাইনারি সংখ্যা খুঁজে বের করতে হবে যেগুলোতে কোনো পর egymানোর ১ নেই। ৩-বিট বাইনারি স্ট্রিংয়ের মধ্যে ০১১, ১১০, ১১১ — এগুলোতে পর egymানোর ১ আছে। বাকি ৫টি সংখ্যায় পর egymানোর ১ নেই। তাই ৩-বিটের জন্য উত্তর হবে ৫।

যদি a[i] হয় i-বিটের সেই বাইনারি সংখ্যাগুলোর সেট যেগুলোতে পর egymানোর ১ নেই, আর b[i] হয় i-বিটের সেট যেগুলোতে পর egymানোর ১ আছে, তবে রিকারেন্স রিলেশন হবে:

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

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

ইনপুট

এই অ্যালগরিদম বাইনারি সংখ্যার বিট সংখ্যা নেয়। ইনপুট ৪ হলে —

আউটপুট

যে বাইনারি স্ট্রিংগুলোতে পর egymানোর ১ নেই, তাদের সংখ্যা রিটার্ন করে। ৪-বিটের জন্য ফলাফল ৮।

অ্যালগরিদম

countBinNums(n)

ইনপুট: n (বিট সংখ্যা)
আউটপুট: পর egymানোর ১ নেই এমন বাইনারি স্ট্রিংয়ের সংখ্যা
শুরু
    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 consecutive 1's: " << countBinNums(n) << endl;
    return 0;
}

আউটপুট

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