Зацикливание по спирали

Другу нужен алгоритм, который позволил бы ему зацикливаться на элементах матрицы NxM (N и M нечетны). Я придумал решение, но я хотел посмотреть, смогут ли мои коллеги SO’s найти лучшее решение.

Я отправляю свое решение в качестве ответа на этот вопрос.

Пример:

Для матрицы 3×3 выход должен быть:

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

Матрица 3x3

Кроме того, алгоритм должен поддерживать неквадратные матрицы, поэтому, например, для матрицы 5×3, результат должен быть:

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

Матрица 5x3

30 Solutions collect form web for “Зацикливание по спирали”

Вот мое решение (в 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; } } 

Мне нравятся генераторы питона.

 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 

Тестирование с помощью:

 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), чтобы найти положение в квадрате спирали: Fiddle

 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 

Было много предлагаемых решений для этой проблемы, написанных на разных языках программирования, однако все они, похоже, вытекают из одного и того же запутанного подхода. Я рассмотрю более общую проблему вычисления спирали, которую можно кратко выразить с помощью индукции.

Базовый кейс: Начните с (0, 0), двигайтесь вперед на 1 квадрат, поворачивайте налево, двигайтесь вперед на 1 квадрат, поворачивайте налево. Индуктивный шаг: переместите вперед n + 1 квадрат, поверните налево, переместите n + 1 квадрат, поверните налево.

Математическая элегантность выражения этой проблемы настоятельно предполагает, что для вычисления решения должен быть простой алгоритм. Помня об абстракции, я решил не реализовывать алгоритм на определенном языке программирования, а скорее как псевдокод.

Сначала я рассмотрю алгоритм вычисления всего 2 итераций спирали, используя 4 пары циклов while. Структура каждой пары аналогична, но сама по себе является самостоятельной. Сначала это может показаться сумасшедшим (некоторые петли выполняются только один раз), но шаг за шагом я буду делать преобразования до тех пор, пока мы не достигнем четырех пар циклов, которые идентичны и, следовательно, могут быть заменены одной парой, помещенной внутри другого цикла. Это даст нам общее решение вычислительных 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 являются целыми числами, поэтому мы можем вычесть любое реальное значение между 0 и 1 из RHS, не влияя на результат неравенства. Мы выбираем вычесть 0,5 из неравенств любой другой пары циклов while, чтобы установить больше шаблона.

 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 

Наконец, мы видим, что структура каждой пары циклов while идентична и может быть сведена к одному циклу, помещенному внутри другого цикла. Кроме того, чтобы избежать использования реальных значений множителей, я умножил начальное значение m; значение m увеличивается на; и обеим сторонам каждого неравенства на 2.

Это приводит к решению, показанному в начале этого ответа.

Java-спираль «Code golf», основанная на варианте 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; } } 

Вот C ++-решение, которое показывает, что вы можете сразу и легко вычислить следующие (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 x 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, чтобы определить, на какой стороне квадрата вы находитесь, и это говорит вам, в каком направлении двигаться.

Вот мое решение (In 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 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 list = new ArrayList(); public Spiral(int width, int height) { this.width = width; this.height = height; } public List 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; } } 

Хаскелл, сделай выбор:

 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.

Мне приходилось выбирать неправильные имена переменных. В именах T == top, L == left, B == bottom, R == right. Итак, tli – верхний левый i, а brj – нижний правый j.

 #include 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> GenerateOutTo(int radius) { //TODO trap negative radius. 0 is ok. foreach(int r in Enumerable.Range(0, radius + 1)) { foreach(Tuple coord in GenerateRing(r)) { yield return coord; } } } public static IEnumerable> GenerateRing(int radius) { //TODO trap negative radius. 0 is ok. Tuple 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); } } } 

Первый пример вопроса (3x3):

 var coords = SpiralCoords.GenerateOutTo(1); 

Второй пример вопроса (5x3):

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

