長方形のタイル状のらせんの位置n番目の要素を探しますか？

Question

長方形のタイル状スパイラルのn番目の要素を取得するアルゴリズムとは何ですか？ここで

はnです：n与えられた場合は座標を計算する方法を、

[-2,2 ][-1,2 ][ 0,2 ][ 1,2 ][ 2,2 ] 
[-2,1 ][-1,1 ][ 0,1 ][ 1,1 ][ 2,1 ] 
[-2,0 ][-1,0 ][ 0,0 ][ 1,0 ][ 2,0 ] 
[-2,-1][-1,-1][ 0,-1][ 1,-1][ 2,-1] 
[-2,-2][-1,-2][ 0,-2][ 1,-2][ 2,-2] 

：

[ 20 ][ 21 ][ 22 ][ 23 ][ 24 ] 
[ 19 ][ 6 ][ 7 ][ 8 ][ 9 ] 
[ 18 ][ 5 ][ 0 ][ 1 ][ 10 ] 
[ 17 ][ 4 ][ 3 ][ 2 ][ 11 ] 
[ 16 ][ 15 ][ 14 ][ 13 ][ 12 ] 

、ここではnのために、対応する座標でありますか？

Answer 1

ここはJavaScriptのコードです。真中（0、0）の番号1から始まる2次元行列の位置を計算する

13 12 11 10 25 
14 3 2 9 24 
15 4 1 8 23 
16 5 6 7 22 
17 18 19 20 21 

/** 
* Finds coordinates (position) of the number 
* 
* @param {Number} n - number to find position/coordinates for 
* @return {Number[]} - x and y coordinates of the number 
*/ 
function position(n) { 
    const k = Math.ceil((Math.sqrt(n) - 1)/2); 
    let t = 2 * k + 1; 
    let m = Math.pow(t, 2); 

    t -= 1; 

    if (n >= m - t) { 
     return [k - (m - n), -k]; 
    } 

    m -= t; 

    if (n >= m - t) { 
     return [-k, -k + (m - n)]; 
    } 

    m -= t; 

    if (n >= m - t) { 
     return [-k + (m - n), k]; 
    } 

    return [k, k - (m - n - t)]; 
} 

Answer 2

最初に、あなたが望む要素がどこにあるのかを知る（ヒント：外側のリングに到達するまで、あなたのスパイラルはネストされた四角で構成されます）。その側にその位置が残っているだけです。

Answer 3

同様の質問は既に存在します... non-looping versionを参照してください。 X/Y座標を入れ替えたり、無効にしたり、を0に変更する必要があるかもしれません。

さらに標準のlooping versionsがあります。

Answer 4

誰も答えていないと、解決策があります：

def square_spiral(total_steps): 
    position = (0,0) 
    direction = (1,0) 
    turn_steps = [floor(((x+2)**2)/4) for x in range(n+2)] 
    for step in range(total_steps): 
     if (step in turn_steps): 
      direction = (-direction[1],direction[0]) 
     position = tuple(a+b for a,b in zip(position,direction)) 
    return position 

これは、所望の経路を通って散歩をシミュレートします。スパイラルに続いて、ポジション（0,0）から始まり、右に1ステップ、下に1ステップ、左に3ステップ、上に3ステップなどを歩きます。これをコードするには、番号1,2,4,6,9,12,16,20などのステップで方向を変えていることに注意してください。 https://oeis.org/は、これが四分の一整数列であることを示しています。だから、私たちが必要とするのは、各反復がステップをシミュレートし、その位置に方向を追加し、ステップ数がシーケンスの一部であるときにそれを90°回転させるループです。

Answer 5

ここ8の逆数の和を使用してJavaScriptで私の解決策だとエッジ番号

複雑さ：O（1）無反復ループ

function spiral(n) { 
    // given n an index in the squared spiral 
    // p the sum of point in inner square 
    // a the position on the current square 
    // n = p + a 

    var r = Math.floor((Math.sqrt(n + 1) - 1)/2) + 1; 

    // compute radius : inverse arithmetic sum of 8+16+24+...= 
    var p = (8 * r * (r - 1))/2; 
    // compute total point on radius -1 : arithmetic sum of 8+16+24+... 

    en = r * 2; 
    // points by edge 

    var a = (1 + n - p) % (r * 8); 
    // compute de position and shift it so the first is (-r,-r) but (-r+1,-r) 
    // so square can connect 

    var pos = [0, 0]; 
    switch (Math.floor(a/(r * 2))) { 
     // find the face : 0 top, 1 right, 2, bottom, 3 left 
     case 0: 
      { 
       pos[0] = a - r; 
       pos[1] = -r; 
      } 
      break; 
     case 1: 
      { 
       pos[0] = r; 
       pos[1] = (a % en) - r; 

      } 
      break; 
     case 2: 
      { 
       pos[0] = r - (a %en); 
       pos[1] = r; 
      } 
      break; 
     case 3: 
      { 
       pos[0] = -r; 
       pos[1] = r - (a % en); 
      } 
      break; 
    } 
    console.log("n : ", n, " r : ", r, " p : ", p, " a : ", a, " --> ", pos); 
    return pos; 
} 

デモ：Fiddle

Answer 6

はここで短いと甘い答えです擬似コードで単純な数学を使うだけです。条件付きも反復もありません。

intRoot=int(sqrt(tileNum)); 

x=(round(intRoot/2)*(-1^(intRoot+1)))+((-1^(intRoot+1))*(((intRoot*(intRoot+1))-tileNum)-abs((intRoot*(intRoot+1))-tileNum))/2); 

y=(round(intRoot/2)*(-1^intRoot))+((-1^(intRoot+1))*(((intRoot*(intRoot+1))-tileNum)+abs((intRoot*(intRoot+1))-tileNum))/2); 

Here's a fiddleアクションでそれを見るために：タイル番号がためにtileNum考えます。