文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
社区首页 >问答首页 >螺旋式循环

问螺旋式循环
EN

Stack Overflow用户
提问于 2008-12-29 18:40:29
回答 34查看 94.9K关注 0票数 170

一个朋友需要一种算法，可以让他遍历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)

​

​

loops
spiral
algorithm
matrix
EN

回答 34

Stack Overflow用户

回答已采纳

发布于 2008-12-29 18:41:38

这是我的解决方案(用Python)：

代码语言：javascript
复制
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
票数 69
EN

Stack Overflow用户

发布于 2009-10-12 15:29:12

C++有没有人？从python快速翻译，为了完整而张贴

代码语言：javascript
复制
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;
    }
}
票数 35
EN

Stack Overflow用户

发布于 2015-11-11 05:22:22

代码语言：javascript
复制
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次迭代的通用解决方案。

代码语言：javascript
复制
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与一个常数的任何乘法简化为另一个常数。这就给我们留下了以下结论。

代码语言：javascript
复制
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，以建立更多的模式。

代码语言：javascript
复制
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循环中执行的步数。

代码语言：javascript
复制
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矩阵的原始问题的正确解决方案。

代码语言：javascript
复制
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)]
票数 22
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：

https://stackoverflow.com/questions/398299

复制
相关文章

相似问题

领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档