首頁猿問在螺旋中循環

在螺旋中循環

算法算法與數據結構

慕后森 2019-07-12 18:30:42

在螺旋中循環一位朋友需要一種算法，可以讓他遍歷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)

查看完整描述

3 回答

慕尼黑的夜晚無繁華

TA貢獻1864條經驗獲得超6個贊

下面是我的解決方案(在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

反對回復 2019-07-12

三國紛爭

TA貢獻1804條經驗獲得超7個贊

有人嗎？從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;
    }}

反對回復 2019-07-12

慕田峪9158850

TA貢獻1794條經驗獲得超7個贊

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之間的任何實值，而不影響不等式的結果。為了建立更多的模式，我們選擇從每對WITH循環的不等式中減去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

最后，我們發現每對WITH循環的結構是相同的，可以簡化為放置在另一個循環內的一個循環。另外，為了避免使用實數，我將m的初始值乘以m；值m被增加，并且每個不等式的兩邊都乘以2。

這將導致答案開頭所示的解決方案。

反對回復 2019-07-12

3 回答
0 關注
613 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

在螺旋中循環

在螺旋中循環

3 回答

添加回答