什麼數學理論被用來解決這個問題？

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] 

我們怎麼positions關係嗎？我們通過人工觀察來完成，但我們應該能夠提出一個公式。因爲數字再次上升然後又回落，我想出一個計算值的好方法，就是使用距離中心的距離（在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; 
} 

Answer 2

看起來像這個解決方案使用的觀察，位置的x和y部分獨立和相同的速度改變。

速度相同意味着在k次移動後，每個座標將改變k次。獨立地表示可以在不知道y座標的情況下計算x座標的變化。

很難遵循實際計算，但它有這些步驟

• 移動到所有反射後2*s[i]
• k1 % (2*s[i])計算座標
• 正常化結果恢復正常板
擴展板的邊緣