알파벳으로 간단한 다중 암호화의 가능한 방법을 찾는 알고리즘

알파벳의 색인 번호로 문자를 대체하는 간단한 암호화 방법을 사용하는 경우 여러 가지 방법으로 암호를 해독 할 수 있습니다. ABOR은 121518이지만 121518은 AYEAH 또는 LAER 일 수도 있습니다.알파벳으로 간단한 다중 암호화의 가능한 방법을 찾는 알고리즘

글쎄, 주어진 숫자가 설명 된 방법 (예 : 1225에 5 - ABBE, AVE, ABY, LBE, LY)을 통해 메시지를 해독 할 수있는 방법을 계산하는 알고리즘이 필요합니다.

원하면 도와주세요.

출처

2010-02-12 ggg

암호화되지 않았습니다. 그것은 단지 인코딩입니다. – kennytm

숫자 1 ... 9의 접두사를 0으로 했으므로 'A'가 01에 해당합니까? 이렇게하면 모든 문자가 1 또는 2 자리가 아닌 한 쌍의 숫자로 표시되므로 쉽게 해독 할 수 있습니다. –

재귀 적으로 할 수 있습니다.

첫 번째 n 개의 숫자를 인코딩하는 총 수는 (마지막 숫자가 1 인 경우 첫 번째 n-1 자릿수를 인코딩하는 방법의 수입니다. < = d < = 9) + (인코딩 방법의 수 마지막 두 자릿수가 10이면= dd < = 26 인 첫 번째 n-2 자리).

지수 적 폭발을 방지하기 위해 결과를 캐시하거나 동적 프로그래밍을 사용하십시오. 이 기법은 피보나치 수를 계산하는 것과 매우 유사합니다. 여기

는, 파이썬에서 할 수있는 원리를 입증하는 방법은 다음과 같습니다

# s is of form [1-9][0-9]* 
s = '121518' 
a=1 # Cache of f(i - 2) 
b=1 # Cache of f(i - 1) 
for i in range(1, len(s)): 
    a, b = b, a * (10 <= int(s[i - 1: i + 1]) <= 26) + b * (s[i] != '0') 
print b

당신은 C++에서 비슷한 방법으로 그것을 할 수 있지만,이 숙제/학습 운동을 것 같다, 나는 희망 C++로 세부 사항을 해결하도록 남겨 두어도 괜찮습니다.

출처

2010-02-12 19:49:53

사실 이것은 동적 프로그래밍을 사용하여 런타임에 상당히 선형이어야합니다. –

실행 시간 *은 "상당히 선형"뿐만 아니라 * 선형입니다. :-) (길이를 재 계산하거나 s [i]를 찾는 것에 대해 각 반복에서 문자열을 가로 지르는 것처럼 바보 같은 짓을하지 않는다고 가정하십시오.) – ShreevatsaR

고마워요.하지만 정확히 당신이 무엇을하고 있는지 정확히 이해할 수 없습니다. 가장 긴 줄 - <= 작거나 등호입니까? b와 문장 (s [i]! = '0')의 곱셈은? – ggg

알파벳으로 간단한 다중 암호화의 가능한 방법을 찾는 알고리즘

답변

관련 문제