确定数字在以 0 为中心并螺旋增加的数字网格中的位置

Question

我有以下数字网格，以 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

如果可以帮助算法变得更好，可以稍微改变这个螺旋。使用您喜欢的任何语言。我真的很感激数学解释。

谢谢。

Answer 1

首先我们需要确定我们处于哪个周期（距中心的距离）和扇区（北、东、南或西）。然后我们可以确定数字的确切位置。

• 每个周期的第一个数字如下：1, 9, 25

• 这是一个二次序列：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)