一位朋友需要一种算法让他循环遍历NxM矩阵的元素(N和M是奇数).我提出了一个解决方案,但我想知道我的同事是否可以提出更好的解决方案.
我发布我的解决方案作为这个问题的答案.
示例输出:
对于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)
这是我的解决方案(在Python中):
def spiral(X, Y):
x = y = 0
dx = 0
dy = -1
for i in range(max(X, Y)**2):
if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2):
print (x, y)
# DO STUFF...
if x == y or (x < 0 and x == -y) or (x > 0 and x == 1-y):
dx, dy = -dy, dx
x, y = x+dx, y+dy
C++有人吗？从python快速翻译,发布完整性
void Spiral( int X, int Y){
int x,y,dx,dy;
x = y = dx =0;
dy = -1;
int t = std::max(X,Y);
int maxI = t*t;
for(int i =0; i < maxI; i++){
if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)){
// DO STUFF...
}
if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))){
t = dx;
dx = -dy;
dy = t;
}
x += dx;
y += dy;
}
}
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
我们现在可以为每对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.
这导致了本答案开头所示的解决方案.
我喜欢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;
}
Java螺旋式"Code golf"尝试,基于C++变体.
public static void Spiral(int X, int Y) {
int x=0, y=0, dx = 0, dy = -1;
int t = Math.max(X,Y);
int maxI = t*t;
for (int i=0; i < maxI; i++){
if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)) {
System.out.println(x+","+y);
//DO STUFF
}
if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))) {
t=dx; dx=-dy; dy=t;
}
x+=dx; y+=dy;
}
}
这是一个C++解决方案,它显示您可以直接轻松地计算下一个(x,y)坐标 - 无需跟踪当前方向,半径或其他任何内容:
void spiral(const int M, const int N)
{
// Generate an Ulam spiral centered at (0, 0).
int x = 0;
int y = 0;
int end = max(N, M) * max(N, M);
for(int i = 0; i < end; ++i)
{
// Translate coordinates and mask them out.
int xp = x + N / 2;
int yp = y + M / 2;
if(xp >= 0 && xp < N && yp >= 0 && yp < M)
cout << xp << '\t' << yp << '\n';
// No need to track (dx, dy) as the other examples do:
if(abs(x) <= abs(y) && (x != y || x >= 0))
x += ((y >= 0) ? 1 : -1);
else
y += ((x >= 0) ? -1 : 1);
}
}
如果您要做的只是生成螺旋中的前N个点(没有原始问题的掩蔽到N x M区域的约束),则代码变得非常简单:
void spiral(const int N)
{
int x = 0;
int y = 0;
for(int i = 0; i < N; ++i)
{
cout << x << '\t' << y << '\n';
if(abs(x) <= abs(y) && (x != y || x >= 0))
x += ((y >= 0) ? 1 : -1);
else
y += ((x >= 0) ? -1 : 1);
}
}
诀窍在于你可以比较x和y来确定你所在方块的哪一侧,并告诉你要移动的方向.
TDD，使用Java。
SpiralTest.java：
import java.awt.Point;
import java.util.List;
import junit.framework.TestCase;
public class SpiralTest extends TestCase {
public void test3x3() throws Exception {
assertEquals("(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)", strung(new Spiral(3, 3).spiral()));
}
public void test5x3() throws Exception {
assertEquals("(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)",
strung(new Spiral(5, 3).spiral()));
}
private String strung(List points) {
StringBuffer sb = new StringBuffer();
for (Point point : points)
sb.append(strung(point));
return sb.toString().trim();
}
private String strung(Point point) {
return String.format("(%s, %s) ", point.x, point.y);
}
}
Spiral.java：
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
public class Spiral {
private enum Direction {
E(1, 0) {Direction next() {return N;}},
N(0, 1) {Direction next() {return W;}},
W(-1, 0) {Direction next() {return S;}},
S(0, -1) {Direction next() {return E;}},;
private int dx;
private int dy;
Point advance(Point point) {
return new Point(point.x + dx, point.y + dy);
}
abstract Direction next();
Direction(int dx, int dy) {
this.dx = dx;
this.dy = dy;
}
};
private final static Point ORIGIN = new Point(0, 0);
private final int width;
private final int height;
private Point point;
private Direction direction = Direction.E;
private List list = new ArrayList();
public Spiral(int width, int height) {
this.width = width;
this.height = height;
}
public List spiral() {
point = ORIGIN;
int steps = 1;
while (list.size() < width * height) {
advance(steps);
advance(steps);
steps++;
}
return list;
}
private void advance(int n) {
for (int i = 0; i < n; ++i) {
if (inBounds(point))
list.add(point);
point = direction.advance(point);
}
direction = direction.next();
}
private boolean inBounds(Point p) {
return between(-width / 2, width / 2, p.x) && between(-height / 2, height / 2, p.y);
}
private static boolean between(int low, int high, int n) {
return low <= n && n <= high;
}
}
京公网安备 11010802040832号 | 京ICP备19059560号-6 