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

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

Вот мое решение (на 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}),"
}

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

spiral x y = (0, 0) : concatMap ring [1 .. max x' y'] where
    ring n | n > x' = left x' n  ++ right x' (-n)
    ring n | n > y' = up   n  y' ++ down (-n) y'
    ring n          = up n n ++ left n n ++ down n n ++ right n n
    up    x y = [(x, n) | n <- [1-y .. y]]; down = (.) reverse . up
    right x y = [(n, y) | n <- [1-x .. x]]; left = (.) reverse . right
    (x', y') = (x `div` 2, y `div` 2)

spiral x y = 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 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, p.x) && between(-height / 2, height / 2, p.y);
    }

    private static boolean between(int low, int high, int n) {
        return low <= n && n <= high;
    }
}

Я люблю генераторы питона.

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)

С ++ кто-нибудь? Быстрый перевод с 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;
    }
}

Это основано на вашем собственном решении, но мы можем быть более умными в поиске углов. Это упрощает понимание того, как можно пропустить области снаружи, если 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 (n-m) ^ 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

Попытка 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;
    }
}

Это в C.

Я случайно выбрал плохие имена переменных. В названиях T == top, L == left, B == bottom, R == right. Итак, tli - это верхний левый i, а brj - нижний правый j.

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

}

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

var coords = SpiralCoords.GenerateOutTo(1);

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

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

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

Это мое очень-очень плохое решение, основанное на минимальных знаниях 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);
}

Cudos для всех, кто действительно может это прочитать

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

Это немного другая версия - попытка использовать recursion и iterators в LUA. На каждом шаге программа спускается дальше по матрице и зацикливается. Я также добавил дополнительный флаг к спирали 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

Вот решение O (1), чтобы найти положение в квадратной спирали: Скрипка

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.info("n : ", n, " r : ", r, " p : ", p, " a : ", a, "  -->  ", pos);
    return pos;
}

Решение для AutoIt

#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

Недавно у меня была аналогичная задача, когда мне пришлось создать 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<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. Лучшее решение, которое я получил для пиксельной эволюции изображения, заполняя все изображение.

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

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.info("[ " + 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/. Просто не забудьте изменить ширину и высоту холста в переменных javascript и в атрибутах HTML.

Мне очень нравится эта задача 1+ для этого поста. Я пробовал это с помощью кода Рубин:

Для 3x3 Квадратная матрица

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

Для 5X3, как вы упомянули на изображении

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

Выход для этого:

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

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

У меня есть библиотека с открытым исходным кодом пиксельное сканирование, которая представляет собой библиотеку Python, которая предоставляет функции для сканирования пикселей на сетке в различных пространственных узорах. Включены пространственные шаблоны: круг, кольца, сетки, змеи и случайные прогулки. Также существуют различные преобразования (например, вырезать, поменять местами, повернуть, перевести). Исходная проблема 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.info(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);

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

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

Версия 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;
}

Я делюсь этим кодом, который я разработал для другой цели; речь идет о нахождении номера столбца «X» и номера строки «Y» элемента массива @ индекс спирали «index». Эта функция принимает ширину «w» и высоту «h» матрицы и требуемый «индекс». Конечно, эту функцию можно использовать для получения того же необходимого результата. Я считаю, что это самый быстрый из возможных методов (поскольку он перепрыгивает через ячейки, а не просматривает их).

    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 зацикливает код спирали по часовой стрелке с использованием Может ли Берк Гюдер ответить.

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

Вот итеративное решение этой проблемы на JavaScript (ES6):

