효율성 문제

내 알고리즘을보다 효율적으로 만들려고하고 있지만 어떤 이유로 그 논리가 올바르지 않으면 내 논리가 올바른지 알 수 있습니다. 일반적인 문제는 u에 'x'의 높이가 있고 'u'거리를 점프 할 수 있지만 높이를 이미 지우지 않은 경우 거리가 떨어지는 것입니다. 점프 수를 계산해야합니다.효율성 문제

초기 코드는

int k=u-d; 
if(x-u<=0){ 
    i++; 
} else { 
    int z=x/k; 
    if (x-((z-1)*k)-u <= 0) { 
     i+=z; 
    } else { 
     i=i+z+1; 
    } 
}

날 시도하고 문제를 명확하게 (어떤 이유로 어떤 경우에 실패, 나는이 생각하는 경우를 모르는) 제대로

while(x-u>0) { 
    x=x-u+d; 
    i++; 
} 
i++;

보다 효율적인 코드를 작동 높이 X의 벽을 가졌 으면 거리 U를 뛰어 올릴 수 있지만 점프 할 때마다 거리 D를 내리 웁니다. 그러면 높이 x = 4, u = 4, d = 1의 벽이 있는지 말할 수 있습니다. 그렇다면 처음으로 점프하면 벽을 비울 수 있기 때문에 점프하면됩니다. 이제 x = 6, u = 4, d = 1이라고 말할 수 있습니다. 그렇다면 처음으로 4도 뛰어 오르지 만 1도 떨어지면 3도 뛰어 오르고 다음 점프는 벽을 비우기 때문에 두 번 뛰어 넘어야합니다.

출처

2011-09-20 yahh

어떤 아이디어를 기반 : 단계의 수는 전체 숫자를해야한다고 불러 오기, 우리는 최종 결과를 얻을 네가 올린 글에 x, u, z, d, i 또는 k가 무엇인지 알 수 없습니다. 디버거를 통해 소풍이 당신에게 말해야합니다. – duffymo

whats k? 및 z? 그리고 다시 설명 할 수 있니? 왜 d가 필요한가요? – SD1990

내가 왜 떨어지는 점을 이해하는지 모르겠지만 어쨌든이 문제를 대수적으로 작성하고 상징적으로 풀어서 코드 조각으로 구현해야하는 것처럼 들린다. – Marcin

자, 보겠습니다. 마지막으로 점프는 x - u 이상의 높이에서 발생합니다. 나머지는 (u - d) 크기 단계로 커버해야하며, 해당 단계 수는 물론 (x - u)/(u - d)입니다.

i 번째 단계 후 높이가 i * (u - d) + u (및 아래로 떨어짐)입니다. 그래서, 대략. (x - u)/(u - d) 걸음, 높이는 x - u + u = x입니다. (ceil 주어진 수보다 작은 정수 이하를 반환하는 수학 함수입니다.)

if (u >= x) 
    return 1; 
if (u <= d) 
    throw "Impossible"; 
return ceil((x - u)/(u - d));

출처

2011-09-20 15:21:47 Vlad

효율성 문제

답변

관련 문제