এই সমস্যায়, আমাদের এমন বাইনারি সংখ্যা খুঁজে বের করতে হবে যাদের কোনোConsecutive 1's নেই। ৩-বিট বাইনারি স্ট্রিং-এ, তিনটি বাইনারি সংখ্যা 011, 110, 111 রয়েছে যাদেরConsecutive 1's আছে, এবং পাঁচটি সংখ্যা আছে যাদেরConsecutive 1's নেই। তাই ৩-বিট সংখ্যার জন্য এই অ্যালগরিদম লাগালে উত্তর হবে ৫।
যদি a[i] হলো বাইনারি সংখ্যার সেট যাদের বিট সংখ্যা i এবং কোনোConsecutive 1's নেই, এবং b[i] হলো বাইনারি সংখ্যার সেট যাদের বিট সংখ্যা i এবংConsecutive 1's আছে, তবে রিকারেন্স রিলেশনগুলো হবে:
a[i] := a[i - 1] + b[i - 1] b[i] := a[i - 1]
ইনপুট এবং আউটপুট
ইনপুট: এই অ্যালগরিদম বাইনারি সংখ্যার বিট সংখ্যা নেয়। ধরি ইনপুট ৪। আউটপুট: এটিConsecutive 1's না থাকা বাইনারি স্ট্রিংয়ের সংখ্যা ফেরত দেয়। এখানে ফলাফল: ৮। (৮টি বাইনারি স্ট্রিং আছে যাদেরConsecutive 1's নেই)
এলগরিদম
countBinNums(n)
ইনপুট: n হলো বিটের সংখ্যা।
আউটপুট:Consecutive 1's না থাকা সংখ্যাগুলোর গণনা।
শুরু
০ দিয়ে শেষ হওয়া স্ট্রিং এবং ১ দিয়ে শেষ হওয়া স্ট্রিং-এর লিস্ট সংজ্ঞায়িত করুন
endWithZero[0] := 1
endWithOne[0] := 1
i := 1 থেকে n-1 পর্যন্ত, করুন
endWithZero[i] := endWithZero[i-1] + endWithOne[i-1]
endWithOne[i] := endWithZero[i-1]
শেষ লুপ
return endWithZero[n-1] + endWithOne[n-1]
শেষ
উদাহরণ (C++ কোড)
#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
