সি/সি++ প্রোগ্রামে কনসিকিউটিভ ১ ছাড়া বাইনারি স্ট্রিং গণনা করা

একটি বাইনারি নম্বর হলো এমন নম্বর যেটে শুধু ০ এবং ১ থাকে। প্রতিটি বাইনারি নম্বর একটি বাইনারি বিটের স্ট্রিম, এবং আমরা এটিকে বাইনারি স্ট্রিং হিসেবে বিবেচনা করি। এই স্ট্রিংয়ের জন্য, আমাদের N বিটের এমন বাইনারি স্ট্রিং গণনা করতে হবে যেগুলোতে কনসিকিউটিভ ১ নেই।

উদাহরণস্বরূপ, N = 5-এর জন্য যেসব বাইনারি স্ট্রিং কনস্ট্রেইন্ট পূরণ করে সেগুলো: 00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101

একটি পদ্ধতি হলো সব N-ডিজিট স্ট্রিং জেনারেট করা এবং কনস্ট্রেইন্ট পূরণকারী স্ট্রিংগুলো প্রিন্ট করা। কিন্তু কাজ করার দৃষ্টিকোণ থেকে এটি এতটা ইফিশিয়েন্ট নয়।

অন্য পদ্ধতি হলো রিকার্শন ব্যবহার করা। রিকার্শনের প্রতিটি পয়েন্টে, আংশিকভাবে ফর্মড নম্বরের সাথে ০ এবং ১ অ্যাপেন্ড করে এক কম ডিজিটের সাথে রিকার্শন করতে হবে। ট্রিকটি হলো, ১ অ্যাপেন্ড করে রিকার্শন করব শুধু তখনই যখন আংশিকভাবে ফর্মড নম্বরের লাস্ট ডিজিট ০ হয়। এভাবে আউটপুট স্ট্রিং-এ কখনো কনসিকিউটিভ ১ থাকবে না।

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; }