在一个螺旋循环

一个朋友需要一个algorithm,让他循环一个NxMmatrix的元素(N和M是奇数)。 我提出了一个解决scheme,但我想看看我的同事是否可以提出一个更好的解决scheme。

我发布我的解决scheme作为这个问题的答案。

输出示例:

对于3x3matrix,输出应该是:

(1,0)(1,0)(1,1)(0,1)(-1,1)(-1,0)(-1,-1)(0,-1)(1,-1 )

3x3矩阵

此外,该algorithm应该支持非平方matrix,例如对于一个5x3matrix,输出应该是:

(1,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)

5x3矩阵

这是我的解决scheme(在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 

C ++的人? 从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; } } 

我爱Python的发电机。

 def spiral(N, M): x,y = 0,0 dx, dy = 0, -1 for dumb in xrange(N*M): if abs(x) == abs(y) and [dx,dy] != [1,0] or x>0 and y == 1-x: dx, dy = -dy, dx # corner, change direction if abs(x)>N/2 or abs(y)>M/2: # non-square dx, dy = -dy, dx # change direction x, y = -y+dx, x+dy # jump yield x, y x, y = x+dx, y+dy 

testing:

 print 'Spiral 3x3:' for a,b in spiral(3,3): print (a,b), print '\n\nSpiral 5x3:' for a,b in spiral(5,3): print (a,b), 

你得到:

 Spiral 3x3: (0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) Spiral 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) 

这里有一个O(1)解决scheme来find平方螺旋的位置: 小提琴

 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+... var en = r * 2; // points by face 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, r]; 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; } 
 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 

对于这个问题,已经有许多提出的解决scheme用各种编程语言写成,但是它们似乎都源于同样复杂的方法。 我将考虑计算螺旋的更一般的问题,可以使用归纳简洁地expression。

基本情况:从(0,0)开始,向前移动1平方米,向左转,向前移动1平方米,向左转。 归纳步骤:向前移动n + 1个方格,向左转,向前移动n + 1个方格,向左转。

expression这个问题的math优雅强烈地表明应该有一个简单的algorithm来计算解决scheme。 记住抽象概念,我select不使用特定的编程语言来实现algorithm,而是使用伪代码。

首先,我将考虑一个algorithm,使用4对while循环计算螺旋的2次迭代。 每一对的结构都是相似的,但本身是不同的。 这看起来似乎很疯狂(一些循环只能执行一次),但是一步一步地进行转换,直到我们到达4对相同的循环,因此可以用放置在另一个循环内的一对循环replace。 这将为我们提供一个计算n迭代的通用解决scheme,而不使用任何条件。

 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 

我们要做的第一个转换是引入一个新的variablesd,用于方向,保持值+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之间的任何实数值,而不会影响不等式的结果。 我们select从每一对while循环的不等式中减去0.5,以build立更多的模式。

 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 

现在我们可以在每一对while循环中引入另一个variablesm作为步数。

 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 

最后,我们看到每对while循环的结构是相同的,可以简化为放置在另一个循环内部的单个循环。 此外,为了避免使用实数值,我已经乘以m的初始值; 值m递增; 而且每个不平等的两边都是2。

这导致解决scheme显示在这个答案的开始。

