এই সমস্যায়, আমাদের কিছু বাইনারি সংখ্যা খুঁজে বের করতে হবে যার কোনো ধারাবাহিক 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]
ইনপুট এবং আউটপুট
Input: This algorithm takes number of bits for a binary number. Let the input is 4. Output: It returns the number of binary strings which have no consecutive 1’s. Here the result is: 8. (There are 8 binary strings which has no consecutive 1’s)
অ্যালগরিদম
countBinNums(n)
ইনপুট: n হল বিটের সংখ্যা।
আউটপুট - গণনা করুন কয়টি সংখ্যা উপস্থিত রয়েছে যার কোনো ধারাবাহিক 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 consecitive 1's: "<<countBinNums(n) << endl;
return 0;
} আউটপুট
Enter number of bits: 4 Number of binary numbers without consecitive 1's: 8
