java - 用什么数学理论来解决这个问题？

Question

我报名参加了一些在线代码竞赛，其中一个问题是让您在特定的 k 圈后计算“板”的 x、y 范围内的点的位置。我能够通过 while 循环和 4 个条件语句进行 K 次迭代来解决问题，并且它在一定程度上起作用。我总是会在他们的一项“隐藏测试”中遇到时间限制。

让我来回答这个问题，我正在查看其他人的代码并注意到这个很酷的预测算法有效，而不是在 O(k*n) 中但在本质上是 O(2*n) (n = 语句数在循环中，k = 步骤数)。谁能解释一下他使用的是什么数学理论？

EDGAR_G6 的解决方案:

int[] chessBishopDream(int[] s, int[] xy, int[] dir, int k) {
int k1;
for (int i = 0; i< 2; i++) {        
    if (dir[i] > 0)
        k1 = k - 2*s[i] + xy[i];
    else 
        k1 = k - (xy[i] + 1);
    k1 = k1 % (2*s[i]);
    xy[i] = k1 % s[i];
    System.out.println(xy[i]);
    System.out.println(k1);
    if (k1 >= s[i])
        xy[i] = k1 - 2 * xy[i] - 1;
    xy[i] %= s[i];
}
return xy;
}

这里是问题:question on code fights

谢谢!

这是直接来自上面链接的问题:

在 ChessLand 中，有一个小而自豪的国际象棋主教，他有一个反复出现的梦想。在梦中，象发现自己在一个 n×m 的棋盘上，棋盘的每边都有镜子，它不是象而是一束光。这道光线只沿着对角线移动(主教做梦也想象不出任何其他类型的走法)，它从不停止，一旦到达棋盘的边缘或角落，它就会从棋盘上反射回来继续前进。

给定射线的初始位置和方向，找到它在 k 步后的位置，其中一步意味着从一个单元格移动到相邻单元格或从板的一角反射。

例子

For boardSize = [3, 7], initPosition = [1, 2],
initDirection = [-1, 1] and k = 13, the output should be
chessBishopDream(boardSize, initPosition, initDirection, k) = [0, 1].

这是主教的路径:

[1, 2] -> [0, 3] -(reflection from the top edge)-> [0, 4] -> 
[1, 5] -> [2, 6] -(reflection from the bottom right corner)-> [2, 6] ->
[1, 5] -> [0, 4] -(reflection from the top edge)-> [0, 3] ->
[1, 2] -> [2, 1] -(reflection from the bottom edge)-> [2, 0] -(reflection from the left edge)->
[1, 0] -> [0, 1]

Answer 1

我用 JavaScript 编写了一个解决方案，我将尝试描述我的方法。

首先，我“手动”遍历了一个维度上的位置序列。

例如，在宽度为 3 和高度为 1 的棋盘上，如果主教从方格 0 开始并朝正方向移动，其位置遵循以下模式:

0 1 2 2 1 0 0 1 2 2 1 0 0 1 ...

请注意，该模式在 6 之后重复。另请注意(自己尝试)，即使高度大于 1，此模式也成立。基本上，您一次只能考虑一个维度。

现在，对于我描述的起始条件，我可以告诉你任何 k 的最终位置，如下所示:

positions = [0, 1, 2, 2, 1, 0]
final = positions[k % 6]

我们是如何获得位置的？我们是通过人工观察来做的，但是我们应该可以得出一个公式。因为数字上升然后又下降，我认为计算该值的一个好方法是使用距中心的距离(在我们的 0 到 5 范围内为 2.5)。如果我们取 2.5 - n 的绝对值，我们会得到:

2.5, 1.5, 0.5, 0.5, 1.5, 2.5

从 2.5 中减去得到这个:

0, 1, 2, 2, 1, 0

这正是我们想要的。

一点点思考和尝试应该表明，同样的事情在负方向和任何起始位置都有效。对于尺寸 3，我们可以使用这个:

modulus = 6
middle = 2.5
newPosition = middle - abs(middle - (position + (k * direction)) % modulus)

泛化到任何尺寸:

modulus = size * 2
middle = (modulus - 1) / 2

至此，我们可以在常数时间内解决任意k的问题:

function chessBishopDream(boardSize, initPosition, initDirection, k) {
    // this array will hold the two coordinates of the final position
    var finalPosition = [];

    // first coordinate, second coordinate
    for (var i = 0; i < 2; i++) {
        var position = initPosition[i];
        var direction = initDirection[i];

        // simple addition, ignoring the edges
        var newPosition = position + direction * k;

        // period of the repeating pattern (e.g. 0 1 2 2 1 0 0 1 ...)
        var modulus = boardSize[i] * 2;

        // this is our "index" into the pattern
        newPosition %= modulus;

        // ensure a positive result of the modulo
        if (newPosition < 0) {
            newPosition += modulus;
        }

        var middle = (modulus - 1) / 2;

        finalPosition[i] = middle - Math.abs(middle - newPosition);
    }

    return finalPosition;
}