确定数字在以0为中心并以螺旋递增的数字网格中的位置 [英] Determine position of number in a grid of numbers centered around 0 and increasing in spiral

问题描述

我得到了以下以0为中心并呈螺旋形增长的数字网格.我需要一种算法，该算法将接收螺旋数并返回x；y-从0到该数字的移动次数.例如，对于数字9，它将返回-2；对于数字9，它将返回-2.-1.对于4，它将为1；对于4，将为1.1.

I've got the following grid of numbers centered around 0 and increasing in spiral. I need an algorithm which would receive number in spiral and return x; y - numbers of moves how to get to that number from 0. For example for number 9 it would return -2; -1. For 4 it would be 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

如果可以帮助改进算法，则可以稍微改变此螺旋.使用您喜欢的任何语言.我真的很感谢数学解释.

This spiral can be slightly changed if it would help the algorithm to be better. Use whatever language you like. I would really appreciate mathematical explanation.

谢谢.

推荐答案

首先，我们需要确定我们所在的周期(与中心的距离)和扇区(北，东，南或西).数字的位置.

First we need to determine which cycle (distance from center) and sector (north, east, south or west) we are in. Then we can determine the exact position of the number.

• 每个周期中的第一个数字如下: 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)))

最后，要获取位置，我们需要从循环和扇区中第一个数字的位置推断出来.

Finally, to get the position, we need to extrapolate from the position of the first number in the cycle and sector.

将它们放在一起:

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)

这篇关于确定数字在以0为中心并以螺旋递增的数字网格中的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！