ইনপুট হিসাবে আমাদের একটি সংখ্যা দেওয়া হয়। লক্ষ্য হল দৈর্ঘ্য সংখ্যার সম্ভাব্য স্ট্রিংগুলির সংখ্যা গণনা করা যাতে সমস্ত সংলগ্ন অক্ষরগুলির ascii মানের মধ্যে 1 হিসাবে পার্থক্য থাকে৷
যদি সংখ্যা 2 হয় তাহলে স্ট্রিংগুলি হবে "ab", "ba", "bc", "cb", ……..”yz", "zy"৷
আসুন উদাহরণ দিয়ে বুঝতে পারি
ইনপুট − সংখ্যা=3
আউটপুট − স্ট্রিংগুলির সংখ্যা যেখানে সন্নিহিত অক্ষরগুলির মধ্যে পার্থক্য রয়েছে একটি হল −98
ব্যাখ্যা − কিছু নমুনা স্ট্রিং হল:“abc”, “aba”, “cde”…..”xyx”, “zyz”, “xyz”।
ইনপুট − সংখ্যা=2
আউটপুট − স্ট্রিংগুলির সংখ্যা যেখানে সন্নিহিত অক্ষরগুলির মধ্যে পার্থক্য রয়েছে একটি হল −50
ব্যাখ্যা − কিছু নমুনা স্ট্রিং হল:“ab”, “ba”, “cd”…..”xy”, “zy”, “yz”।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
দৈর্ঘ্যের জন্য =2.
a=“ab”
দিয়ে শুরু হওয়া স্ট্রিংb=“ba”, “bc”
দিয়ে শুরু হওয়া স্ট্রিংc=“cd”, “cb”...............
দিয়ে শুরু হওয়া স্ট্রিংদৈর্ঘ্যের জন্য =n.
স্ট্রিং শুরু হচ্ছে a=পথের দৈর্ঘ্য n-1 দিয়ে শুরু হচ্ছে b
স্ট্রিং শুরু হয় b=পথের দৈর্ঘ্যের স্ট্রিং সংখ্যার n-1 a বা c দিয়ে শুরু হয়
c দিয়ে শুরু হওয়া স্ট্রিং =দৈর্ঘ্য n-1 এর স্ট্রিং সংখ্যার উপায় b বা d দিয়ে শুরু হয়
আমরা ডায়নামিক প্রোগ্রামিং ব্যবহার করে এটি সমাধান করব।
একটি অ্যারে অ্যারে নিন[num+1][27]। arr[i][j]-এর বর্ণমালা সংখ্যা j দিয়ে শুরু করে i দৈর্ঘ্যের বেশ কয়েকটি স্ট্রিং রয়েছে। সমস্ত arr[1][j] হবে 1 স্ট্রিং “a”, “b”...”z”।
arr[2 to num+1][0 to 25] এর জন্য বিশ্রাম, j=0 এর জন্য arr[i][j]=arr[i-1][j+1] সেট করুন। অন্যথায় arr[i][j] =arr[i-1][j-1] + arr[i-1][j+1];
ফলাফল হবে সংখ্যা-ম সারির সংখ্যার যোগফল।
-
ইনপুট পূর্ণসংখ্যা নিন
-
ফাংশন ডিফারেন্স_স্ট্রিংস(int num) num নেয় এবং স্ট্রিং এর সংখ্যা ফেরত দেয় যেখানে সন্নিহিত অক্ষরগুলির মধ্যে একটি পার্থক্য রয়েছে
-
0 হিসাবে প্রাথমিক গণনা নিন।
-
সমস্ত 0s সহ arr[num + 1][27] শুরু করুন।
-
সমস্ত 1 এর সাথে arr[1][0 থেকে 25] শুরু করুন।
-
ট্রাভার্স 2D অ্যারে অ্যারে[][][] সারি 2য় থেকে শেষ পর্যন্ত লুপের জন্য দুটি এবং সমস্ত 26টি বর্ণমালার জন্য 0 থেকে 25 কলাম ব্যবহার করে৷
-
j=0 এর জন্য, প্রারম্ভিক অক্ষর হল 'a'। বর্তমান গণনা হিসাবে সেট করুন arr[i][j] =arr[i - 1][j + 1];
-
অন্যথায় arr[i][j] =(arr[i - 1][j - 1] + arr[i - 1][j + 1])
-
এখন উপরের লুপগুলি শেষ হওয়ার পরে, শেষ সারিটি অতিক্রম করুন এবং গণনা করতে arr[num][ 0 থেকে 25] যোগ করুন।
-
ফলাফল হিসাবে রিটার্ন গণনা।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int difference_strings(int num){
long int count = 0;
long int arr[num + 1][27];
memset(arr, 0, sizeof(arr));
for (int i = 0; i <= 25; i++){
arr[1][i] = 1;
}
for (int i = 2; i <= num; i++){
for (int j = 0; j <= 25; j++){
if (j == 0){
arr[i][j] = arr[i - 1][j + 1];
}
else{
arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]);
}
}
}
for (int i = 0; i <= 25; i++){
count = (count + arr[num][i]);
}
return count;
}
int main(){
int num = 2;
cout<<"Count of strings where adjacent characters are of difference one are: "<<difference_strings(num);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of strings where adjacent characters are of difference one are: 50
