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