재귀를 건너 뛰는 중

Question

첫 번째 줄은 숫자, int x입니다. 다음 m 줄은 문자를 포함합니다. m 줄 후에, 숫자 int y를 읽는다.

목표는 각 행에서 1 문자의 재귀에서 soluiton 수 int y를 찾는 것입니다.

문제는 가능한 모든 암호를 거치지 않는 훨씬 빠른 해결책이 있음을 나타냅니다. 그게 내 질문이다. 어떻게 할 수 있습니까? 어떤 도움이라도 대단히 감사하겠습니다.

Answer 1

이것은 그리 복잡하지 않습니다. m 줄의 문자 수를 세어 볼 수 있습니다. 그런 다음 참조 된 행의 한 문자를 건너 뛸 경우 건너 뛸 수있는 솔루션의 수를 지정하는 모든 문자 행의 값을 계산합니다. 시각 : 당신이 "ABC"라인은 n + 1 번째 문자에 n 번째 편지에서 건너 뛸 경우, 당신은 모든 다음 줄의 길이의 제품을 말한다만큼 가능한 솔루션을 건너

abc -> 3 letters 
xy -> 2 letters 
dmnr -> 4 letters 

. 따라서 2 * 4 솔루션을 건너 뜁니다. ->8 solutions.

이 단계를 xy-> 건너 뛰기로 반복하십시오.

마지막 줄은 재귀 경로 자체이기 때문에 간략히 건너 뜁니다 (1 solution).

이제 특정 문자로 건너 뛰면 건너 뛰는 솔루션의 수를 알 수 있습니다. 마지막 것은 간단합니다. 1부터 시작하여 정확하게 r에 도달 할 때까지 각 행의 계산 된 값을 숫자에 더하십시오.

는 C++로 의미

int v = 1, r=10; 
int i1=0, i2=0, i3=0; 

while (v<=r-8) { 
    i1++; 
    v+=8; 
} 
while (v<=r-4) { 
    i2++; 
    v+=4; 
} 
while (v<=r-1) { 
    i3++; 
    v++; 
} 

지금 I1 당신이 "ABC"줄에서 사용할 필요가 문자의 인덱스, I2는 "dmnr에서"XY "에서 문자와 I3의 인덱스 " :) 그게 다야. 알고리즘은 i1 = 1, i2 = 0, i3 = 1 -> "b"+ "x"+ "m"으로 끝납니다.

이 정보가 도움이되기를 바랍니다. 그것은 재귀를 제거하지만 아무런 문제가 없습니다. ;)