Это мое очень плохое решение, сделанное из минимальных знаний Java. Здесь я должен разместить единицы на поле по спирали. Единицы не могут быть размещены на вершине других частей или на горах или в океане.

Быть ясным. Это нехорошее решение. Это очень плохое решение, добавленное для удовольствия других людей, чтобы посмеяться над тем, как плохо это можно сделать

 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); } 

Престижность любому, кто действительно может это прочитать

Бонусный вопрос: каково время работы этого «алгоритма»?

Это немного другая версия – попытка использования recursion и iterators в LUA. На каждом шаге программа опускается далее внутри матрицы и петель. Я также добавил дополнительный флаг для спирали по clockwise или anticlockwise clockwise anticlockwise . Выход начинается с нижних правых углов и рекурсивно поворачивается к центру.

 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 

Цикл Python по часовой стрелке спиральный код, используя Can Berk Güder .

 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 

Это основано на вашем собственном решении, но мы можем умнее находить углы. Это облегчает просмотр того, как вы можете пропустить области вне, если 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), это 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 
 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

 #include  #include  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 

Недавно у меня была аналогичная задача, когда мне пришлось создать 2D-массив и использовать спиральный матричный алгоритм для сортировки и печати результатов. Этот код C # будет работать с массивом N, N 2D. Это многословно для ясности и, вероятно, может быть переупорядочено в соответствии с вашими потребностями.

 //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= 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; } в //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= 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 '
'; print_r(spiral($i)); echo '

'; }

Я сделал это с другом, который настраивает спираль на соотношение сторон canvasа на Javascript. Лучшее решение, которое я получил для пикселя эволюции изображения по пикселям, заполняя все изображение.

Надеюсь, это поможет кому-то.

 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/ . Просто не забудьте изменить ширину и высоту canvasа на javascript vars и на атрибуты HTML.

У меня есть библиотека с открытым исходным кодом, pixcan , которая представляет собой библиотеку python, которая предоставляет функции сканирования пикселей на сетке во множестве пространственных шаблонов. Пространственные узоры include круглые, кольца, сетки, змеи и случайные блуждания. Существуют также различные преобразования (например, клип, своп, поворот, перевод). Исходную задачу ОП можно решить следующим образом

 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# version, handles non-square sizes as well.

 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; } 

I am sharing this code which I designed for a different purpose; it is about finding the Column number “X”, and the row number “Y” of array element @ spiral index “index”. This function takes the width “w” and height “h” of the matrix, and the required “index”. Of course, this function can be used to produce the same required output. I think it is the fastest possible method (as it jumps over cells instead of scanning them).

  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 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 }; } 

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 

Here’s an answer in Julia: my approach is to assign the points in concentric squares (‘spirals’) around the origin (0,0) , where each square has side length m = 2n + 1 , to produce an ordered dictionary with location numbers (starting from 1 for the origin) as keys and the corresponding coordinate as value.

Since the maximum location per spiral is at (n,-n) , the rest of the points can be found by simply working backward from this point, ie from the bottom right corner by m-1 units, then repeating for the perpendicular 3 segments of m-1 units.

This process is written in reverse order below, corresponding to how the spiral proceeds rather than this reverse counting process, ie the ra [right ascending] segment is decremented by 3(m+1) , then la [left ascending] by 2(m+1) , and so on – hopefully this is self-explanatory.

 import DataStructures: OrderedDict, merge function spiral(loc::Int) s = sqrt(loc-1) |> floor |> Int if s % 2 == 0 s -= 1 end s = (s+1)/2 |> Int return s end function perimeter(n::Int) n > 0 || return OrderedDict([1,[0,0]]) m = 2n + 1 # width/height of the spiral [square] indexed by n # loc_max = m^2 # loc_min = (2n-1)^2 + 1 ra = [[m^2-(y+3m-3), [n,ny]] for y in (m-2):-1:0] la = [[m^2-(y+2m-2), [yn,n]] for y in (m-2):-1:0] ld = [[m^2-(y+m-1), [-n,yn]] for y in (m-2):-1:0] rd = [[m^2-y, [ny,-n]] for y in (m-2):-1:0] return OrderedDict(vcat(ra,la,ld,rd)) end function walk(n) cds = OrderedDict(1 => [0,0]) n > 0 || return cds for i in 1:n cds = merge(cds, perimeter(i)) end return cds end 

