ধরুন, আমাদের একটি পূর্ণসংখ্যা N আছে, আমাদের N দৈর্ঘ্যের সম্ভাব্য সমস্ত স্বতন্ত্র বাইনারি স্ট্রিংগুলির সংখ্যা খুঁজে বের করতে হবে, যার অন্তত তিনটি পরপর 1s আছে। তাই যদি n =4 হয়, তাহলে সংখ্যাগুলো হবে 0111, 1110, 1111, সুতরাং আউটপুট হবে 3।
এটি সমাধান করার জন্য, আমরা ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করতে পারি। সুতরাং DP(i, x) i + 1 থেকে i + x অবস্থানে x ধারাবাহিক 1s সহ দৈর্ঘ্য i এর স্ট্রিংগুলির সংখ্যা নির্দেশ করে। তাহলে পুনরাবৃত্তি সম্পর্ক −
এর মত হবেDP(i, x) =DP(i – 1, 0) + DP(i – 1, x + 1)।
পুনরাবৃত্তিটি এই সত্যের উপর ভিত্তি করে যে স্ট্রিংটির i অবস্থানে 0 বা 1 থাকতে পারে।
- যদি ith সূচকে 0 থাকে, তাহলে x =0 এর (i – 1)তম অবস্থানের মান
- যদি ith সূচকে 1 থাকে, তাহলে x এর (i – 1) তম অবস্থানের মান =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
