9

長方形のタイル状のらせんのn番目の要素を取得するためのアルゴリズムは何ですか？

ここにありnます：

[ 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とおりです。

[-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]

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

4

6 に答える 6

5

これは JavaScript のコードです。真ん中の番号1から始まる2Dマトリックスの位置を計算します（0、0）

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)];
}
于 2016-12-27T18:59:47.527 に答える
2

まず、目的の要素がどのリングにあるかを調べます (ヒント: 外側のリングに到達するまで、スパイラルはネストされた正方形で構成されています)。次に、(4 つの) どちら側にあるかを調べます。その側の位置で。

于 2012-04-10T19:00:34.547 に答える
1

同様の質問がすでに存在します...私の非ループバージョンを参照してください。100必要な方向と原点に0応じて、X/Y 座標を交換および/または否定し、 を に変更する必要がある場合があります。

より標準的なループ バージョンもあります。

于 2012-04-10T19:06:35.900 に答える
1

誰も答えなかったので、解決策があります：

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/は、これが 1/4 平方整数シーケンスであることを示しています。したがって、必要なのは、各反復がステップをシミュレートし、位置に方向を追加し、ステップ カウントがシーケンスの一部である場合に 90° 回転するループだけです。

于 2012-04-10T22:50:47.947 に答える