So for your first example, plugging m = 3 into the equation to find n gives n = (5-1)/2 = 2 , and walk(2) gives an ordered dictionary of locations to coordinates, which you can turn into just an array of coordinates by accessing the dictionary’s vals field:

 walk(2) DataStructures.OrderedDict{Any,Any} with 25 entries: 1 => [0,0] 2 => [1,0] 3 => [1,1] 4 => [0,1] ⋮ => ⋮ [(co[1],co[2]) for co in walk(2).vals] 25-element Array{Tuple{Int64,Int64},1}: (0,0) (1,0) ⋮ (1,-2) (2,-2) 

Note that for some functions [eg norm ] it can be preferable to leave the coordinates in arrays rather than Tuple{Int,Int} , but here I change them into tuples— (x,y) —as requested, using list comprehension.

The context for “supporting” a non-square matrix isn’t specified (note that this solution still calculates the off-grid values), but if you want to filter to only the range x by y (here for x=5 , y=3 ) after calculating the full spiral then intersect this matrix against the values from walk .

 grid = [[x,y] for x in -2:2, y in -1:1] 5×3 Array{Array{Int64,1},2}: [-2,-1] [-2,0] [-2,1] ⋮ ⋮ ⋮ [2,-1] [2,0] [2,1] [(co[1],co[2]) for co in intersect(walk(2).vals, grid)] 15-element Array{Tuple{Int64,Int64},1}: (0,0) (1,0) ⋮ (-2,0) (-2,-1) 

This is my approach for a square spiral in c#, i made this some time ago, i just thought i could add it, since it’s different from all the others, not the best, but just a different way, i am sure it can be adapted for a non-square too.

This approach i take the max number of steps in, instead of the max vector tho.

