মনে করুন, আমাদের একটি পূর্ণসংখ্যা N আছে। আমাদের দৈর্ঘ্য N-এর সব সম্ভাব্য ভিন্ন বাইনারি স্ট্রিং যাতে অন্তত তিনটি ক্রমাগত ১ থাকে, তাদের সংখ্যা বের করতে হবে। তাই যদি n = 4 হয়, তবে সংখ্যাগুলো হবে 0111, 1110, 1111, তাই আউটপুট হবে 3।
এটি সমাধানের জন্য, আমরা ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করতে পারি। যেন DP(i, x) নির্দেশ করে দৈর্ঘ্য i-এর স্ট্রিং которых i+1 থেকে i+x পজিশনে xটি ক্রমাগত ১ থাকে। তখন রিকারেন্স রিলেশন হবে -
DP(i, x) = DP(i – 1, 0) + DP(i – 1, x + 1)।
রিকারেন্সটি এই তথ্যের ওপর ভিত্তি করে তৈরি, যে স্ট্রিং-এ i-তম পজিশনে ০ বা ১ থাকতে পারে।
- যদি i-তম ইনডেক্সে ০ থাকে, তবে (i-1)তম পজিশনে x = 0
- যদি i-তম ইনডেক্সে ১ থাকে, তবে (i-1)তম পজিশনে x = 1 + i-তম পজিশনের x-এর মান
উদাহরণ
#include <iostream>
using namespace std;
int n;
int numberCount(int i, int x, int table[][4]) {
if (i < 0)
return x == 3;
if (table[i][x] != -1)
return table[i][x];
table[i][x] = numberCount(i - 1, 0, table);
table[i][x] += numberCount(i - 1, x + 1, table);
return table[i][x];
}
int main() {
n = 4;
int table[n][4];
for (int i = 0; i < n; i++)
for (int j = 0; j < 4; j++)
table[i][j] = -1;
for (int i = 0; i < n; i++) {
table[i][3] = (1 << (i + 1));
}
cout << "The number of binary strings with at least 3 consecutive 1s: " << numberCount(n - 1, 0, table);
}
আউটপুট
The number of binary strings with at least 3 consecutive 1s: 3
