資料結構
網路
關係資料庫管理系統(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 次瀏覽
