在螺旋中循环

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&nbsp;spiral(X,&nbsp;Y): &nbsp;&nbsp;&nbsp;&nbsp;x&nbsp;=&nbsp;y&nbsp;=&nbsp;0 &nbsp;&nbsp;&nbsp;&nbsp;dx&nbsp;=&nbsp;0 &nbsp;&nbsp;&nbsp;&nbsp;dy&nbsp;=&nbsp;-1 &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(max(X,&nbsp;Y)**2): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(-X/2&nbsp;<&nbsp;x&nbsp;<=&nbsp;X/2)&nbsp;and&nbsp;(-Y/2&nbsp;<&nbsp;y&nbsp;<=&nbsp;Y/2): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print&nbsp;(x,&nbsp;y) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;DO&nbsp;STUFF... &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;x&nbsp;==&nbsp;y&nbsp;or&nbsp;(x&nbsp;<&nbsp;0&nbsp;and&nbsp;x&nbsp;==&nbsp;-y)&nbsp;or&nbsp;(x&nbsp;>&nbsp;0&nbsp;and&nbsp;x&nbsp;==&nbsp;1-y): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dx,&nbsp;dy&nbsp;=&nbsp;-dy,&nbsp;dx &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x,&nbsp;y&nbsp;=&nbsp;x+dx,&nbsp;y+dy

Answer 2

