문제
친구에 필요한 알고리즘을 것이다 그에게 반복을 통해 요소의 n×m 개 매트릭스(N M 은 홀수).저는 솔루션을 도출했습니다,하지만 보고 싶었으면 나의 동무'ers 으로 올 수 있는 더 나은 솔루션입니다.
내가 전한 솔루션으로 이 질문에 대답.
를 들어 출력:
에 대한 3x3 행렬 출력해야한다:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)
또한,알고리즘을 지원해야 합 정사각형이 아닌 행렬,그래서 예를 들어에 대한 5x3 행렬 출력해야한다:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)
해결책
다음은 내 솔루션 (파이썬)입니다.
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;
}
}
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 쌍의 루프에 도착할 때까지 다른 루프 안에있는 단일 쌍으로 교체 할 수 있습니다. 이를 통해 조건부를 사용하지 않고도 컴퓨팅의 일반적인 솔루션을 제공합니다.
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
우리가 할 첫 번째 변환은 값 +1 또는 -1을 보유하는 방향에 대한 새로운 변수 d를 도입하는 것입니다. 방향은 각 루프 쌍 후에 전환됩니다. 우리는 모든 시점에서 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 사이의 실제 값을 빼낼 수 있습니다. 우리는 더 많은 패턴을 설정하기 위해 다른 모든 쌍 루프의 불평등에서 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을 소개 할 수 있습니다.
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
마지막으로, 우리는 각 쌍 루프의 구조가 동일하고 다른 루프 내부에 배치 된 단일 루프로 감소 될 수 있음을 알 수 있습니다. 또한 실제 가치가있는 숫자를 사용하지 않기 위해 M의 초기 값을 곱했습니다. 값 m은 증가합니다. 그리고 각 불평등의 양면은 2.
이것은이 답변의 시작 부분에 표시된 솔루션으로 이어집니다.
나는 Python의 발전기를 좋아합니다.
def spiral(N, M):
x,y = 0,0
dx, dy = 0, -1
for dumb in xrange(N*M):
if abs(x) == abs(y) and [dx,dy] != [1,0] or x>0 and y == 1-x:
dx, dy = -dy, dx # corner, change direction
if abs(x)>N/2 or abs(y)>M/2: # non-square
dx, dy = -dy, dx # change direction
x, y = -y+dx, x+dy # jump
yield x, y
x, y = x+dx, y+dy
테스트 :
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) 솔루션입니다. 깡깡이
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;
}
C ++ 변형을 기반으로 Java Spiral "Code Golf"시도.
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;
}
}
다음은 다음 (X, Y) 좌표를 이전 방향으로부터 직접적이고 쉽게 계산할 수 있음을 보여주는 C ++ 솔루션입니다. 현재 방향, 반경 또는 기타 다른 것을 추적 할 필요가 없습니다.
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를 비교하여 정사각형의 측면을 결정할 수 있으며, 어떤 방향으로 들어갈 지 알 수 있다는 것입니다.
Java에서 TDD.
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(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] ]
오픈 소스 라이브러리가 있습니다. 픽셀 스칸, 이것은 다양한 공간 패턴으로 그리드의 픽셀을 스캔하는 기능을 제공하는 파이썬 라이브러리입니다. 포함 된 공간 패턴은 원형, 반지, 그리드, 뱀 및 임의의 산책입니다. 다양한 변환이 있습니다 (예 : 클립, 스왑, 회전, 번역). 원래 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)
라이브러리 생성기 및 변환은 다양한 순서와 공간 패턴으로 포인트를 변경하기 위해 묶을 수 있습니다.
이것은 C에 있습니다.
나는 나쁜 변수 이름을 선택했습니다. 이름으로 t == 상단, l == 왼쪽, b == 하단, r == 오른쪽으로. 따라서 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);
이것은 약간 다른 버전입니다 - 사용하려고합니다. 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
이 문제에 대한 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);
이렇게하면 1 단계로 좌표 (x = 0, y = 0)에서 시작하여 외부 나선형이 생성되고 총 항목 수는 100과 같습니다. 구현은 항상 다음 순서로 이동을 시작합니다. 왼쪽.
이 구현은 정사각형 행렬을 만듭니다.
여기에 답을 줄리아:나의 접근 방식은 할당하는 포인트에서 동심의 사각형('나선형')주위에 원산지 (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
by 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)
다음은 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
줄인 또는 행 색인 등을 의미합니다.)
모든 사각형은 크기와 동일하며 동심 사각형 위로 반복했습니다.
각 정사각형에 대해 코드에는 4 개의 루프 (각 측면에 하나)가 있으며 각 루프에는 열 또는 행 색인이 증가하거나 줄입니다. 만약에 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)
이것은 자신의 솔루션을 기반으로하지만 코너를 찾는 데 더 똑똑 할 수 있습니다. 이렇게하면 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<X or y<Y:
if abs(y)<Y:
for x in range(x, x+side, d):
if abs(x)<X: yield x,y
x += d
else:
x += side
if abs(x)<X:
for y in range(y, y+side, d):
if abs(y)<Y: yield x,y
y += d
else:
y += side
d =-d
side = d-side
Here is my attempt for simple C solution. First print the outer spiral and move one block inside..and repeat.
#define ROWS 5
#define COLS 5
//int A[ROWS][COLS] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {11, 12, 13, 14}, {15, 16, 17, 18} };
//int A[ROWS][COLS] = { {1, 2, 3}, {6, 7, 8}, { 12, 13, 14} };
//int A[ROWS][COLS] = { {1, 2}, {3, 4}};
int A[ROWS][COLS] = { {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15} , {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25} };
void print_spiral(int rows, int cols)
{
int row = 0;
int offset = 0;
while (offset < (ROWS - 1)) {
/* print one outer loop at a time. */
for (int col = offset; col <= cols; col++) {
printf("%d ", A[offset][col]);
}
for (row = offset + 1; row <= rows; row++) {
printf("%d ", A[row][cols]);
}
for (int col = cols - 1; col >= offset; col--) {
printf("%d ", A[rows][col]);
}
for (row = rows - 1; row >= offset + 1; row--) {
printf("%d ", A[row][offset]);
}
/* Move one block inside */
offset++;
rows--;
cols--;
}
printf("\n");
}
int _tmain(int argc, _TCHAR* argv[])
{
print_spiral(ROWS-1, COLS-1);
return 0;
}
이것은 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);
}
실제로 이것을 읽을 수있는 사람에게 안심하십시오
보너스 질문 :이 "알고리즘"의 실행 시간은 무엇입니까? :피
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의 속성에서 캔버스의 너비와 높이를 변경하십시오.
JavaScript에서 재미를 위해 :
function spiral(x, y) {
var iy = ix = 0
, hr = (x - 1) / 2
, vr = (y - 1) / 2
, tt = x * y
, matrix = []
, step = 1
, dx = 1
, dy = 0;
while(matrix.length < tt) {
if((ix <= hr && ix >= (hr * -1)) && (iy <= vr && (iy >= (vr * -1)))) {
console.log(ix, iy);
matrix.push([ix, iy]);
}
ix += dx;
iy += dy;
// check direction
if(dx !== 0) {
// increase step
if(ix === step && iy === (step * -1)) step++;
// horizontal range reached
if(ix === step || (ix === step * -1)) {
dy = (ix === iy)? (dx * -1) : dx;
dx = 0;
}
} else {
// vertical range reached
if(iy === step || (iy === step * -1)) {
dx = (ix === iy)? (dy * -1) : dy;
dy = 0;
}
}
}
return matrix;
}
var sp = spiral(5, 3);
C# 버전, 비 제곱 크기도 처리합니다.
private static Point[] TraverseSpiral(int width, int height) {
int numElements = width * height + 1;
Point[] points = new Point[numElements];
int x = 0;
int y = 0;
int dx = 1;
int dy = 0;
int xLimit = width - 0;
int yLimit = height - 1;
int counter = 0;
int currentLength = 1;
while (counter < numElements) {
points[counter] = new Point(x, y);
x += dx;
y += dy;
currentLength++;
if (dx > 0) {
if (currentLength >= xLimit) {
dx = 0;
dy = 1;
xLimit--;
currentLength = 0;
}
} else if (dy > 0) {
if (currentLength >= yLimit) {
dx = -1;
dy = 0;
yLimit--;
currentLength = 0;
}
} else if (dx < 0) {
if (currentLength >= xLimit) {
dx = 0;
dy = -1;
xLimit--;
currentLength = 0;
}
} else if (dy < 0) {
if (currentLength >= yLimit) {
dx = 1;
dy = 0;
yLimit--;
currentLength = 0;
}
}
counter++;
}
Array.Reverse(points);
return points;
}
다른 목적을 위해 설계된이 코드를 공유하고 있습니다. 열 번호 "x"및 배열 요소 "y"의 열 번호 "y"를 찾는 것입니다. 이 함수는 행렬의 너비 "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 루핑 시계 방향 나선형 코드 사용 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
VB.net에서 Davidont의 우수한 솔루션
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
이것은 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);
}