เราได้รับสตริงที่แสดงถึงลำดับตัวเลข แต่ละหลักจะถูกถอดรหัสจาก 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 ถึงความยาว-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
