আমাদেরকে একটি স্ট্রিং দেওয়া হয়েছে যা একটি ডিজিট সিকোয়েন্সের প্রতিনিধিত্ব করে। প্রতিটি সংখ্যা ইংরেজি বর্ণমালা হিসাবে 1 থেকে 26 পর্যন্ত ডিকোড করা হয়। 1 হল 'A', 2 হল 'B' এবং 26 পর্যন্ত 'Z' হিসাবে। লক্ষ্য হল একটি প্রদত্ত অঙ্কের ক্রম থেকে সমস্ত সম্ভাব্য ডিকোডিংয়ের গণনা খুঁজে বের করা। যদি ক্রমটি '123' হয় তবে সম্ভাব্য ডিকোডিংগুলি হল 'ABC' (1-2-3), 'LC' (12-3), 'AW' (1-23)। গণনা 3।
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − str[]=”1532”
আউটপুট − প্রদত্ত ডিজিট সিকোয়েন্সের সম্ভাব্য ডিকোডিংয়ের সংখ্যা হল − 2
ব্যাখ্যা − সম্ভাব্য ডিকোডিং হল AECB - (1-5-3-2) এবং OCB (15-3-2)৷
ইনপুট − str[]=”216”
আউটপুট − একটি প্রদত্ত ডিজিট সিকোয়েন্সের সম্ভাব্য ডিকোডিংয়ের সংখ্যা হল −3
ব্যাখ্যা − সম্ভাব্য ডিকোডিংগুলি হল "BAF" ( 2-1-6 ), "UF" ( 21-6 ), "BP" ( 2-16 )
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
আমরা একটি পুনরাবৃত্ত পদ্ধতি ব্যবহার করে এটি করব। এই পুনরাবৃত্ত পদ্ধতিতে স্ট্রিংয়ের অংশগুলি পাস করুন।
শেষ সংখ্যাটি সত্য হলে ‘0’ না হলে, 0 এবং দৈর্ঘ্য-1-এর মধ্যে বাকি স্ট্রিংটি পরীক্ষা করুন। শেষ দুই অঙ্কের স্ট্রিং অংশটি 1 এবং 26-এর মধ্যে একটি সংখ্যা তৈরি করে কিনা তা পরীক্ষা করুন। সত্য হলে, গণনা আপডেট করুন এবং 0 এবং দৈর্ঘ্য-2-এর মধ্যে বাকি স্ট্রিংটি পরীক্ষা করুন।
-
আমরা স্ট্রিং str[] হিসাবে ইনপুট নিচ্ছি।
-
ফাংশন decode_digit_seq(char *str, int length) স্ট্রিং এবং এর দৈর্ঘ্য নেয় এবং str এর সম্ভাব্য ডিকোডিংয়ের গণনা প্রদান করে।
-
যদি দৈর্ঘ্য 0 হয়। রিটার্ন 1।
-
যদি দৈর্ঘ্য 1 হয়। রিটার্ন 1।
-
যদি শেষ একক অক্ষর অ-শূন্য হয়, গণনা হবে decode_digit_seq(str, int length-1)
-
যদি দ্বিতীয় শেষ অক্ষরটি 1 হয় তবে শেষ দুটি সংখ্যা 10 এবং 19 (J থেকে S) এর মধ্যে হবে, গণনা হিসাবে আপডেট করুন =গণনা + decode_digit_seq(str, length-2)
-
যদি দ্বিতীয় শেষ অক্ষর 2 হয় এবং শেষ অক্ষর হয় <7 তাহলে শেষ দুটি সংখ্যা 20 এবং 26 (T থেকে Z) এর মধ্যে হবে, গণনা হিসাবে আপডেট করুন =গণনা + decode_digit_seq(str, length-2)
-
এখন সব মামলা নেওয়া হয়েছে।
-
শেষ পর্যন্ত সমস্ত পুনরাবৃত্তির পরে ফলাফল হিসাবে গণনা করা হয়।
উদাহরণ
#include <iostream>
#include
using namespace std;
int decode_digit_seq(char *str, int length){
int count = 0;
if(length == 0){
return 1;
}
if(length == 1){
return 1;
}
if(str[0] == '0'){
return 0;
}
if(str[length-1] > '0'){
count = decode_digit_seq(str, length-1);
}
if(str[length-2] == '1'){
count = count + decode_digit_seq(str, length-2);
}
if(str[length-2] == '2' && str[length-1] < '7'){
count = count + decode_digit_seq(str, length-2);
}
return count;
}
int main(){
char str[] = "7651";
int length = strlen(str);
cout<<"Count of Possible Decodings of a given Digit Sequence are: "<< decode_digit_seq(str, length);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of Possible Decoding of a given Digit Sequence are: 1
