logo标签列表

从原点开始迭代离散二维网格上的外螺旋的算法

algorithmlanguage-agnosticrecursioniteration
42
例如，这是预期螺旋的形状（以及每个迭代步骤）。
          y
          |
          |
   16 15 14 13 12
   17  4  3  2 11
-- 18  5  0  1 10 --- x
   19  6  7  8  9
   20 21 22 23 24
          |
          |

这里的线是x轴和y轴。

在每次迭代中，算法会“返回”这些坐标（即点的坐标）：

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

我尝试过搜索，但不确定该搜索什么，而且我的尝试都没有结果。

除了创建/编码每层新的螺旋方式之类的混乱、不优雅和临时的方法外，我甚至不知道从哪里开始。

有人能帮我入门吗？

此外，是否有一种可以轻松切换顺时针和逆时针（方向）以及从哪个方向开始“旋转”螺旋的方法？（旋转）

还有没有办法以递归的方式实现这一点？

我的应用程序

我有一个填充有数据点的稀疏网格，并且我想将一个新数据点添加到该网格中，并使其“尽可能接近”给定的其他点。

为此，我将调用grid.find_closest_available_point_to(point)，它将遍历上面给出的螺旋，并返回第一个为空且可用的位置。

因此，首先它将检查point+[0,0]（只是为了完整起见）。然后它将检查point+[1,0]。然后它将检查point+[1,1]。然后是point+[0,1]，依此类推。并且返回第一个在网格中的位置为空（或未被数据点占用）的位置。

网格大小没有上限。

我已经完成了这个任务，但是无法理解您给出的输出示例。 - alcuadrado
听起来像是一个代码高尔夫问题... - Jeff Meatball Yang
@alcuadrado 首先，它返回原点。然后它返回点[1,0]。然后它逆时针“螺旋”并返回点[1,1]。我会尽力让它更清晰明了。 - Justin L.
这个问题与ProjectEuler的问题有关吗？ - Khaled Alshaya
@Arak 这不是这样的；我会在帖子中澄清我的目的。 - Justin L.
请查看https://dev59.com/a3RC5IYBdhLWcg3wJNgN。 - rahil627
13个回答
0

我曾经做过一个类似的训练练习，输出和螺旋方向有些不同，并且有一个额外的要求，即函数的空间复杂度必须为O(1)。

思考了一会儿后，我想到了一个主意：通过知道螺旋开始的位置和我正在计算值的位置，我可以通过减去所有完整的螺旋“圈”，然后只计算一个更简单的值来简化问题。

这是我在Ruby中实现该算法的代码：

def print_spiral(n)
  (0...n).each do |y|
    (0...n).each do |x|
      printf("%02d ", get_value(x, y, n))
    end
    print "\n"
  end
end


def distance_to_border(x, y, n)
  [x, y, n - 1 - x, n - 1 - y].min
end

def get_value(x, y, n)
  dist = distance_to_border(x, y, n)
  initial = n * n - 1

  (0...dist).each do |i|
    initial -= 2 * (n - 2 * i) + 2 * (n - 2 * i - 2)
  end        

  x -= dist
  y -= dist
  n -= dist * 2

  if y == 0 then
    initial - x # If we are in the upper row
  elsif y == n - 1 then
    initial - n - (n - 2) - ((n - 1) - x) # If we are in the lower row
  elsif x == n - 1 then
    initial - n - y + 1# If we are in the right column
  else
    initial - 2 * n - (n - 2) - ((n - 1) - y - 1) # If we are in the left column
  end
end

print_spiral 5

这不完全是你要求的东西，但我相信它会帮助你思考问题。

0

这是算法。它顺时针旋转，但稍加修改就可以逆时针旋转。我在不到一个小时的时间内完成了它。

// spiral_get_value(x,y);
sx = argument0;
sy = argument1;
a = max(sqrt(sqr(sx)),sqrt(sqr(sy)));
c = -b;
d = (b*2)+1;
us = (sy==c and sx !=c);
rs = (sx==b and sy !=c);
bs = (sy==b and sx !=b);
ls = (sx==c and sy !=b);
ra = rs*((b)*2);
ba = bs*((b)*4);
la = ls*((b)*6);
ax = (us*sx)+(bs*-sx);
ay = (rs*sy)+(ls*-sy);
add = ra+ba+la+ax+ay;
value = add+sqr(d-2)+b;
return(value);`

它将处理任何x / y值（无限）。

它是用GML（Game Maker Language）编写的，但实际逻辑在任何编程语言中都是正确的。

单行算法只有2个变量（sx和sy），用于x和y输入。我基本上扩展了括号，很多。这使得您可以更轻松地将其粘贴到记事本中，并将“sx”更改为您的x参数/变量名称，“sy”更改为您的y参数/变量名称。

`// spiral_get_value(x,y);

sx = argument0;  
sy = argument1;

value = ((((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*2))+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*4))+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*6))+((((sy==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sx !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sx)+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sx))+(((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sy)+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sy))+sqr(((max(sqrt(sqr(sx)),sqrt(sqr(sy)))*2)+1)-2)+max(sqrt(sqr(sx)),sqrt(sqr(sy)));

return(value);`

我知道回复已经晚了:D但我希望它能帮助未来的访问者。
您可以在个人资料中添加个人详细信息。头像已经在此帖子中显示了您的姓名。 - nhahtdh
0

我遇到过类似的问题，但我不想每次都循环整个螺旋以找到下一个新坐标。要求是您知道上一个坐标。

这是我根据阅读其他解决方案得出的：

function getNextCoord(coord) {

    // required info
    var x     = coord.x,
        y     = coord.y,
        level = Math.max(Math.abs(x), Math.abs(y));
        delta = {x:0, y:0};

    // calculate current direction (start up)
    if (-x === level)
        delta.y = 1;    // going up
    else if (y === level)
        delta.x = 1;    // going right
    else if (x === level)        
        delta.y = -1;    // going down
    else if (-y === level)
        delta.x = -1;    // going left

    // check if we need to turn down or left
    if (x > 0 && (x === y || x === -y)) {
        // change direction (clockwise)
        delta = {x: delta.y, 
                 y: -delta.x};
    }

    // move to next coordinate
    x += delta.x;
    y += delta.y;

    return {x: x,
            y: y};
}

coord = {x: 0, y: 0}
for (i = 0; i < 40; i++) {
    console.log('['+ coord.x +', ' + coord.y + ']');
    coord = getNextCoord(coord);  

}

仍然不确定它是否是最优雅的解决方案。也许一些优雅的数学方法可以消除一些if语句。一些限制包括需要进行一些修改才能改变螺旋方向，不能考虑非正方形螺旋，并且无法围绕固定坐标进行螺旋。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接