हमें एक अंक अनुक्रम का प्रतिनिधित्व करने वाली एक स्ट्रिंग दी गई है। प्रत्येक अंक को अंग्रेजी वर्णमाला के रूप में 1 से 26 तक डिकोड किया जाता है। 1 'ए' है, 2 'बी' है और इसी तरह 26 तक 'जेड' है। लक्ष्य किसी दिए गए अंक अनुक्रम में से सभी संभावित डिकोडिंग की गणना करना है। यदि अनुक्रम '123' है तो संभावित डिकोडिंग 'एबीसी' (1-2-3), 'एलसी' (12-3), 'एडब्ल्यू' (1-23) हैं। गिनती 3 है।
आइए उदाहरणों से समझते हैं।
इनपुट - str[]="1532"
आउटपुट − दिए गए अंकों के अनुक्रम के संभावित डिकोडिंग की संख्या है − 2
स्पष्टीकरण − संभावित डिकोडिंग AECB - (1-5-3-2) और OCB (15-3-2) हैं।
इनपुट - str[]="216"
आउटपुट − दिए गए अंकों के अनुक्रम के संभावित डिकोडिंग की संख्या है − 3
स्पष्टीकरण - संभावित डिकोडिंग "बीएएफ" (2-1-6), "यूएफ" (21-6), "बीपी" (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, लंबाई-2)
-
यदि दूसरा अंतिम वर्ण 2 है और अंतिम वर्ण <7 है तो अंतिम दो अंक 20 और 26 (T से Z) के बीच होंगे, गिनती को गिनती के रूप में अपडेट करें =गिनती + decode_digit_seq(str, लंबाई-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