Chúng tôi được cung cấp một chuỗi đại diện cho một chuỗi chữ số. Mỗi chữ số được giải mã từ 1 đến 26 dưới dạng Bảng chữ cái tiếng Anh. 1 là ‘A’, 2 là ‘B’ và cứ tiếp tục như vậy cho đến 26 là ‘Z’. Mục đích là để tìm số lượng tất cả các giải mã có thể có từ một dãy chữ số nhất định. Nếu chuỗi là ‘123’ thì các giải mã có thể là ‘ABC’ (1-2-3), ‘LC’ (12-3), ‘AW’ (1-23). Đếm là 3.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - str [] =”1532”
Đầu ra - Số lượng các giải mã có thể xảy ra của một dãy chữ số nhất định là - 2
Giải thích - Các giải mã có thể là AECB - (1-5-3-2) và OCB (15-3-2).
Đầu vào - str [] =”216”
Đầu ra - Số lượng các giải mã có thể xảy ra của một dãy chữ số nhất định là - 3
Giải thích - Các giải mã có thể là “BAF” (2-1-6), “UF” (21-6), “BP” (2-16)
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi sẽ làm điều này bằng cách sử dụng một phương pháp đệ quy. Chuyển các phần của chuỗi sang phương thức đệ quy này.
Kiểm tra xem chữ số cuối cùng có phải là ‘0’ không nếu đúng, hãy kiểm tra phần còn lại của chuỗi từ 0 đến độ dài-1. Kiểm tra xem phần chuỗi hai chữ số cuối cùng có tạo thành một số từ 1 đến 26. Nếu đúng, hãy cập nhật số lượng và kiểm tra phần còn lại của chuỗi từ 0 đến độ dài-2.
-
Chúng tôi đang lấy đầu vào là chuỗi str [].
-
Hàm decode_digit_seq (char * str, int length) lấy chuỗi và độ dài của nó và trả về số lượng các giải mã có thể có của str.
-
Nếu độ dài là 0. Trả về 1.
-
Nếu độ dài là 1. Trả về 1.
-
Nếu ký tự đơn cuối cùng khác 0, số lượng sẽ là decode_digit_seq (str, int length-1)
-
Nếu ký tự cuối cùng thứ hai là 1 thì hai chữ số cuối sẽ nằm trong khoảng từ 10 đến 19 (J đến S), cập nhật đếm là count =count + decode_digit_seq (str, length-2)
-
Nếu ký tự cuối cùng thứ hai là 2 và ký tự cuối cùng là <7 thì hai chữ số cuối cùng sẽ nằm trong khoảng từ 20 đến 26 (T đến Z), số lượng cập nhật là count =count + decode_digit_seq (str, length-2)
-
Bây giờ tất cả các trường hợp đã được thực hiện.
-
Cuối cùng sau tất cả các lần đệ quy trả về kết quả là kết quả.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of Possible Decoding of a given Digit Sequence are: 1