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

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