计算C ++中给定数字序列的可能解码
我们得到了一个代表数字序列的字符串。每个数字从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和length-1之间。检查最后两位数字的字符串部分是否使数字介于1和26之间。如果为true,则更新count并检查字符串的其余部分(介于0和length-2之间)。
我们将输入作为字符串str []。
函数decode_digit_seq(char * str,int length)获取字符串及其长度,并返回可能的str解码计数。
如果length为0。返回1。
如果length为1,则返回1。
如果最后一个字符不为零,则计数为decode_digit_seq(str,int length-1)
如果倒数第二个字符是1,则后两位数字将在10到19之间(从J到S),将count更新为count = count + encode_digit_seq(str,length-2)
如果倒数第二个字符是2并且最后一个字符<7,则后两位数将在20到26之间(从T到Z),更新计数为count = count + encode_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
以上是 计算C ++中给定数字序列的可能解码 的全部内容, 来源链接: utcz.com/z/321548.html