如何找到具有过度环绕的数字的两个方向上的最短路径？

Question

假设我必须从 0 到 10 中选择一个数字。

我选择的数字是 6。

我要选择的下一个数字是 0。

现在的规则是我必须继续将数字递增 1 或递减 1，该数字也可以环绕最后一个数字。

现在最重要的是找到最短的方向。

所以

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

在这种情况下，增量获胜。

好吧，我想出了这段代码（可能被破坏了）

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

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

现在而不是在两个方向上使用 while 循环.. 并找出哪个需要更少的移动..

有什么方法可以在没有 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