The main thing about this approach is the corners, there’s some adjustments for the first step and the “progress” step needed to go out of the “corner” in the right bottom corner.

 private void Spiral(int sequence) { const int x = 0; const int y = 1; int[,] matrix = new int[2, sequence]; int dirX, dirY, prevX, prevY, curr; dirX = dirY = prevX = prevY = curr = default(int); do { if (curr > 0) { prevX = matrix[x, curr - 1]; prevY = matrix[y, curr - 1]; } //Change direction based on the corner. if (Math.Abs(prevX) == Math.Abs(prevY) && curr > 0) { dirX = dirY = 0; if (prevY > 0 && prevX > 0) dirX = -1; else if (prevY > 0 && prevX < 0) dirY = -1; else if (prevY < 0 && prevX < 0) dirX = 1; else if (prevY < 0 && prevX > 0) //Move forward dirX = 1; else if (prevY == 0 && prevX == 0) //For the first step. dirX = 1; } else if (prevY < 0 && prevX > 0 && (Math.Abs(matrix[x, curr - 2]) == Math.Abs(matrix[y, curr - 2]))) //Move forward { dirX = 0; dirY = 1; } else if (prevX == 1 && prevY == 0) //For the second step. { dirY = 1; dirX = 0; } matrix[x, curr] = prevX + dirX; matrix[y, curr] = prevY + dirY; System.Console.Write($"({matrix[x, curr]},{matrix[y, curr]}) "); } while (++curr < sequence); } 

Here’s a solution in Python 3 for printing consecutive integers in a spiral clockwise and counterclockwise.

 import math def sp(n): # spiral clockwise a=[[0 for x in range(n)] for y in range(n)] last=1 for k in range(n//2+1): for j in range(k,nk): a[k][j]=last last+=1 for i in range(k+1,nk): a[i][j]=last last+=1 for j in range(nk-2,k-1,-1): a[i][j]=last last+=1 for i in range(nk-2,k,-1): a[i][j]=last last+=1 s=int(math.log(n*n,10))+2 # compute size of cell for printing form="{:"+str(s)+"}" for i in range(n): for j in range(n): print(form.format(a[i][j]),end="") print("") sp(3) # 1 2 3 # 8 9 4 # 7 6 5 sp(4) # 1 2 3 4 # 12 13 14 5 # 11 16 15 6 # 10 9 8 7 def sp_cc(n): # counterclockwise a=[[0 for x in range(n)] for y in range(n)] last=1 for k in range(n//2+1): for j in range(nk-1,k-1,-1): a[nk-1][j]=last last+=1 for i in range(nk-2,k-1,-1): a[i][j]=last last+=1 for j in range(k+1,nk): a[i][j]=last last+=1 for i in range(k+1,nk-1): a[i][j]=last last+=1 s=int(math.log(n*n,10))+2 # compute size of cell for printing form="{:"+str(s)+"}" for i in range(n): for j in range(n): print(form.format(a[i][j]),end="") print("") sp_cc(5) # 9 10 11 12 13 # 8 21 22 23 14 # 7 20 25 24 15 # 6 19 18 17 16 # 5 4 3 2 1 

объяснение

A spiral is made of concentric squares, for instance a 5×5 square with clockwise rotation looks like this:

  5x5 3x3 1x1 >>>>> ^ v >>> ^ v + ^ v + > ^ v < << <<< 

( >>>>> means "go 5 times right" or increase column index 5 times, v means down or increase row index, etc.)

All squares are the same up to their size, I looped over the concentric squares.

For each square the code has four loops (one for each side), in each loop we increase or decrease the columns or row index. If i is the row index and j the column index then a 5x5 square can be constructed by: - incrementing j from 0 to 4 (5 times) - incrementing i from 1 to 4 (4 times) - decrementing j from 3 to 0 (4 times) - decrementing i from 3 to 1 (3 times)

For the next squares (3x3 and 1x1) we do the same but shift the initial and final indices appropriately. I used an index k for each concentric square, there are n//2 + 1 concentric squares.

Finally, some math for pretty-printing.

To print the indexes:

 def spi_cc(n): # counter-clockwise a=[[0 for x in range(n)] for y in range(n)] ind=[] last=n*n for k in range(n//2+1): for j in range(nk-1,k-1,-1): ind.append((nk-1,j)) for i in range(nk-2,k-1,-1): ind.append((i,j)) for j in range(k+1,nk): ind.append((i,j)) for i in range(k+1,nk-1): ind.append((i,j)) print(ind) spi_cc(5) 
Interesting Posts

Имея стороннюю банку, включенную в затененную банку Maven, не добавляя ее в локальный repository

Сохраните одну веб-страницу (с фоновым изображением) с помощью Wget

Как установить часовой пояс по умолчанию в node.js?

std :: string to char *

Показывать источник видео Youtube в теге HTML5?

Windows Disk I / O 100% при загрузке в течение 20 минут

Существует ли стандартная функция в C, которая вернет длину массива?

Преобразовать шестнадцатеричную строку (char ) в int?

как конвертировать миллисекунды в формат даты в android?

Метод setMobileDataEnabled больше не может быть вызван как для Android L, так и позже

Снижается ли производительность при выполнении циклов, чей счетчик uop не кратен ширине процессора?

Я не могу изменить системные файлы из CMD

Как я могу извлечь букву диска для нового подключенного диска в байте?

MVVM Light Messenger – отправка и регистрация объектов

Соглашения о кодировании – перечисление имен

Давайте будем гением компьютера.