3

0 を中心としてらせん状に増加する次の数字のグリッドがあります。スパイラルで数値を受け取り、x を返すアルゴリズムが必要です。y - 0 からその番号に到達するまでの移動回数。たとえば、番号 9 の場合は -2 を返します。-1. 4 の場合は 1 になります。1.

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

このスパイラルは、アルゴリズムの改善に役立つ場合は、わずかに変更できます。好きな言語を使用してください。数学的な説明をいただければ幸いです。

ありがとうございました。

4

2 に答える 2

5

最初に、どのサイクル (中心からの距離) とセクター (北、東、南、または西) を決定する必要があります。次に、数値の正確な位置を決定できます。

  • 各サイクルの最初の数値は次のとおりです。1, 9, 25

  • これは 2 次シーケンスです。first(n) = (2n-1)^2 = 4n^2 - 4n + 1

  • これの逆はサイクル数です:cycle(i) = floor((sqrt(i) + 1) / 2)

  • サイクルの長さは次のとおりです。length(n) = first(n+1) - first(n) = 8n

  • セクターは次のようになります。
    sector(i) = floor(4 * (i - first(cycle(i))) / length(cycle(i)))

  • 最後に、位置を取得するには、サイクルとセクターの最初の数値の位置から外挿する必要があります。

すべてをまとめるには：

def first(cycle):
    x = 2 * cycle - 1
    return x * x

def cycle(index):
    return (isqrt(index) + 1)//2

def length(cycle):
    return 8 * cycle

def sector(index):
    c = cycle(index)
    offset = index - first(c)
    n = length(c)
    return 4 * offset / n

def position(index):
    c = cycle(index)
    s = sector(index)
    offset = index - first(c) - s * length(c) // 4
    if s == 0: #north
        return -c, -c + offset + 1
    if s == 1: #east
        return -c + offset + 1, c
    if s == 2: #south
        return c, c - offset - 1
    # else, west
    return c - offset - 1, -c

def isqrt(x):
    """Calculates the integer square root of a number"""
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

例：

>>> position(9)
(-2, -1)
>>> position(4)
(1, 1)
>>> position(123456)
(-176, 80)
于 2012-07-18T22:28:54.367 に答える
1

このような意味ですか？私はアルゴリズムを実装していませんでしたが、コードはより適切に記述できますが、それは機能します-それは常に開始です:)必要に応じてしきい値を変更するだけで、結果が得られます。

static int threshold=14, x=0, y=0;

    public static void main(String[] args) {

        int yChange=1, xChange=1, count=0;
        while( !end(count) ){

            for (int i = 0; i < yChange; i++) {
                if( end(count) )return;
                count++;
                y--;
            }
            yChange++;
            for (int i = 0; i < xChange; i++) {
                if( end(count) )return;
                count++;
                x++;
            }
            xChange++;
            for (int i = 0; i < yChange; i++) {
                if( end(count) )return;
                count++;
                y++;
            }
            yChange++;
            for (int i = 0; i < xChange; i++) {
                if( end(count) )return;
                count++;
                x--;
            }
            xChange++;

        }

    }

    public static boolean end(int count){
        if(count<threshold){
            return false;
        }else{
            System.out.println("count: "+count+", x: "+x+", y: "+y);
            return true;
        }
    }
于 2012-07-18T21:57:51.837 に答える