친구에게는 NxM 행렬의 요소를 반복 할 수있는 알고리즘이 필요했습니다 (N과 M이 홀수 임). 나는 해결책을 찾았지만 동료 SO’ers가 더 나은 해결책을 찾을 수 있는지 알고 싶었다.
이 질문에 대한 답변으로 솔루션을 게시하고 있습니다.
출력 예 :
3×3 행렬의 경우 출력은 다음과 같아야합니다.
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1 )
또한이 알고리즘은 비 제곱 행렬을 지원해야하므로 예를 들어 5×3 행렬의 경우 출력은 다음과 같아야합니다.
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1 ) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)
답변
내 솔루션은 다음과 같습니다 (파이썬).
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 ++ 누군가? 완전성을 위해 게시 된 파이썬에서 빠른 번역
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 사이의 실제 값을 뺄 수 있습니다. 더 많은 패턴을 설정하기 위해 다른 모든 한 쌍의 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
이제 각 while 루프 쌍에서 수행하는 단계 수에 대해 다른 변수 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
마지막으로, 각 한 쌍의 while 루프의 구조는 동일하며 다른 루프 안에 배치 된 단일 루프로 축소 될 수 있습니다. 또한 실제 숫자를 사용하지 않기 위해 m의 초기 값을 곱했습니다. 값 m은 증분된다; 각 불평등의 양쪽에 2 씩
이것은이 답변의 시작 부분에 표시된 솔루션으로 이어집니다.
답변
다음은 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;
}
답변
나는 파이썬 생성기를 좋아합니다.
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 ++ 변형을 기반으로하는 Java 나선형 “코드 골프”시도.
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를 비교하여 현재 사각형의 어느 쪽을 결정하고 어떤 방향으로 이동 할지를 알려줍니다.
