math - 确定数字在以 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)