Java螺旋“代码高尔夫”尝试,基于C ++变体。

 public static void Spiral(int X, int Y) { int x=0, y=0, dx = 0, dy = -1; int t = Math.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)) { System.out.println(x+","+y); //DO STUFF } if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))) { t=dx; dx=-dy; dy=t; } x+=dx; y+=dy; } } 

这是我的解决scheme(在Ruby中)

 def spiral(xDim, yDim) sx = xDim / 2 sy = yDim / 2 cx = cy = 0 direction = distance = 1 yield(cx,cy) while(cx.abs <= sx || cy.abs <= sy) distance.times { cx += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } distance.times { cy += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } distance += 1 direction *= -1 end end spiral(5,3) { |x,y| print "(#{x},#{y})," } 

TDD,在Java中。

SpiralTest.java:

 import java.awt.Point; import java.util.List; import junit.framework.TestCase; public class SpiralTest extends TestCase { public void test3x3() throws Exception { assertEquals("(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)", strung(new Spiral(3, 3).spiral())); } public void test5x3() throws Exception { assertEquals("(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)", strung(new Spiral(5, 3).spiral())); } private String strung(List<Point> points) { StringBuffer sb = new StringBuffer(); for (Point point : points) sb.append(strung(point)); return sb.toString().trim(); } private String strung(Point point) { return String.format("(%s, %s) ", point.x, point.y); } } 

Spiral.java:

 import java.awt.Point; import java.util.ArrayList; import java.util.List; public class Spiral { private enum Direction { E(1, 0) {Direction next() {return N;}}, N(0, 1) {Direction next() {return W;}}, W(-1, 0) {Direction next() {return S;}}, S(0, -1) {Direction next() {return E;}},; private int dx; private int dy; Point advance(Point point) { return new Point(point.x + dx, point.y + dy); } abstract Direction next(); Direction(int dx, int dy) { this.dx = dx; this.dy = dy; } }; private final static Point ORIGIN = new Point(0, 0); private final int width; private final int height; private Point point; private Direction direction = Direction.E; private List<Point> list = new ArrayList<Point>(); public Spiral(int width, int height) { this.width = width; this.height = height; } public List<Point> spiral() { point = ORIGIN; int steps = 1; while (list.size() < width * height) { advance(steps); advance(steps); steps++; } return list; } private void advance(int n) { for (int i = 0; i < n; ++i) { if (inBounds(point)) list.add(point); point = direction.advance(point); } direction = direction.next(); } private boolean inBounds(Point p) { return between(-width / 2, width / 2, px) && between(-height / 2, height / 2, py); } private static boolean between(int low, int high, int n) { return low <= n && n <= high; } } 

这是一个C ++解决scheme,它显示了你可以直接和容易地计算下一个(x,y)坐标,而不需要跟踪当前方向,半径或其他任何东西:

 void spiral(const int M, const int N) { // Generate an Ulam spiral centered at (0, 0). int x = 0; int y = 0; int end = max(N, M) * max(N, M); for(int i = 0; i < end; ++i) { // Translate coordinates and mask them out. int xp = x + N / 2; int yp = y + M / 2; if(xp >= 0 && xp < N && yp >= 0 && yp < M) cout << xp << '\t' << yp << '\n'; // No need to track (dx, dy) as the other examples do: if(abs(x) <= abs(y) && (x != y || x >= 0)) x += ((y >= 0) ? 1 : -1); else y += ((x >= 0) ? -1 : 1); } } 

如果你所要做的就是生成螺旋中的前N个点(没有原始问题的掩蔽到N×M区域的限制),代码就变得非常简单:

 void spiral(const int N) { int x = 0; int y = 0; for(int i = 0; i < N; ++i) { cout << x << '\t' << y << '\n'; if(abs(x) <= abs(y) && (x != y || x >= 0)) x += ((y >= 0) ? 1 : -1); else y += ((x >= 0) ? -1 : 1); } } 

诀窍是你可以比较x和y来确定你所在的广场的哪一侧,并告诉你进入的方向。

哈斯克尔,请select:

 spiral xy = (0, 0) : concatMap ring [1 .. max x' y'] where ring n | n > x' = left x' n ++ right x' (-n) ring n | n > y' = up ny' ++ down (-n) y' ring n = up nn ++ left nn ++ down nn ++ right nn up xy = [(x, n) | n <- [1-y .. y]]; down = (.) reverse . up right xy = [(n, y) | n <- [1-x .. x]]; left = (.) reverse . right (x', y') = (x `div` 2, y `div` 2) spiral xy = filter (\(x',y') -> 2*abs x' <= x && 2*abs y' <= y) . scanl (\(a,b) (c,d) -> (a+c,b+d)) (0,0) $ concat [ (:) (1,0) . tail $ concatMap (replicate n) [(0,1),(-1,0),(0,-1),(1,0)] | n <- [2,4..max xy] ] 

这是在C.

我碰巧select了不好的variables名称。 在名称T ==顶部,L ==左边,B ==底部,R ==右边。 所以,tli是左上angular,而brj是右下angularj。

 #include<stdio.h> typedef enum { TLTOR = 0, RTTOB, BRTOL, LBTOT } Direction; int main() { int arr[][3] = {{1,2,3},{4,5,6}, {7,8,9}, {10,11,12}}; int tli = 0, tlj = 0, bri = 3, brj = 2; int i; Direction d = TLTOR; while (tli < bri || tlj < brj) { switch (d) { case TLTOR: for (i = tlj; i <= brj; i++) { printf("%d ", arr[tli][i]); } tli ++; d = RTTOB; break; case RTTOB: for (i = tli; i <= bri; i++) { printf("%d ", arr[i][brj]); } brj --; d = BRTOL; break; case BRTOL: for (i = brj; i >= tlj; i--) { printf("%d ", arr[bri][i]); } bri --; d = LBTOT; break; case LBTOT: for (i = bri; i >= tli; i--) { printf("%d ", arr[i][tlj]); } tlj ++; d = TLTOR; break; } } if (tli == bri == tlj == brj) { printf("%d\n", arr[tli][tlj]); } } 

这里是C#,linq'ish。

 public static class SpiralCoords { public static IEnumerable<Tuple<int, int>> GenerateOutTo(int radius) { //TODO trap negative radius. 0 is ok. foreach(int r in Enumerable.Range(0, radius + 1)) { foreach(Tuple<int, int> coord in GenerateRing(r)) { yield return coord; } } } public static IEnumerable<Tuple<int, int>> GenerateRing(int radius) { //TODO trap negative radius. 0 is ok. Tuple<int, int> currentPoint = Tuple.Create(radius, 0); yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); //move up while we can while (currentPoint.Item2 < radius) { currentPoint.Item2 += 1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move left while we can while (-radius < currentPoint.Item1) { currentPoint.Item1 -=1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move down while we can while (-radius < currentPoint.Item2) { currentPoint.Item2 -= 1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move right while we can while (currentPoint.Item1 < radius) { currentPoint.Item1 +=1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move up while we can while (currentPoint.Item2 < -1) { currentPoint.Item2 += 1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } } } 

问题的第一个例子(3×3)将是:

 var coords = SpiralCoords.GenerateOutTo(1); 

问题的第二个例子(5×3)将是:

 var coords = SpiralCoords.GenerateOutTo(2).Where(x => abs(x.Item2) < 2); 

这是我非常糟糕的解决scheme,从最基本的Java知识。 在这里,我必须把单位放在一个螺旋状的场地上。 单位不能放在其他单位的顶部,山上或海洋。

要清楚。 这不是一个好的解决scheme。 这是一个非常糟糕的解决scheme,为了别人的乐趣嘲笑它可以做多坏

 private void unitPlacementAlgorithm(Position p, Unit u){ int i = p.getRow(); int j = p.getColumn(); int iCounter = 1; int jCounter = 0; if (getUnitAt(p) == null) { unitMap.put(p, u); } else { iWhileLoop(i, j, iCounter, jCounter, -1, u); } } private void iWhileLoop(int i, int j, int iCounter, int jCounter, int fortegn, Unit u){ if(iCounter == 3) { for(int k = 0; k < 3; k++) { if(k == 2) { //This was added to make the looping stop after 9 units System.out.println("There is no more room around the city"); return; } i--; if (getUnitAt(new Position(i, j)) == null && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) { unitMap.put(new Position(i, j), u); return; } iCounter--; } } while (iCounter > 0) { if (fortegn > 0) { i++; } else { i--; } if (getUnitAt(new Position(i, j)) == null && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) { unitMap.put(new Position(i, j), u); return; } iCounter--; jCounter++; } fortegn *= -1; jWhileLoop(i, j, iCounter, jCounter, fortegn, u); } private void jWhileLoop(int i, int j, int iCounter, int jCounter, int fortegn, Unit u) { while (jCounter > 0) { if (fortegn > 0) { j++; } else { j--; } if (getUnitAt(new Position(i, j)) == null && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) { unitMap.put(new Position(i, j), u); return; } jCounter--; iCounter++; if (jCounter == 0) { iCounter++; } } iWhileLoop(i, j, iCounter, jCounter, fortegn, u); } 

感谢任何能够真正阅读本文的人

奖金问题:这个“algorithm”的运行时间是多less? :P

这是一个稍微不同的版本 – 尝试使用LUA中的recursioniterators 。 在每个步骤中,程序在matrix内部进一步下降并循环。 我还添加了一个额外的标志clockwiseanticlockwise 。 输出从右下angular开始,recursion地向中心循环。

 local row, col, clockwise local SpiralGen SpiralGen = function(loop) -- Generator of elements in one loop local startpos = { x = col - loop, y = row - loop } local IteratePosImpl = function() -- This function calculates returns the cur, next position in a loop. If called without check, it loops infinitely local nextpos = {x = startpos.x, y = startpos.y} local step = clockwise and {x = 0, y = -1} or { x = -1, y = 0 } return function() curpos = {x = nextpos.x, y = nextpos.y} nextpos.x = nextpos.x + step.x nextpos.y = nextpos.y + step.y if (((nextpos.x == loop or nextpos.x == col - loop + 1) and step.y == 0) or ((nextpos.y == loop or nextpos.y == row - loop + 1) and step.x == 0)) then --Hit a corner in the loop local tempstep = {x = step.x, y = step.y} step.x = clockwise and tempstep.y or -tempstep.y step.y = clockwise and -tempstep.x or tempstep.x -- retract next step with new step nextpos.x = curpos.x + step.x nextpos.y = curpos.y + step.y end return curpos, nextpos end end local IteratePos = IteratePosImpl() -- make an instance local curpos, nextpos = IteratePos() while (true) do if(nextpos.x == startpos.x and nextpos.y == startpos.y) then coroutine.yield(curpos) SpiralGen(loop+1) -- Go one step inner, since we're done with this loop break -- done with inner loop, get out else if(curpos.x < loop + 1 or curpos.x > col - loop or curpos.y < loop + 1 or curpos.y > row - loop) then break -- done with all elemnts, no place to loop further, break out of recursion else local curposL = {x = curpos.x, y = curpos.y} curpos, nextpos = IteratePos() coroutine.yield(curposL) end end end end local Spiral = function(rowP, colP, clockwiseP) row = rowP col = colP clockwise = clockwiseP return coroutine.wrap(function() SpiralGen(0) end) -- make a coroutine that returns all the values as an iterator end --test for pos in Spiral(10,2,true) do print (pos.y, pos.x) end for pos in Spiral(10,9,false) do print (pos.y, pos.x) end 

这是基于你自己的解决scheme,但我们可以更聪明地findangular落。 这使得更容易看到,如果M和N非常不同,那么你可以跳过外面的区域。

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

和一个比O(max(n,m)^ 2)更好的发生器的解决scheme,因为如果它们不是解决scheme的一部分,它将跳过整个条带,所以它是O(nm + abs(nm)^ 2)。

 def spiral(X,Y): X = X+1>>1 Y = Y+1>>1 x = y = 0 d = side = 1 while x<X or y<Y: if abs(y)<Y: for x in range(x, x+side, d): if abs(x)<X: yield x,y x += d else: x += side if abs(x)<X: for y in range(y, y+side, d): if abs(y)<Y: yield x,y y += d else: y += side d =-d side = d-side 
 Here is my attempt for simple C solution. First print the outer spiral and move one block inside..and repeat. #define ROWS 5 #define COLS 5 //int A[ROWS][COLS] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {11, 12, 13, 14}, {15, 16, 17, 18} }; //int A[ROWS][COLS] = { {1, 2, 3}, {6, 7, 8}, { 12, 13, 14} }; //int A[ROWS][COLS] = { {1, 2}, {3, 4}}; int A[ROWS][COLS] = { {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15} , {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25} }; void print_spiral(int rows, int cols) { int row = 0; int offset = 0; while (offset < (ROWS - 1)) { /* print one outer loop at a time. */ for (int col = offset; col <= cols; col++) { printf("%d ", A[offset][col]); } for (row = offset + 1; row <= rows; row++) { printf("%d ", A[row][cols]); } for (int col = cols - 1; col >= offset; col--) { printf("%d ", A[rows][col]); } for (row = rows - 1; row >= offset + 1; row--) { printf("%d ", A[row][offset]); } /* Move one block inside */ offset++; rows--; cols--; } printf("\n"); } int _tmain(int argc, _TCHAR* argv[]) { print_spiral(ROWS-1, COLS-1); return 0; } 

AutoIt的解决scheme

 #include <Math.au3> #include <Array.au3> Func SpiralSearch($xMax,$yMax) $x = 0 $y = 0 $dx = 0 $dy = -1 for $i=0 To _max($xMax, $yMax)^2-1 Step 1 if -$xMax/2 < $x and $x <= $xMax/2 And -$yMax/2 < $y And $y <= $yMax/2 Then MsgBox(0, "We are here ", $x & " " & $y) EndIf if $x == $y or ($x < 0 and $x == -$y) or ($x > 0 and $x == 1-$y) Then _ArraySwap ($dx, $dy) $dx=-$dx EndIf $x += $dx $y += $dy Next EndFunc 

我最近有一个类似的挑战,我必须创build一个二维数组,并使用螺旋matrixalgorithm来sorting和打印结果。 这个C#代码将与一个N,N二维数组一起工作。 这是为了清晰起见,可能会被重新考虑,以适应您的需求。

 //CREATE A NEW MATRIX OF SIZE 4 ROWS BY 4 COLUMNS - SCALE MATRIX SIZE HERE SpiralMatrix SM = new SpiralMatrix(4, 4); string myData = SM.Read(); public class SpiralMatrix { //LETS BUILD A NEW MATRIX EVERY TIME WE INSTANTIATE OUR CLASS public SpiralMatrix(int Rows, int Cols) { Matrix = new String[Rows, Cols]; int pos = 1; for(int r = 0; r<Rows; r++){ for (int c = 0; c < Cols; c++) { //POPULATE THE MATRIX WITH THE CORRECT ROW,COL COORDINATE Matrix[r, c] = pos.ToString(); pos++; } } } //READ MATRIX public string Read() { int Row = 0; int Col = 0; string S = ""; bool isDone = false; //CHECK tO SEE IF POSITION ZERO IS AVAILABLE if(PosAvailable(Row, Col)){ S = ConsumePos(Row, Col); } //START READING SPIRAL //THIS BLOCK READS A FULL CYCLE OF RIGHT,DOWN,LEFT,UP EVERY ITERATION while(!isDone) { bool goNext = false; //READ ALL RIGHT SPACES ON THIS PATH PROGRESSION while (PosAvailable(Row, Col+1)) { //Is ReadRight Avail Col++; S += ConsumePos(Row, Col); goNext = true; } //READ ALL DOWN SPACES ON THIS PATH PROGRESSION while(PosAvailable(Row+1, Col)){ //Is ReadDown Avail Row++; S += ConsumePos(Row, Col); goNext = true; } //READ ALL LEFT SPACES ON THIS PATH PROGRESSION while(PosAvailable(Row, Col-1)){ //Is ReadLeft Avail Col--; S += ConsumePos(Row, Col); goNext = true; } //READ ALL UP SPACES ON THIS PATH PROGRESSION while(PosAvailable(Row-1, Col)){ //Is ReadUp Avail Row--; S += ConsumePos(Row, Col); goNext = true; } if(!goNext){ //DONE - SET EXIT LOOP FLAG isDone = true; } } return S; } //DETERMINE IF THE POSITION IS AVAILABLE public bool PosAvailable(int Row, int Col) { //MAKE SURE WE ARE WITHIN THE BOUNDS OF THE ARRAY if (Row < Matrix.GetLength(0) && Row >= 0 && Col < Matrix.GetLength(1) && Col >= 0) { //CHECK COORDINATE VALUE if (Matrix[Row, Col] != ConsumeChar) return true; else return false; } else { //WE ARE OUT OF BOUNDS return false; } } public string ConsumePos(int Row, int Col) { string n = Matrix[Row, Col]; Matrix[Row, Col] = ConsumeChar; return n; } public string ConsumeChar = "X"; public string[,] Matrix; } 

// PHP的实现

 function spiral($n) { $r = intval((sqrt($n + 1) - 1) / 2) + 1; // compute radius : inverse arithmetic sum of 8+16+24+...= $p = (8 * $r * ($r - 1)) / 2; // compute total point on radius -1 : arithmetic sum of 8+16+24+... $en = $r * 2; // points by face $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 $pos = array(0, 0, $r); switch (intval($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; } return $pos; } for ($i = 0; $i < 168; $i++) { echo '<pre>'; print_r(spiral($i)); echo '</pre>'; } 

我和一位朋友做了这个调整螺旋到Javascript的canvas长宽比的朋友。 最好的解决scheme,我得到了像素逐像素,填补整个图像。

希望它有助于一个人。

 var width = 150; var height = 50; var x = -(width - height)/2; var y = 0; var dx = 1; var dy = 0; var x_limit = (width - height)/2; var y_limit = 0; var counter = 0; var canvas = document.getElementById("canvas"); var ctx = canvas.getContext('2d'); setInterval(function(){ if ((-width/2 < x && x <= width/2) && (-height/2 < y && y <= height/2)) { console.log("[ " + x + " , " + y + " ]"); ctx.fillStyle = "#FF0000"; ctx.fillRect(width/2 + x, height/2 - y,1,1); } if( dx > 0 ){//Dir right if(x > x_limit){ dx = 0; dy = 1; } } else if( dy > 0 ){ //Dir up if(y > y_limit){ dx = -1; dy = 0; } } else if(dx < 0){ //Dir left if(x < (-1 * x_limit)){ dx = 0; dy = -1; } } else if(dy < 0) { //Dir down if(y < (-1 * y_limit)){ dx = 1; dy = 0; x_limit += 1; y_limit += 1; } } counter += 1; //alert (counter); x += dx; y += dy; }, 1); 

你可以看到它在http://jsfiddle.net/hitbyatruck/c4Kd6/上工作。; 只要确保在javascriptvariables和HTML上的属性上更改canvas的宽度和高度即可。

我有一个开源的图书馆,像素扫描,这是一个python库,提供function,扫描网格上的各种空间模式的像素。 包括空间模式是圆形,环形,网格,蛇和随机游走。 也有各种转换(例如,剪辑,交换,旋转,翻译)。 原来的OP问题可以解决如下

 for x, y in clip(swap(ringscan(0, 0, 0, 2)), miny=-1, maxy=1): print x, y 

这产生点

 (0,0) (1,0) (1,1) (0,1) (-1,1) (-1,0) (-1,-1) (0,-1) (1,-1) (2,0) (2,1) (-2,1) (-2,0) (-2,-1) (2,-1) 

库生成器和转换可以链接在一起,以改变各种顺序和空间模式中的点。

只是为了在Javascript中获得乐趣:

 function spiral(x, y) { var iy = ix = 0 , hr = (x - 1) / 2 , vr = (y - 1) / 2 , tt = x * y , matrix = [] , step = 1 , dx = 1 , dy = 0; while(matrix.length < tt) { if((ix <= hr && ix >= (hr * -1)) && (iy <= vr && (iy >= (vr * -1)))) { console.log(ix, iy); matrix.push([ix, iy]); } ix += dx; iy += dy; // check direction if(dx !== 0) { // increase step if(ix === step && iy === (step * -1)) step++; // horizontal range reached if(ix === step || (ix === step * -1)) { dy = (ix === iy)? (dx * -1) : dx; dx = 0; } } else { // vertical range reached if(iy === step || (iy === step * -1)) { dx = (ix === iy)? (dy * -1) : dy; dy = 0; } } } return matrix; } var sp = spiral(5, 3); 

C#版本,也处理非方形大小。

 private static Point[] TraverseSpiral(int width, int height) { int numElements = width * height + 1; Point[] points = new Point[numElements]; int x = 0; int y = 0; int dx = 1; int dy = 0; int xLimit = width - 0; int yLimit = height - 1; int counter = 0; int currentLength = 1; while (counter < numElements) { points[counter] = new Point(x, y); x += dx; y += dy; currentLength++; if (dx > 0) { if (currentLength >= xLimit) { dx = 0; dy = 1; xLimit--; currentLength = 0; } } else if (dy > 0) { if (currentLength >= yLimit) { dx = -1; dy = 0; yLimit--; currentLength = 0; } } else if (dx < 0) { if (currentLength >= xLimit) { dx = 0; dy = -1; xLimit--; currentLength = 0; } } else if (dy < 0) { if (currentLength >= yLimit) { dx = 1; dy = 0; yLimit--; currentLength = 0; } } counter++; } Array.Reverse(points); return points; } 

我正在分享我为不同目的devise的代码; 它是关于find列号“X”和数组元素@螺旋索引“索引”的行号“Y”。 该函数取matrix的宽度“w”和高度“h”,以及所需的“索引”。 当然,这个function可以用来产生相同的所需输出。 我认为这是最快的方法(因为它跳过单元而不是扫描它们)。

  rec BuildSpiralIndex(long w, long h, long index = -1) { long count = 0 , x = -1, y = -1, dir = 1, phase=0, pos = 0, length = 0, totallength = 0; bool isVertical = false; if(index>=(w*h)) return null; do { isVertical = (count % 2) != 0; length = (isVertical ? h : w) - count/2 - count%2 ; totallength += length; count++; } while(totallength<index); count--; w--; h--; phase = (count / 4); pos = (count%4); x = (pos > 1 ? phase : w - phase); y = ((pos == 1 || pos == 2) ? h - phase : phase) + (1 * (pos == 3 ? 1 : 0)); dir = pos > 1 ? -1 : 1; if (isVertical) y -= (totallength - index - 1) * dir; else x -= (totallength - index -1) * dir; return new rec { X = x, Y = y }; } 

Python looping clockwise spiral code using Can Berk Güder answer .

 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 

Here's a JavaScript (ES6) iterative solution to this problem:

 let spiralMatrix = (x, y, step, count) => { let distance = 0; let range = 1; let direction = 'up'; for ( let i = 0; i < count; i++ ) { console.log('x: '+x+', y: '+y); distance++; switch ( direction ) { case 'up': y += step; if ( distance >= range ) { direction = 'right'; distance = 0; } break; case 'right': x += step; if ( distance >= range ) { direction = 'bottom'; distance = 0; range += 1; } break; case 'bottom': y -= step; if ( distance >= range ) { direction = 'left'; distance = 0; } break; case 'left': x -= step; if ( distance >= range ) { direction = 'up'; distance = 0; range += 1; } break; default: break; } } } 

以下是如何使用它:

spiralMatrix(0, 0, 1, 100);

This will create an outward spiral, starting at coordinates (x = 0, y = 0) with step of 1 and a total number of items equals to 100. The implementation always starts the movement in the following order – up, right, bottom, left.

Please, note that this implementation creates square matrices.

Davidont's excellent solution in VB.Net

  Public Function Spiral(n As Integer) As RowCol ' 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 ' starts with row 0 col -1 Dim r As Integer = CInt(Math.Floor((Math.Sqrt(n + 1) - 1) / 2) + 1) ' compute radius : inverse arithmetic sum of 8+16+24+...= Dim p As Integer = (8 * r * (r - 1)) \ 2 ' compute total point on radius -1 : arithmetic sum of 8+16+24+... Dim en As Integer = r * 2 ' points by face Dim a As Integer = (1 + n - p) Mod (r * 8) ' compute the position and shift it so the first is (-r,-r) but (-r+1,-r) ' so square can connect Dim row As Integer Dim col As Integer Select Case Math.Floor(a \ (r * 2)) ' find the face : 0 top, 1 right, 2, bottom, 3 left Case 0 row = a - r col = -r Case 1 row = r col = (a Mod en) - r Case 2 row = r - (a Mod en) col = r Case 3 row = -r col = r - (a Mod en) End Select Return New RowCol(row, col) End Function 

I really like this challenge 1+ for this post. I tried this by Ruby Code :

For 3X3 Square matrix

 (0..8).each do |i| j = Math.sqrt(i).round k = (j ** 2 - i).abs - j p = [k, -k].map {|l| (l + j ** 2 - i - (j % 2)) * 0.5 * (-1) ** j}.map(&:to_i) puts "(#{p[0]}, #{p[1]}) " end 

输出:

 (0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) 

For 5X3 as you mentioned in image

 iter = (0..19).to_enum while true i = iter.next j = Math.sqrt(i).round k = (j ** 2 - i).abs - j p = [k, -k].map {|l| (l + j ** 2 - i - (j % 2)) * 0.5 * (-1) ** j}.map(&:to_i) print "(#{p[0]}, #{p[1]}) " if i == 11 5.times {i = iter.next} end end 

Output for this:

 (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)