有人吗？从python快速翻译，张贴完整性void&nbsp;Spiral(&nbsp;int&nbsp;X,&nbsp;int&nbsp;Y){ &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;x,y,dx,dy; &nbsp;&nbsp;&nbsp;&nbsp;x&nbsp;=&nbsp;y&nbsp;=&nbsp;dx&nbsp;=0; &nbsp;&nbsp;&nbsp;&nbsp;dy&nbsp;=&nbsp;-1; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;t&nbsp;=&nbsp;std::max(X,Y); &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;maxI&nbsp;=&nbsp;t*t; &nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=0;&nbsp;i&nbsp;<&nbsp;maxI;&nbsp;i++){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;((-X/2&nbsp;<=&nbsp;x)&nbsp;&&&nbsp;(x&nbsp;<=&nbsp;X/2)&nbsp;&&&nbsp;(-Y/2&nbsp;<=&nbsp;y)&nbsp;&&&nbsp;(y&nbsp;<=&nbsp;Y/2)){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;DO&nbsp;STUFF... &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(&nbsp;(x&nbsp;==&nbsp;y)&nbsp;||&nbsp;((x&nbsp;<&nbsp;0)&nbsp;&&&nbsp;(x&nbsp;==&nbsp;-y))&nbsp;||&nbsp;((x&nbsp;>&nbsp;0)&nbsp;&&&nbsp;(x&nbsp;==&nbsp;1-y))){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t&nbsp;=&nbsp;dx; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dx&nbsp;=&nbsp;-dy; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dy&nbsp;=&nbsp;t; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x&nbsp;+=&nbsp;dx; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;y&nbsp;+=&nbsp;dy; &nbsp;&nbsp;&nbsp;&nbsp;}}

Answer 3

let&nbsp;x&nbsp;=&nbsp;0 let&nbsp;y&nbsp;=&nbsp;0 let&nbsp;d&nbsp;=&nbsp;1 let&nbsp;m&nbsp;=&nbsp;1 while&nbsp;true &nbsp;&nbsp;while&nbsp;2&nbsp;*&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;&nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;&nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d &nbsp;&nbsp;while&nbsp;2&nbsp;*&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;&nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;&nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d &nbsp;&nbsp;d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d &nbsp;&nbsp;m&nbsp;=&nbsp;m&nbsp;+&nbsp;1对于这个问题，有很多用不同的编程语言编写的解决方案，但是它们似乎都源于相同的复杂方法。我将考虑一个更普遍的计算螺旋的问题，它可以用归纳简洁地表达出来。大小写：从(0，0)开始，向前移动1平方，左转，向前移动1平方，左转。归纳步骤：向前移动n+1平方，左转，向前移动n+1平方，左转。表达这一问题的数学优雅有力地表明，应该有一个简单的算法来计算解决方案。请记住，我选择的不是用特定的编程语言实现算法，而是将其作为伪代码来实现。首先，我将考虑一种算法，它使用4对while循环来计算螺旋的2次迭代。每对的结构是相似的，但其本身是不同的。这在一开始可能看起来很疯狂(有些循环只执行一次)，但我将逐步进行转换，直到我们到达4对相同的循环，因此可以用放置在另一个循环中的单个循环替换。这将为我们提供一个不使用任何条件计算n次迭代的通用解决方案。let&nbsp;x&nbsp;=&nbsp;0 let&nbsp;y&nbsp;=&nbsp;0 //RIGHT,&nbsp;UP while&nbsp;x&nbsp;<&nbsp;1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;1 while&nbsp;y&nbsp;<&nbsp;1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;1 //LEFT,&nbsp;LEFT,&nbsp;DOWN,&nbsp;DOWN while&nbsp;x&nbsp;>&nbsp;-1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;-&nbsp;1 while&nbsp;y&nbsp;>&nbsp;-1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;-&nbsp;1 //RIGHT,&nbsp;RIGHT,&nbsp;RIGHT,&nbsp;UP,&nbsp;UP,&nbsp;UP while&nbsp;x&nbsp;<&nbsp;2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;1 while&nbsp;y&nbsp;<&nbsp;2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;1 //LEFT,&nbsp;LEFT,&nbsp;LEFT,&nbsp;LEFT,&nbsp;DOWN,&nbsp;DOWN,&nbsp;DOWN,&nbsp;DOWN while&nbsp;x&nbsp;>&nbsp;-2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;-&nbsp;1 while&nbsp;y&nbsp;>&nbsp;-2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;-&nbsp;1我们将进行的第一个转换是为方向引入一个新变量d，它包含值+1或-1。方向在每对回路之后切换。由于我们在所有点都知道d的值，所以我们可以用它把每个不等式的每一面相乘，相应地调整不等式的方向，并将d的任何乘积简化为另一个常数。这就留给我们以下几点。let&nbsp;x&nbsp;=&nbsp;0 let&nbsp;y&nbsp;=&nbsp;0 let&nbsp;d&nbsp;=&nbsp;1 //RIGHT,&nbsp;UP while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d //LEFT,&nbsp;LEFT,&nbsp;DOWN,&nbsp;DOWN while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d //RIGHT,&nbsp;RIGHT,&nbsp;RIGHT,&nbsp;UP,&nbsp;UP,&nbsp;UP while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d //LEFT,&nbsp;LEFT,&nbsp;LEFT,&nbsp;LEFT,&nbsp;DOWN,&nbsp;DOWN,&nbsp;DOWN,&nbsp;DOWN while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d现在我们注意到x*d和rhs都是整数，所以我们可以从rhs中减去0到1之间的任何实值，而不影响不等式的结果。为了建立更多的模式，我们选择从每对WITH循环的不等式中减去0.5。let&nbsp;x&nbsp;=&nbsp;0 let&nbsp;y&nbsp;=&nbsp;0 let&nbsp;d&nbsp;=&nbsp;1 //RIGHT,&nbsp;UP while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;0.5 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;0.5 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d //LEFT,&nbsp;LEFT,&nbsp;DOWN,&nbsp;DOWN while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;1 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d //RIGHT,&nbsp;RIGHT,&nbsp;RIGHT,&nbsp;UP,&nbsp;UP,&nbsp;UP while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;1.5 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;1.5 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d //LEFT,&nbsp;LEFT,&nbsp;LEFT,&nbsp;LEFT,&nbsp;DOWN,&nbsp;DOWN,&nbsp;DOWN,&nbsp;DOWN while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;2 &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d现在，我们可以引入另一个变量m，用于我们在每一对while循环上采取的步骤数。let&nbsp;x&nbsp;=&nbsp;0 let&nbsp;y&nbsp;=&nbsp;0 let&nbsp;d&nbsp;=&nbsp;1 let&nbsp;m&nbsp;=&nbsp;0.5 //RIGHT,&nbsp;UP while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d m&nbsp;=&nbsp;m&nbsp;+&nbsp;0.5 //LEFT,&nbsp;LEFT,&nbsp;DOWN,&nbsp;DOWN while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d m&nbsp;=&nbsp;m&nbsp;+&nbsp;0.5 //RIGHT,&nbsp;RIGHT,&nbsp;RIGHT,&nbsp;UP,&nbsp;UP,&nbsp;UP while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d d&nbsp;=&nbsp;-1&nbsp;*&nbsp;d m&nbsp;=&nbsp;m&nbsp;+&nbsp;0.5 //LEFT,&nbsp;LEFT,&nbsp;LEFT,&nbsp;LEFT,&nbsp;DOWN,&nbsp;DOWN,&nbsp;DOWN,&nbsp;DOWN while&nbsp;x&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;x&nbsp;=&nbsp;x&nbsp;+&nbsp;d while&nbsp;y&nbsp;*&nbsp;d&nbsp;<&nbsp;m &nbsp;&nbsp;print(x,&nbsp;y) &nbsp;&nbsp;y&nbsp;=&nbsp;y&nbsp;+&nbsp;d最后，我们发现每对WITH循环的结构是相同的，可以简化为放置在另一个循环内的一个循环。另外，为了避免使用实数，我将m的初始值乘以m；值m被增加，并且每个不等式的两边都乘以2。这将导致答案开头所示的解决方案。