首頁(yè) 猿問(wèn) 在螺旋中循環(huán)

在螺旋中循環(huán)

算法算法與數(shù)據(jù)結(jié)構(gòu)

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

在螺旋中循環(huán)一位朋友需要一種算法，可以讓他遍歷NxM矩陣的元素(N和M是奇數(shù))。我想出了一個(gè)解決方案，但我想看看我的同伴們是否能想出一個(gè)更好的解決方案。我把我的解決方案作為這個(gè)問(wèn)題的答案。示例輸出：對(duì)于3x3矩陣，輸出應(yīng)該是：(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)此外，算法應(yīng)該支持非平方矩陣，因此，例如，對(duì)于5x3矩陣，輸出應(yīng)該是：(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 回答

慕尼黑的夜晚無(wú)繁華

TA貢獻(xiàn)1864條經(jīng)驗(yàn) 獲得超6個(gè)贊

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

反對(duì) 回復(fù) 2019-07-12

三國(guó)紛爭(zhēng)

TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超7個(gè)贊

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

反對(duì) 回復(fù) 2019-07-12

慕田峪9158850

TA貢獻(xiàn)1794條經(jīng)驗(yàn) 獲得超8個(gè)贊

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

對(duì)于這個(gè)問(wèn)題，有很多用不同的編程語(yǔ)言編寫(xiě)的解決方案，但是它們似乎都源于相同的復(fù)雜方法。我將考慮一個(gè)更普遍的計(jì)算螺旋的問(wèn)題，它可以用歸納簡(jiǎn)潔地表達(dá)出來(lái)。

大小寫(xiě)：從(0，0)開(kāi)始，向前移動(dòng)1平方，左轉(zhuǎn)，向前移動(dòng)1平方，左轉(zhuǎn)。歸納步驟：向前移動(dòng)n+1平方，左轉(zhuǎn)，向前移動(dòng)n+1平方，左轉(zhuǎn)。

表達(dá)這一問(wèn)題的數(shù)學(xué)優(yōu)雅有力地表明，應(yīng)該有一個(gè)簡(jiǎn)單的算法來(lái)計(jì)算解決方案。請(qǐng)記住，我選擇的不是用特定的編程語(yǔ)言實(shí)現(xiàn)算法，而是將其作為偽代碼來(lái)實(shí)現(xiàn)。

首先，我將考慮一種算法，它使用4對(duì)while循環(huán)來(lái)計(jì)算螺旋的2次迭代。每對(duì)的結(jié)構(gòu)是相似的，但其本身是不同的。這在一開(kāi)始可能看起來(lái)很瘋狂(有些循環(huán)只執(zhí)行一次)，但我將逐步進(jìn)行轉(zhuǎn)換，直到我們到達(dá)4對(duì)相同的循環(huán)，因此可以用放置在另一個(gè)循環(huán)中的單個(gè)循環(huán)替換。這將為我們提供一個(gè)不使用任何條件計(jì)算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

我們將進(jìn)行的第一個(gè)轉(zhuǎn)換是為方向引入一個(gè)新變量d，它包含值+1或-1。方向在每對(duì)回路之后切換。由于我們?cè)谒悬c(diǎn)都知道d的值，所以我們可以用它把每個(gè)不等式的每一面相乘，相應(yīng)地調(diào)整不等式的方向，并將d的任何乘積簡(jiǎn)化為另一個(gè)常數(shù)。這就留給我們以下幾點(diǎn)。

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

現(xiàn)在我們注意到x*d和rhs都是整數(shù)，所以我們可以從rhs中減去0到1之間的任何實(shí)值，而不影響不等式的結(jié)果。為了建立更多的模式，我們選擇從每對(duì)WITH循環(huán)的不等式中減去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

現(xiàn)在，我們可以引入另一個(gè)變量m，用于我們?cè)诿恳粚?duì)while循環(huán)上采取的步驟數(shù)。

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

最后，我們發(fā)現(xiàn)每對(duì)WITH循環(huán)的結(jié)構(gòu)是相同的，可以簡(jiǎn)化為放置在另一個(gè)循環(huán)內(nèi)的一個(gè)循環(huán)。另外，為了避免使用實(shí)數(shù)，我將m的初始值乘以m；值m被增加，并且每個(gè)不等式的兩邊都乘以2。

這將導(dǎo)致答案開(kāi)頭所示的解決方案。

反對(duì) 回復(fù) 2019-07-12