আমাদের N এবং K পূর্ণসংখ্যা দেওয়া হয়েছে। আমাদের দৈর্ঘ্য N এর বাইনারি স্ট্রিং রয়েছে, যার মধ্যে 0 এবং 1’সনলি রয়েছে। লক্ষ্য হল N দৈর্ঘ্যের এই ধরনের স্ট্রিংগুলির সংখ্যা খুঁজে বের করা যাতে K পরপর 1 আছে। অর্থাৎ, যদি N=3, এবং K=2, তাহলে সম্ভাব্য 3-সংখ্যার বাইনারি স্ট্রিংগুলি গণনা করুন যাতে 2টি পরপর 1 আছে।
উদাহরণ − 111, এখানে সংলগ্ন 1 দুবার দেখা যাচ্ছে (K বার)।
011 এবং 110 তে সংলগ্ন 1টি শুধুমাত্র একবার উপস্থিত হয়েছিল।
আমরা পূর্ববর্তী মানের ফলাফল সংরক্ষণ করে এটি সমাধান করব।
3D অ্যারে গণনা নেওয়া হচ্ছে[x][y][z]। যেখানে x হল N, y হল K এবং z হল স্ট্রিং এর শেষ সংখ্যা ( 0 বা 1 )
- N=1 এর জন্য, স্ট্রিং হবে "0" এবং "1"। সন্নিহিত 1’s=0 এর গণনা।
সুতরাং যেকোন K এর জন্য। যদি N=1, গণনা=0।
গণনা[1][K][0] =গণনা[1][K][1] =0।
- যখন শেষ অঙ্কটি 0 হয়, তখন সংলগ্ন 1-কে K হিসাবে গণনা করতে
K-এর সাথে N-1 দৈর্ঘ্যের সমস্ত সংখ্যা + শেষ 0 → নতুন দৈর্ঘ্য =N
যদি K সংলগ্ন 1 এর গণনা C হয় তবে শেষে 0 যোগ করলে সেই গণনা পরিবর্তন হবে না।
গণনা[N][K][0] =গণনা[N-1][K][0] + গণনা[N-1][K][1]
- যখন শেষ অঙ্ক 1 হয়, তখন পাশের 1-এর গণনা K হিসাবে করতে
দৈর্ঘ্যের N-1-এর সমস্ত সংখ্যা K-এর সাথে 0 দিয়ে শেষ হয় + শেষ 1 → নতুন দৈর্ঘ্য =N,
গণনা[N-1][K][0]
দৈর্ঘ্যের N-1-এর সমস্ত সংখ্যা 1 দিয়ে শেষ K-1 + শেষ 1 → নতুন দৈর্ঘ্য =N,
গণনা[N-1][K-1][1]
গণনা[N][K][1] =গণনা[N-1][K][0] + গণনা[N-1][K-1][1]
এমন মোট স্ট্রিং=গণনা[N][K][0] + গণনা[N][K][1]
ইনপুট
N=4, K=2
আউটপুট
Count of strings: 2
ব্যাখ্যা − 1110, 0111 হল দৈর্ঘ্য 4 এর একমাত্র স্ট্রিং যেখানে সংলগ্ন 1 শুধুমাত্র দুবার দেখা যায়।
1110- “11 10”, then “1 11 0” ( splitting to show which adjacent 1’s are counted ) 0111- “0 11 1”, then “01 11”. K=2, adjacent 1’s= 2 times
ইনপুট
N=3, K=1
আউটপুট
Count of strings: 2
ব্যাখ্যা − 110, 011. দৈর্ঘ্যের একমাত্র স্ট্রিং 3 যেখানে সংলগ্ন 1 একবার দেখা যায়৷
111 সংলগ্ন 1-এ দুবার প্রদর্শিত হয়।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
পূর্ণসংখ্যা N এবং K স্ট্রিংগুলির দৈর্ঘ্য এবং সংখ্যা সংরক্ষণ করে। কতবার সংলগ্ন 1 প্রতিটিতে উপস্থিত হয়।
-
ফাংশন স্ট্রিংকাউন্ট (int n, int k) পরামিতি হিসাবে n এবং k নেয় এবং K বার সংলগ্ন 1 এর সাথে স্ট্রিংগুলির গণনা প্রদান করে।
-
অ্যারে গণনা[i][j][0/1] ব্যবহার করা হয় i দৈর্ঘ্যের স্ট্রিংগুলির গণনাকে j সংলগ্ন 1 এর সাথে 0 বা 1 পাঠাতে।
-
প্রাথমিক অবস্থা হল গণনা[1][0][0] =1; গণনা[1][0][1] =1;
-
এখন 2 দৈর্ঘ্যের স্ট্রিং ( i=2) থেকে n দৈর্ঘ্য পর্যন্ত শুরু করুন। এই জাতীয় প্রতিটি স্ট্রিংয়ের জন্য 1 এর সংলগ্ন Ktimes এর গণনা পরীক্ষা করুন। j=0;j<=k, পূর্ববর্তী গণনা থেকে। বর্তমান গণনা[i][j][0] এবং গণনা[i][j][1] আপডেট করুন।
-
j-1>=0 হলে, সংলগ্ন 1-এর গণনা 1-এর চেয়ে বেশি হয়। তারপর 1-এর শেষ হওয়া স্ট্রিংগুলির সংখ্যা গণনা[i][j][1] + count[i - 1][j - 1][1] হিসাবে আপডেট করুন ];
-
শেষে গণনা [n][k][0] এবং গণনা [n][k][1] যোগ করুন। ফলস্বরূপ এটি সংরক্ষণ করুন৷
৷ - কাঙ্খিত গণনা হিসাবে ফলাফল ফেরত দিন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
//count of strings with length=n and adajcent 1's=k
int count[n + 1][k + 1][2]={0};
//count[n][k][0] -- strings with length=n and adajcent 1's=k last character is 0
//count[n][k][1] -- strings with length=n and adajcent 1's=k last character is 1
// If n = 1 and k = 0.
count[1][0][0] = 1;
count[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
// number of adjacent 1's can not exceed i-1
for (int j = 0; j <= k; j++) {
count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
count[i][j][1] = count[i - 1][j][0];
if (j - 1 >= 0)
count[i][j][1] =count[i][j][1] + count[i - 1][j - 1][1];
}
}
int result=count[n][k][0]+count[n][k][1];
return result;
}
int main(){
int N = 6, K = 3;
cout <<"Strings of length 6 and 3 adjacent 1's in each :"<< stringcount(N,K);
return 0;
} আউটপুট
Strings of length 6 and 3 adjacent 1's in each :7
