在螺旋中循环

Question

在螺旋中循环一位朋友需要一种算法，可以让他遍历NxM矩阵的元素(N和M是奇数)。我想出了一个解决方案，但我想看看我的同伴们是否能想出一个更好的解决方案。我把我的解决方案作为这个问题的答案。示例输出：对于3x3矩阵，输出应该是：(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)此外，算法应该支持非平方矩阵，因此，例如，对于5x3矩阵，输出应该是：(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, 1) (-2, 0) (-2, -1)

Answer 1

下面是我的解决方案(在Python中)：

def spiral(X, Y):
    x = y = 0
    dx = 0
    dy = -1
    for i in range(max(X, Y)**2):
        if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2):
            print (x, y)
            # DO STUFF...
        if x == y or (x < 0 and x == -y) or (x > 0 and x == 1-y):
            dx, dy = -dy, dx
        x, y = x+dx, y+dy

Answer 2

有人吗？从python快速翻译，张贴完整性

void Spiral( int X, int Y){
    int x,y,dx,dy;
    x = y = dx =0;
    dy = -1;
    int t = std::max(X,Y);
    int maxI = t*t;
    for(int i =0; i < maxI; i++){
        if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)){
            // DO STUFF...
        }
        if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))){
            t = dx;
            dx = -dy;
            dy = t;
        }
        x += dx;
        y += dy;
    }}

Answer 3

let x = 0
let y = 0
let d = 1
let m = 1

while true
  while 2 * x * d < m
    print(x, y)
    x = x + d
  while 2 * y * d < m
    print(x, y)
    y = y + d
  d = -1 * d
  m = m + 1

对于这个问题，有很多用不同的编程语言编写的解决方案，但是它们似乎都源于相同的复杂方法。我将考虑一个更普遍的计算螺旋的问题，它可以用归纳简洁地表达出来。

大小写：从(0，0)开始，向前移动1平方，左转，向前移动1平方，左转。归纳步骤：向前移动n+1平方，左转，向前移动n+1平方，左转。

表达这一问题的数学优雅有力地表明，应该有一个简单的算法来计算解决方案。请记住，我选择的不是用特定的编程语言实现算法，而是将其作为伪代码来实现。

首先，我将考虑一种算法，它使用4对while循环来计算螺旋的2次迭代。每对的结构是相似的，但其本身是不同的。这在一开始可能看起来很疯狂(有些循环只执行一次)，但我将逐步进行转换，直到我们到达4对相同的循环，因此可以用放置在另一个循环中的单个循环替换。这将为我们提供一个不使用任何条件计算n次迭代的通用解决方案。

let x = 0
let y = 0

//RIGHT, UP
while x < 1
  print(x, y)
  x = x + 1
while y < 1
  print(x, y)
  y = y + 1

//LEFT, LEFT, DOWN, DOWN
while x > -1
  print(x, y)
  x = x - 1
while y > -1
  print(x, y)
  y = y - 1

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x < 2
  print(x, y)
  x = x + 1
while y < 2
  print(x, y)
  y = y + 1

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x > -2
  print(x, y)
  x = x - 1
while y > -2
  print(x, y)
  y = y - 1

我们将进行的第一个转换是为方向引入一个新变量d，它包含值+1或-1。方向在每对回路之后切换。由于我们在所有点都知道d的值，所以我们可以用它把每个不等式的每一面相乘，相应地调整不等式的方向，并将d的任何乘积简化为另一个常数。这就留给我们以下几点。

let x = 0
let y = 0
let d = 1

//RIGHT, UP
while x * d < 1
  print(x, y)
  x = x + d
while y * d < 1
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, DOWN, DOWN
while x * d < 1
  print(x, y)
  x = x + d
while y * d < 1
  print(x, y)
  y = y + d
d = -1 * d

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < 2
  print(x, y)
  x = x + d
while y * d < 2
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < 2
  print(x, y)
  x = x + d
while y * d < 2
  print(x, y)
  y = y + d

现在我们注意到x*d和rhs都是整数，所以我们可以从rhs中减去0到1之间的任何实值，而不影响不等式的结果。为了建立更多的模式，我们选择从每对WITH循环的不等式中减去0.5。

let x = 0
let y = 0
let d = 1

//RIGHT, UP
while x * d < 0.5
  print(x, y)
  x = x + d
while y * d < 0.5
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, DOWN, DOWN
while x * d < 1
  print(x, y)
  x = x + d
while y * d < 1
  print(x, y)
  y = y + d
d = -1 * d

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < 1.5
  print(x, y)
  x = x + d
while y * d < 1.5
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < 2
  print(x, y)
  x = x + d
while y * d < 2
  print(x, y)
  y = y + d

现在，我们可以引入另一个变量m，用于我们在每一对while循环上采取的步骤数。

let x = 0
let y = 0
let d = 1
let m = 0.5

//RIGHT, UP
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d
d = -1 * d
m = m + 0.5

//LEFT, LEFT, DOWN, DOWN
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d
d = -1 * d
m = m + 0.5

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d
d = -1 * d
m = m + 0.5

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d

最后，我们发现每对WITH循环的结构是相同的，可以简化为放置在另一个循环内的一个循环。另外，为了避免使用实数，我将m的初始值乘以m；值m被增加，并且每个不等式的两边都乘以2。

这将导致答案开头所示的解决方案。