একটি বাইনারি সংখ্যা হল এমন একটি সংখ্যা যাতে মাত্র দুটি থাকে অর্থাৎ একটি বা দুটি থাকে। প্রতিটি বাইনারি সংখ্যা বাইনারি বিটের একটি স্ট্রিম, এবং আমরা এটিকে একটি বাইনারি স্ট্রিং হিসাবে বিবেচনা করি। এই স্ট্রিংটির জন্য, আমাদেরকে বাইনারি স্ট্রিংয়ের সংখ্যা খুঁজে বের করতে হবে যাতে পরপর এন বিটগুলি থাকে না।
উদাহরণ স্বরূপ, N - 5 এর জন্য বাইনারি স্ট্রিংগুলি প্রদত্ত সীমাবদ্ধতাগুলিকে পূরণ করে 00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 1010>
একটি পদ্ধতি হল সমস্ত N-সংখ্যার স্ট্রিং তৈরি করা এবং শুধুমাত্র সেই স্ট্রিংগুলি প্রিন্ট করা যা প্রদত্ত সীমাবদ্ধতাগুলিকে সন্তুষ্ট করে। কিন্তু কাজ করার ক্ষেত্রে এই পদ্ধতিটি ততটা কার্যকর নয়।
অন্য পদ্ধতি হল পুনরাবৃত্তি ব্যবহার করা। পুনরাবৃত্তির প্রতিটি বিন্দুতে, আমরা আংশিকভাবে গঠিত সংখ্যার সাথে 0 এবং 1 যুক্ত করি এবং একটি কম সংখ্যার সাথে পুনরাবৃত্তি করি। এখানে কৌশলটি হল যে আমরা 1 যুক্ত করব এবং আংশিকভাবে গঠিত সংখ্যার শেষ সংখ্যা 0 হলেই পুনরাবৃত্তি করব, এইভাবে, আউটপুট স্ট্রিংয়ে আমাদের কখনই পরপর 1 থাকবে না।
Input: n = 5 Output: Number of 5-digit binary strings without any consecutive 1's are 13
উদাহরণ
#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
if (n == 0)
return 0;
if (n == 1) {
if (last_digit)
return 1;
else
return 2;
}
if (last_digit == 0)
return countStrings(n - 1, 0) + countStrings(n - 1, 1);
else
return countStrings(n - 1, 0);
}
int main() {
int n = 5;
cout << "Number of " << n << "-digit binary strings without any "
"consecutive 1's are " << countStrings(n, 0);
return 0;
} 