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

在螺旋中循環(huán)

Android

犯罪嫌疑人X 2019-08-03 13:03:08

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

拉風(fēng)的咖菲貓

TA貢獻(xiàn)1995條經(jīng)驗獲得超2個贊

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

反對回復(fù) 2019-08-05

BIG陽

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

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

反對回復(fù) 2019-08-05

繁星淼淼

TA貢獻(xiàn)1775條經(jīng)驗獲得超11個贊

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

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

大小寫：從(0，0)開始，向前移動1平方，左轉(zhuǎn)，向前移動1平方，左轉(zhuǎn)。歸納步驟：向前移動n+1平方，左轉(zhuǎn)，向前移動n+1平方，左轉(zhuǎn)。

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

首先，我將考慮一種算法，它使用4對while循環(huán)來計算螺旋的2次迭代。每對的結(jié)構(gòu)是相似的，但其本身是不同的。這在一開始可能看起來很瘋狂(有些循環(huán)只執(zhí)行一次)，但我將逐步進(jìn)行轉(zhuǎn)換，直到我們到達(dá)4對相同的循環(huán)，因此可以用放置在另一個循環(huán)中的單個循環(huán)替換。這將為我們提供一個不使用任何條件計算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)行的第一個轉(zhuǎn)換是為方向引入一個新變量d，它包含值+1或-1。方向在每對回路之后切換。由于我們在所有點都知道d的值，所以我們可以用它把每個不等式的每一面相乘，相應(yīng)地調(diào)整不等式的方向，并將d的任何乘積簡化為另一個常數(shù)。這就留給我們以下幾點。

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之間的任何實值，而不影響不等式的結(jié)果。為了建立更多的模式，我們選擇從每對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)在，我們可以引入另一個變量m，用于我們在每一對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)每對WITH循環(huán)的結(jié)構(gòu)是相同的，可以簡化為放置在另一個循環(huán)內(nèi)的一個循環(huán)。另外，為了避免使用實數(shù)，我將m的初始值乘以m；值m被增加，并且每個不等式的兩邊都乘以2。

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

反對回復(fù) 2019-08-05