랩핑 넘는 숫자의 양방향에서 최단 경로를 찾는 방법은 무엇입니까?

Question

0-10에서 숫자를 선택해야한다고 가정 해 봅니다. 내가 선택하고 싶은 다음 숫자는 0

지금 규칙은 내가 1 수를 증가 시키거나 1을 감소시키는 유지해야 있습니다 6.

입니다

내가 선택할 수는있다, 수 마지막 숫자를 둘러 쌀 수도 있습니다.

이제 가장 중요한 것은 가장 짧은 방향을 찾는 것입니다. 이 경우

그래서

6-5-4-3-2-1-0 = 7 moves. 
6-7-8-9-10-0 = 6 moves. 

그래서 증가 승리.

이 잘 나는

어떤 방법으로 .. 대신 .. 양방향으로 while 루프를 사용하여 적은 이동 걸립니다 알아내는 이제 (아마도 깨진)이 코드

int movesInc = 1; 
int movesDec = 1; 
int curNumber = 6; 
int nextNumber = 0; 
while((curNumber-- % 11) != nextNumber) 
    movesDec++; 

while((curNumber++ % 11) != nextNumber) 
    movesInc++; 

함께했다 while 루프없이 이것을 할 수 있습니까? 아마 수학 방정식의 일종일까요?

Answer 1

귀하의 코드는 두 가지 이유로 제대로 사실 일을하지 않습니다 : - 각 숫자 사이에 당신이 계산보다 적은 한 단계 당신을 떠나, 한 단계

대신 모듈 (11)을 작동한다 10의 (나는 당신이 지금 나의 이전의 코멘트 당 이것을 고쳤다는 것을 안다).

Java 및 C++의 % 연산자는 사용자가 생각하는대로 표지판을 처리하지 않습니다.

이것은 잘 작동하지 않지만 루프가 필요하지 않습니다.

6시에 테스트되었고 0으로 끝납니다. 일반적으로 작동 할 것으로 기대됩니다. 다른 범위의 경우 결과가 부정적 일 때 추가 된 숫자를 변경해야합니다.

int curNumber = 6; 
    int nextNumber = 0; 
    int movesInc = (nextNumber - curNumber) + 1 
        + ((nextNumber > curNumber)? 0: 11); 
    int movesDec = (curNumber - nextNumber) + 1 
        + ((nextNumber < curNumber)? 0: 11); 

+ 1은 두 종점을 모두 계산하기 때문입니다. 세 번째 표현식은 0을 처리하는 것입니다.

Answer 2

int curNumber; 
int nextNumber; 
//calculate the modulo size by the highest number 
int module = 10 + 1; 
//calculate the direct distance to the nextNumber 
int directDist = nextNumber - curNumber; 

int nextNumberWrapped; 
//calculate the wrapped distance, deciding the direction which wraps 
if(directDist < 0) 
    //wrapping in positive direction: 10 -> 0 
    nextNumberWrapped = nextNumber + module; 
else 
    //wrapping in negative direction 0 -> 10 
    nextNumberWrapped = nextNumber - module; 
//calculating the wrapped distance 
int wrappedDist = nextNumberWrapped - curNumber; 
//assume the directDist to be shortest 
int shortestDist = directDist; 
//proof wrong if neccessary (compare the distances absolute values) 
if(abs(wrappedDist) < abs(directDist)) 
    //save the signed distance 
    shortestDist = wrappedDist; 

shortestDist의 절대 값은 가장 짧은 거리의 길이를 나타내며 기호는 사용자에게 방향을 제공합니다. 그래서 부호가 음수이면 감소해야하고 양수이면 부호를 줄여서 최단 거리로 이동해야합니다.

http://ideone.com/0yCDw

또한 귀하의 예제는 잘못된 것 같다.

6-5-4-3-2-1-0 
^^^^^^
1 2 3 4 5 6 -> 6 moves 
6-7-8-9-10-0 
^^^^^ 
1 2 3 4 5 -> 5 moves