এই সমস্যায়, আমাদের কিছু বাইনারি সংখ্যা খুঁজে বের করতে হবে যার কোনো ধারাবাহিক 1s নেই। একটি 3-বিট বাইনারি স্ট্রিং-এ, তিনটি বাইনারি সংখ্যা রয়েছে 011, 110, 111, যাদের পরপর 1s আছে এবং পাঁচটি সংখ্যা আছে যার কোনো ধারাবাহিক 1s নেই। তাই 3-বিট সংখ্যার জন্য এই অ্যালগরিদম প্রয়োগ করার পরে, উত্তর হবে 5।
যদি a[i] বাইনারি সংখ্যার সেট হয়, যার বিটের সংখ্যা i, এবং কোনো পরপর 1s থাকে না, এবং b[i] হল বাইনারি সংখ্যার সেট, যেখানে বিটের সংখ্যা i এবং পরপর 1s থাকে, তারপর −
এর মতো পুনরাবৃত্তি সম্পর্ক রয়েছেa[i] := a[i - 1] + b[i - 1]
b[i] := a[i - 1]
ইনপুট
এই অ্যালগরিদমটি বাইনারি সংখ্যার জন্য বিট সংখ্যা নেয়। ইনপুট 4 হয়.
আউটপুট
এটি বাইনারি স্ট্রিংগুলির সংখ্যা প্রদান করে যার কোনো ধারাবাহিক 1 নেই।
এখানে ফলাফল হল − 8। (8টি বাইনারি স্ট্রিং আছে যার কোনো ধারাবাহিক 1 নেই)
অ্যালগরিদম
countBinNums(n)
Input: n is the number of bits. Output: Count how many numbers are present which have no consecutive 1. Begin define lists with strings ending with 0 and ending with 1 endWithZero[0] := 1 endWithOne[0] := 1 for i := 1 to n-1, do endWithZero[i] := endWithZero[i-1] + endWithOne[i-1] endWithOne[i] := endWithZero[i-1] done return endWithZero[n-1] + endWithOne[n-1] End
উদাহরণ
#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
