循环往复 - 开卷题库

小开

最佳答案

以下是我的解决方案(使用 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}),"
}

小开

Haskell 随你挑:

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)

小开

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

小开

这是基于你自己的解决方案，但我们可以更聪明地找到角落。这样，如果 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);
}

真正能看懂这本书的人都可以得到奖励

附加问题: 这个“算法”的运行时间是多少

小开

这是一个稍微不同的版本-尝试在 LUA 中使用 recursion和 iterators。在每个步骤中，程序在矩阵和循环中进一步下降。我还增加了一个额外的旗帜螺旋 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.log("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.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/上工作。只要确保在 javascript vars 和 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 × 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 来确定你所在的正方形的哪一边，然后告诉你移动的方向。

小开

我有一个开放源码库 < a href = “ https://github.com/dpmcmlxvi/pixelscanner”rel = “ nofollow”> pixelscanner ，它是一个 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)

可以将库生成器和转换链接起来，以便在各种各样的顺序和空间模式中更改点。

小开

只是为了好玩:

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

小开

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


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

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

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

表达这个问题的数学优雅强烈建议应该有一个简单的算法来计算解决方案。为了保持抽象性，我选择不在特定的编程语言中实现算法，而是作为伪代码。

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

let x = 0
let y = 0


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


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


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


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

我们将要进行的第一个转换是引入一个新的变量 d，用于表示方向，它包含值 + 1或 -1。方向在每对环之后切换。既然我们知道 d 在所有点上的值，我们可以用它来乘以每个不等式的每一边，相应地调整不等式的方向，并将 d 乘以一个常数简化为另一个常数。我们还剩下以下几个问题。

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


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


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


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


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

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

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


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


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


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


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

现在我们可以引入另一个变量 m，表示我们在每对 while 循环中执行的步骤数。

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


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


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


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


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

最后，我们看到每对 while 循环的结构是相同的，可以简化为放置在另一个循环内的单个循环。另外，为了避免使用实值数字，我将 m 的初始值乘以; ，m 的值增加了; ，每个不等式的两边都增加了2。

这导致了在这个答案的开头显示的解决方案。

编辑: 已经有几年了，但是我有一个类似的问题，并且写了下面的解决方案在 F # ，我想分享。在我最初的回答中，print 这个词可能用词不当，但是希望这个非伪代码版本能够解决注释中提到的有关通用性和终止条件的任何问题。我已经添加了一些示例用例，用于在任意点上进行螺旋运动，并为迭代 NxM 矩阵找到原始问题的正确解决方案。

let spiral =
let rec f (x, y) d m = seq {
let mutable x = x
let mutable y = y
while 2 * x * d < m do
yield x, y
x <- x + d
while 2 * y * d < m do
yield x, y
y <- y + d
yield! f (x, y) -d (m + 1)
}
f (0, 0) 1 1


spiral
|> Seq.take 5
|> List.ofSeq;;
// [(0, 0); (1, 0); (1, 1); (0, 1); (-1, 1)]


spiral
|> Seq.take 5
|> Seq.map (fun (x, y) -> x + 5, y + 5)
|> List.ofSeq;;
// [(5, 5); (6, 5); (6, 6); (5, 6); (4, 6)]


spiral
|> Seq.takeWhile (fun (x, y) -> x * x + y * y < 9)
|> Seq.filter (fun (x, y) -> -2 <= x && x <= 2 && -1 <= y && y <= 1)
|> List.ofSeq;;
// [(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 # 版本，也可以处理非正方形大小。

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”的数组元素@螺旋索引“索引”。这个函数接受矩阵的宽度“ w”和高度“ h”，以及所需的“ index”。当然，这个函数可以用来生成相同的所需输出。我认为这是最快的可能的方法(因为它跳过细胞而不是扫描它们)。

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

小开

使用 Berk Güder 能回答吗的 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.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);

这将创建一个向外的螺旋，从坐标(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

小开

Julia 给出了一个答案: 我的方法是在原点 (0,0)周围的同心方块(‘螺旋线’)中分配点，每个方块都有边长 m = 2n + 1，生成一个有序的字典，位置编号(从原点1开始)作为键，相应的坐标作为值。

由于每个螺旋的最大位置是在 (n,-n)，其余的点可以通过从这个点向后工作来找到，即从右下角的 m-1单位，然后对于 m-1单位的垂直3段重复。

这个过程是按照下面的倒序写的，对应的是螺旋进程而不是这个反向计数过程，即 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)
}
}
}
}
}
}