let spiralMatrix = (x, y, step, count) => {
    let distance = 0;
    let range = 1;
    let direction = 'up';

    for ( let i = 0; i < count; i++ ) {
        console.info('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);

Это создаст внешнюю спираль, начиная с координат (x = 0, y = 0) с шагом 1, а общее количество элементов равно 100. Реализация всегда начинает движение в следующем порядке - вверх, вправо, вниз, оставил.

Обратите внимание, что эта реализация создает квадратные матрицы.

Отличное решение Davidont в 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

Вот ответ в Джулии: мой подход состоит в том, чтобы назначить точки в концентрических квадратах ('спиралях') вокруг исходной точки (0,0), где каждый квадрат имеет длину стороны m = 2n + 1, чтобы создать упорядоченный словарь с номерами местоположений (начиная с 1 для начала координат) как ключи и соответствующая координата как значение.

Поскольку максимальное положение на спираль находится в (n,-n), остальные точки можно найти, просто работая в обратном направлении от этой точки, то есть от нижнего правого угла на единицы m-1, а затем повторяя для перпендикулярных 3 сегментов единиц m-1.

Этот процесс описан ниже в обратном порядке, что соответствует тому, как движется спираль, а не процессу обратного счета, то есть сегмент ra [восходящий правый] уменьшается на 3(m+1), затем la [восходящий влево] на 2(m+1) и так далее - надеюсь, это говорит само за себя.

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,n-y]] for y in (m-2):-1:0]
    la = [[m^2-(y+2m-2), [y-n,n]] for y in (m-2):-1:0]
    ld = [[m^2-(y+m-1), [-n,y-n]] for y in (m-2):-1:0]
    rd = [[m^2-y, [n-y,-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

Итак, в вашем первом примере включение m = 3 в уравнение для поиска n дает n = (5-1)/2 = 2, а walk(2) дает упорядоченный словарь местоположений для координат, который вы можете превратить просто в массив координат, обратившись к полю vals словаря:

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)

Обратите внимание, что для некоторых функций [например, norm] может быть предпочтительнее оставить координаты в массивах, а не в Tuple{Int,Int}, но здесь я преобразовываю их в кортежи - (x,y) - по запросу, используя понимание списка.

Контекст для «поддержки» неквадратной матрицы не указан (обратите внимание, что это решение по-прежнему вычисляет значения вне сети), но если вы хотите отфильтровать только диапазон x по y (здесь для x=5, y=3) после вычисляя полную спираль, затем intersect этой матрицы по значениям из 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)

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

В этом подходе я использую максимальное количество шагов вместо максимального вектора tho.

Главное в этом подходе - углы, есть некоторые корректировки для первого шага и шага «прогресса», необходимого для выхода из «угла» в правом нижнем углу.

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

Вот решение в Python 3 для печати последовательных целых чисел по спирали по и против часовой стрелки.

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,n-k):
          a[k][j]=last
          last+=1
      for i in range(k+1,n-k):
          a[i][j]=last
          last+=1
      for j in range(n-k-2,k-1,-1):
          a[i][j]=last
          last+=1
      for i in range(n-k-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(n-k-1,k-1,-1):
          a[n-k-1][j]=last
          last+=1
      for i in range(n-k-2,k-1,-1):
          a[i][j]=last
          last+=1
      for j in range(k+1,n-k):
          a[i][j]=last
          last+=1
      for i in range(k+1,n-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_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

Объяснение

Спираль состоит из концентрических квадратов, например квадрат 5x5 с вращением по часовой стрелке выглядит так:

 5x5        3x3      1x1

>>>>>
^   v       >>>
^   v   +   ^ v   +   >
^   v       <<<
<<<<v

(>>>>> означает «пойти 5 раз вправо» или увеличить индекс столбца в 5 раз, v означает уменьшить или увеличить индекс строки и т. д.)

Все квадраты одинаковые по размеру, концентрические квадраты я обвела петлей.

Для каждого квадрата код имеет четыре цикла (по одному для каждой стороны), в каждом цикле мы увеличиваем или уменьшаем столбцы или индекс строки. Если i - это индекс строки, а j - индекс столбца, то квадрат 5x5 можно построить следующим образом: - увеличение j от 0 до 4 (5 раз) - увеличение i от 1 до 4 (в 4 раза) - уменьшение j с 3 до 0 (в 4 раза) - уменьшение i с 3 до 1 (в 3 раза)

Для следующих квадратов (3x3 и 1x1) мы делаем то же самое, но соответственно сдвигаем начальный и конечный индексы. Я использовал индекс k для каждого концентрического квадрата, есть n // 2 + 1 концентрических квадратов.

Наконец, немного математики для красивой печати.

Чтобы распечатать индексы:

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(n-k-1,k-1,-1):
          ind.append((n-k-1,j))
      for i in range(n-k-2,k-1,-1):
          ind.append((i,j))
      for j in range(k+1,n-k):
          ind.append((i,j))
      for i in range(k+1,n-k-1):
          ind.append((i,j))

    print(ind)

spi_cc(5)

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

import numpy as np
import matplotlib.pyplot as plt

def spiral(m, n):
    M = np.zeros([m, n], dtype=int)
    i, j = 0, 0 # location of "turtle"
    di, dj = 0, 1 # direction of movement
    h = (np.min([m,n]))/2
    for ii in range(m * n):
        M[i, j] = ii
        if (i < h and (i == j+1 or i+1 == n-j)) or (i >= m-h and (m-i == n-j or m-i == j+1)):
            di, dj = dj, -di # turn clockwise
        i, j = i + di, j + dj
    return M

plt.imshow(spiral(16, 24))

Ваш вопрос выглядит как вопрос, называемый спиральной памятью. В этой задаче каждый квадрат в сетке распределяется по спирали, начиная с числа 1, расположенного в начале координат. И затем считая, вращаясь по спирали наружу. Например:

17  16  15  14  13

18   5   4   3  12

19   6   1   2  11

20   7   8   9  10

21  22  23  ---->

Мое решение для вычисления координат каждого числа, следующего за этим спиралевидным узором, размещено ниже:

def spiral_pattern(num):
    x = y = 0
    for _ in range(num-1):
        x, y = find_next(x, y)
    yield (x, y)


def find_next(x, y):
    """find the coordinates of the next number"""
    if x == 0 and y == 0:
        return 1, 0

    if abs(x) == abs(y):
        if x > 0 and y > 0:
            x, y = left(x, y)
        elif x < 0 and y > 0:
            x, y = down(x, y)
        elif x < 0 and y < 0:
            x, y = right(x, y)
        elif x > 0 and y < 0:
            x, y = x+1, y
    else:
        if x > y and abs(x) > abs(y):
            x, y = up(x, y)
        elif x < y and abs(x) < abs(y):
            x, y = left(x, y)
        elif x < y and abs(x) > abs(y):
            x, y = down(x, y)
        elif x > y and abs(x) < abs(y):
            x, y = right(x, y)

    return x, y

def up(x, y):
    return x, y+1


def down(x, y):
    return x, y-1


def left(x, y):
    return x-1, y


def right(x, y):
    return x+1, y

Спираль Kotlin.

data class Point(val x: Int, val y: Int) {
    operator fun plus(p: Point): Point = Point(x + p.x, y + p.y)

    override fun toString() = "($x, $y)"

    companion object {
        enum class Directions(val d: Point) {
            RIGHT(Point(1, 0)),
            UP(Point(0, 1)),
            LEFT(Point(-1, 0)),
            DOWN(Point(0, -1))
        }

        fun spiral() = sequence {
            var p = Point(0, 0)
            // Always start at the origin.
            yield(p)
            // 0, 2, 4, 6 ...
            generateSequence(0) { it + 2 }.forEach { n ->
                // For each of the 4 directions
                Directions.values().forEach { d ->
                    // actual length depends slightly on direction
                    val l = n + when (d) {
                        Directions.RIGHT, Directions.UP -> 1
                        Directions.LEFT, Directions.DOWN -> 2
                    }
                    // run to the next corner
                    for (i in 1..l) {
                        p += d.d
                        yield(p)
                    }
                }
            }
        }
    }
}