알파벳으로 메시지 인코딩
실력을 향상시키기 위해 아래 문제를 해결하려고 노력하고 있습니다. 누군가가 내 코드를 더 나은 방식으로 개선하면 감사하겠습니다.
매핑 a = 1, b = 2, ... z = 26이고 인코딩 된 메시지가 주어지면 디코딩 할 수있는 방법의 수를 계산합니다. 예를 들어 '111'메시지는 'aaa', 'ka'및 'ak'로 디코딩 될 수 있으므로 3을 제공합니다. 메시지를 해독 할 수 있다고 가정 할 수 있습니다. 예를 들어 '001'은 허용되지 않습니다.
#include <stdio.h>
#include <stdlib.h>
#define MIN_ALPH 1
#define MAX_ALPH 26
//return number of possible encode methods
int encode(unsigned int num)
{
int count=0;
unsigned int ddigit;
//encode by 2 digits
for(int i=10; i<=num; i*=10)
{
ddigit = (num % (i*10)) / (i/10);
if (ddigit >= MIN_ALPH && ddigit <= MAX_ALPH)
count++;
}
//extra count for the single digit encoding since all digits are non-zero
return ++count;
}
int main(void)
{
/*Given the mapping a = 1, b = 2, ... z = 26, and an encoded message,
count the number of ways it can be decoded.
For example, the message '111' would give 3,
since it could be decoded as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable.
For example, '001' is not allowed.*/
printf( "result: %d\n", encode(512));
printf( "result: %d\n", encode(542));
printf( "result: %d\n", encode(112));
}
답변
내가 다시 알파벳 문자 자리에서가는 동작을 부를 것이다 - 용어는 약간의 실수입니다 디코딩 인코딩보다는를 - 우리의 기능 중 그 중 정말되지 않습니다 : 그것의 계산 . (나는 당신이 영어 원어민이 아니라고 생각하므로이 비판을 너무 거칠게 받아들이지 마십시오!).
인터페이스는 놀랍습니다. 정수 유형을 허용하면 입력의 최대 길이가 크게 제한되고 결과로 부호없는 유형을 반환 할 수 있습니다.
unsigned int count_decodings(const char *input);
힌트로 빼서 문자를 숫자로 변환하는 것이 안전합니다 '0'(C는 호스트 환경의 문자 코딩에 관계없이 숫자 0..9에 연속 인코딩이 있음을 보장합니다).
알고리즘이 잘못된 결과를 생성 합니다 .
이 주석은 정당화되지 않습니다.
//extra count for the single digit encoding since all digits are non-zero
return ++count;
예를 들어, - 일부 자리는 참으로 제로 할 수 10및 201각 정확히 하나의 방법을 디코딩 할 수있다. 그것은 당신이 할 수 있고해야 할 몇 가지 추가 테스트를 제안해야합니다.
몇 가지 테스트가있어서 좋습니다 main(). 나는 더 나아가 테스트를 자체 검사 하도록 할 것입니다 . 단순히 결과를 인쇄하는 대신 예상 값과 비교하고 EXIT_SUCCESS모든 테스트가 통과 한 경우에만 반환 해야합니다. 이와 같은 단위 테스트를 지원하는 데 사용할 수있는 여러 라이브러리가 있거나 아주 간단하게 할 수 있습니다.
int failures = 0;
failures += count_decodings("10") != 1;
failures += count_decodings("11") != 2;
// more tests here
어떤 테스트가 실패했는지, 예상 결과와 실제 결과가 무엇인지는 알 수 없습니다. 여기에서 도움이되는 매크로를 만들 수 있습니다 (단위 테스트 프레임 워크가 제공하는 것입니다).
메시지에는 11111113 가지 조합이 있습니다.
......aaaaaa
_.... kaaaa
._... akaaa
.._.. aakaa
..._. aaaka
...._ aaaak
__.. kkaa
_._. kaka
_.._ kaak
.__. akka
._._ akak
..__ aakk
___ kkk
처음에 "3"이 있으면 kkk, kaak, kaka, kkaa 및 kaaaa를 잃습니다. 나는 당신이 조합 최대 값에서 시작하여 얼마나 많은 것을 배제 할 수 있는지 확인해야한다고 생각합니다. 그러나 이것은 매우 사소하지 않을 것입니다. 어디에서 왔습니까?
이:
99991999919999199991999919
"ai"또는 "s"에 대한 다섯 가지 선택을 결합하는 방법에 따라 여러 가지 방법으로 읽을 수 있습니다.
프로그램은 "111111"에 대해 "6"만 인쇄합니다. "aaaaaa"에서 "aaaak"(위)까지만 계산됩니다.