9

获取矩形平铺螺旋的第 n 个元素的算法是什么？

这里是n：

[ 20  ][ 21  ][ 22  ][ 23  ][ 24  ]
[ 19  ][  6  ][  7  ][  8  ][  9  ]
[ 18  ][  5  ][  0  ][  1  ][ 10  ]
[ 17  ][  4  ][  3  ][  2  ][ 11  ]
[ 16  ][ 15  ][ 14  ][ 13  ][ 12  ]

这里是对应的坐标n：

[-2,2 ][-1,2 ][ 0,2 ][ 1,2 ][ 2,2 ]
[-2,1 ][-1,1 ][ 0,1 ][ 1,1 ][ 2,1 ]
[-2,0 ][-1,0 ][ 0,0 ][ 1,0 ][ 2,0 ]
[-2,-1][-1,-1][ 0,-1][ 1,-1][ 2,-1]
[-2,-2][-1,-2][ 0,-2][ 1,-2][ 2,-2]

如果给定n，如何计算坐标？

4

6 回答 6

15

这是一个简短而甜蜜的答案，只使用伪代码中的简单数学。没有条件，也没有迭代。给定tileNum瓷砖编号：

intRoot=int(sqrt(tileNum));

x=(round(intRoot/2)*(-1^(intRoot+1)))+((-1^(intRoot+1))*(((intRoot*(intRoot+1))-tileNum)-abs((intRoot*(intRoot+1))-tileNum))/2);

y=(round(intRoot/2)*(-1^intRoot))+((-1^(intRoot+1))*(((intRoot*(intRoot+1))-tileNum)+abs((intRoot*(intRoot+1))-tileNum))/2);

这是一个在行动中看到它的小提琴。

于 2013-12-15T06:21:37.793 回答
5

这是 JavaScript 中的代码。它计算二维矩阵的位置，从中间的数字 1 (0, 0)

13  12  11  10  25
14   3   2   9  24
15   4   1   8  23
16   5   6   7  22
17  18  19  20  21

/**
 * Finds coordinates (position) of the number
 * 
 * @param {Number} n - number to find position/coordinates for
 * @return {Number[]} - x and y coordinates of the number
 */
function position(n) {
    const k = Math.ceil((Math.sqrt(n) - 1) / 2);
    let t = 2 * k + 1;
    let m = Math.pow(t, 2);

    t -= 1;

    if (n >= m - t) {
        return [k - (m - n), -k];
    }

    m -= t;

    if (n >= m - t) {
        return [-k, -k + (m - n)];
    }

    m -= t;

    if (n >= m - t) {
        return [-k + (m - n), k];
    }

    return [k, k - (m - n - t)];
}
于 2016-12-27T18:59:47.527 回答
2

首先，找出你想要的元素在哪个环（提示：直到你到达外环，你的螺旋是由嵌套的正方形组成的），然后它在（4 个）的哪一侧，然后你就离开了它的位置在那一边。

于 2012-04-10T19:00:34.547 回答
1

已经存在类似的问题......请参阅我的非循环版本。您可能需要交换和/或取反 X/Y 坐标，并将100's 更改为 's，0具体取决于您想要的方向和原点。

还有更多规范的循环版本。

于 2012-04-10T19:06:35.900 回答
1

由于没有人回答，有一个解决方案：

def square_spiral(total_steps):
    position = (0,0)
    direction = (1,0)
    turn_steps = [floor(((x+2)**2)/4) for x in range(n+2)]
    for step in range(total_steps):
        if (step in turn_steps):
            direction = (-direction[1],direction[0])
        position = tuple(a+b for a,b in zip(position,direction))
    return position

这模拟了通过所需路径的步行。您从位置 (0,0) 开始，向右走 1 步，向下走 1 步，向左走 3 步，向上走 3 步，依此类推，沿着螺旋。要对此进行编码，请注意我们正在改变数字 1、2、4、6、9、12、16、20 等步骤的方向。https://oeis.org/显示这是四分之一平方整数序列。所以我们所需要的只是一个循环，其中每次迭代模拟一个步骤，将方向添加到位置并在步数是序列的一部分时将其旋转 90º。

于 2012-04-10T22:50:47.947 回答
1

这是我在 javascript 中使用 8 的倒数和边编号的解决方案

复杂性：O(1) 无迭代循环

function spiral(n) {
    // given n an index in the squared spiral
    // p the sum of point in inner square
    // a the position on the current square
    // n = p + a

    var r = Math.floor((Math.sqrt(n + 1) - 1) / 2) + 1;

    // compute radius : inverse arithmetic sum of 8+16+24+...=
    var p = (8 * r * (r - 1)) / 2;
    // compute total point on radius -1 : arithmetic sum of 8+16+24+...

    en = r * 2;
    // points by edge

    var a = (1 + n - p) % (r * 8);
    // compute de position and shift it so the first is (-r,-r) but (-r+1,-r)
    // so square can connect

    var pos = [0, 0];
    switch (Math.floor(a / (r * 2))) {
        // find the face : 0 top, 1 right, 2, bottom, 3 left
        case 0:
            {
                pos[0] = a - r;
                pos[1] = -r;
            }
            break;
        case 1:
            {
                pos[0] = r;
                pos[1] = (a % en) - r;

            }
            break;
        case 2:
            {
                pos[0] = r - (a %en);
                pos[1] = r;
            }
            break;
        case 3:
            {
                pos[0] = -r;
                pos[1] = r - (a % en);
            }
            break;
    }
    console.log("n : ", n, " r : ", r, " p : ", p, " a : ", a, "  -->  ", pos);
    return pos;
}

演示：小提琴

于 2013-10-10T05:08:48.470 回答