숫자 시퀀스를 나타내는 문자열이 제공됩니다. 각 숫자는 영어 알파벳으로 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 )
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
재귀적 방법을 사용하여 이 작업을 수행합니다. 이 재귀 메서드에 문자열의 일부를 전달합니다.
true이면 마지막 숫자가 '0'이 아닌지 확인하고 0과 length-1 사이의 나머지 문자열을 확인합니다. 마지막 두 자리 문자열 부분이 1에서 26 사이의 숫자인지 확인합니다. true이면 개수를 업데이트하고 0과 length-2 사이의 나머지 문자열을 확인합니다.
-
문자열 str[]로 입력을 받습니다.
-
Decode_digit_seq(char *str, int length) 함수는 문자열과 그 길이를 가져와 str의 가능한 디코딩 횟수를 반환합니다.
-
길이가 0이면 1을 반환합니다.
-
길이가 1이면 1을 반환합니다.
-
마지막 단일 문자가 0이 아닌 경우 count는 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)
로 업데이트 카운트 -
이제 모든 사건이 접수됩니다.
-
결국 모든 재귀는 결과로 count를 반환합니다.
예시
#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