螺旋队列

Apr 15, 2019

Coding

Algorithm

问题 #

21  22  …
20  7   8   9   10
19  6   1   2   11
18  5   4   3   12
17  16  15  14  13

看清以上数字排列的规律，设 1 点的坐标是 (0,0)，x 方向向右为正，y 方向向下为正。例如，7 的坐标为 (-1,-1)，2 的坐标为 (0,1)，3 的坐标为 (1,1)。编程实现输入任意一点坐标 (x,y)，输出所对应的数字。

分析 #

以(0,0) 即数字 1 为中心，螺旋的形式如图

圆心为第0圈，往外为第1圈，再往外为第2圈，依次类推

每一圈数字的右上角的点p, 它的数值是可以推导出来的

n = 0  -> p = 1   即 (2 * 0 + 1) ^ 2
n = 1  -> p = 9   即 (2 * 1 + 1) ^ 2
n = 2  -> p = 25  即 (2 * 2 + 1) ^ 2

所以，第n圈，右上角的数值为 p = (2n+1)^2，故而，

p1 = p – n
p2 = p – 3n
p3 = p – 5n
p4 = p – 7n

知道了以上点的数值之后，就可以计算任意一点(x,y)处的数值了。

代码 #

// 螺旋队列

package main
import "fmt"

func getAbs(x int) int {
    if x > 0 {
        return x
    }
    return -x
}

func getMax(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func GetValue(x,y int) int {

    // x,y 中较大的值，就是(x,y)所在的圈数
    n := getMax(x,y)

    p := (2 * n + 1) * (2 * n + 1)
    p1 := p - n
    p2 := p - 3 * n
    p3 := p - 5 * n
    p4 := p - 7 * n

    if x == n {
        return p4 + y
    }

    if x == -n {
        return p2 - y
    }

    if y == n {
        return p1 + x
    }

    if y == -n {
        return p3 - x
    }

    return 0
}

func main(){
   fmt.Printf("%v\n", GetValue(0,0))
   fmt.Printf("%v\n", GetValue(1,1))
   fmt.Printf("%v\n", GetValue(10,10))
}