数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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之间的数字。如果是，则更新计数并检查从0到length-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)，将计数更新为count = count + decode_digit_seq(str, length-2)
如果倒数第二个字符是2且最后一个字符<7，则最后两位数字将在20到26之间(T到Z)，将计数更新为count = count + 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
228 次浏览
