旋转队列的简要分析

看到了一道关于旋转队列的题目，觉得蛮有意思的，虽然仅仅是一个数值处理问题，但是寻找规律的过程还是蛮有意思的，关于旋转队列的实现也已经有了很多的版本，我就其中的一种做简要的分析和总结。

 

题目大概如下所示：

设1点的坐标是(0,0)，x方向向右为正，y方向向下为正。例如：7的坐标为(-1,-1)，2的坐标为(1,0)，3的坐标为(1,1)。编程实现输入任意一点坐标(x,y)，输出所对应的数字；或输入任意数字，输出该数字的坐标。实现的效果如上图所示，从图中可知，只需要找到正确的数值分析式，就能够得到坐标处对应的数值。

 

下面简要的分析其中的一些规律，这类问题我觉得关键还是要找到突破点，然后找到具体数值的表达式，表达式清楚了就只是程序的转化问题啦。

 

从图上可知，在第0层时只有一个值1，第1层是有8个值（2-9）,第2层上的值从10到25，第3层的值从26到49，由图可知每一层的最后一个值都是奇数的平方（1,9,25,49,81,...）,再和层数关联起来，得到每一层的最后一个数都是(2n+1)^2,同样每一层的起始值也就可以确定，即(2n-1)^2+1。也就是每一层的值都是处在(2n-1)^2+1和(2n+1)^2之间，这样采用(2n-1)^2作为一个基准，加上对应的数就能得到具体的数值。

 

因此我们可以得到如下的结论：

 

旋转队列每一层的开始值都是(2n-1)^2+1,结尾值都是(2n+1)^2,其中的n就是层数（0,1,2,...）,可以认为是坐标中较大的绝对值值确定所在的层，比如(2,3),则表示该坐标处于第3层，而（-3，-2）也表示这个数值在第3层上。有了这种层的概念就会使得推理的过程更见的简单。也就是说坐标值中绝对值较大的值就是所谓的层。

 

结合上面的图像可知道，每一层的开始值都是出于东方，也就是x>0的方向，结束于北方，即y<0的方向，这时候我们可以根据东西南北四个方向来确定坐标对应的值。

 

即：首先采用输入的坐标值确定该数值对应的层数，然后根据输入坐标的x,y确定坐标所在的方向，这时候依据每一个方向的起始值就能较好的确定所有的值（具体分析该值与每一层的开始值之间的联系），但是这种方法有问题，因为每一层上每个方向（东西南北）的起始坐标都是在变化的，并不便于得到通用的表达式。

 

这时候可以考虑对称性问题，因为在上面的图中我们可以知道该图基本上是按照x,y对称的，如果我们知道了四个正方向的值，那么就能根据对称性快速的确定其他的值，也就是只需要知道每一层与坐标轴相交的几个值就能快速的确定其他的值。

 

但是如何让确定坐标轴上的值呢？

 

这就要密切联系每一层的结束值(2n+1)^2，根据这个值我们可以知道下一层正东方的值(2n+1)^2+n+1,加入坐标所在的层为K,则正东方的值就应该是(2*K-1)^2+K,这个可以很容易的确定，因为开始值到坐标轴的距离刚好就是层数K,也就是加上K。其他三个方向的值也就能够快速的确定。

 

因此我们可以知道每一个方向的对称轴的表达式分别为：

 

正东方：（2*K-1)^2+K

正南方：（2*K-1)^2+3K

正西方：（2*K-1)^2+5K

正北方：（2*K-1)^2+7K

 

依据每一个方向的坐标轴的对称性确定对应的值，在对称的方向上只需要一个坐标值就能确定其他的值，这时候四个方向上的值分别为：

 

东方：（2*K-1)^2 + K + y

南方：（2*K-1)^2 + 3K - x

西方：（2*K-1)^2 + 5K - y

北方：（2*K-1)^2 + 7K + x

 

这样也就找到了每一行的表达式，就能实现每一个方向上数值的确定。程序的实现也就相对来说非常容易实现啦。在打印的过程中需要注意数组行列的差别。

 

实现的基本过程如下：

#include<iostream>
#include<string>

using namespace std;

#define abs(x) ((x) > 0 ? (x) : (-x))
#define max(x,y) (abs(x) >= abs(y) ? abs(x) : abs(y))

int reverse_xy(int x, int y)
{
        int cnt = 0;

        /*保存所在的行*/
        int t = max(x, y);

        /*最先判断北方(y=-t)*/
        if(-t == y)
        {
                cnt = (2*t-1)*(2*t-1) + 7*t + x;
        }
        else if(-t == x)/*西方*/
        {
                cnt = (2*t-1)*(2*t-1) + 5*t - y;
        }
        else if(t == y)/*南方*/
        {
                cnt = (2*t-1)*(2*t-1) + 3*t - x;
        }
        else if(t == x)/*东方*/
        {
                cnt = (2*t-1)*(2*t-1) + t + y;
        }

        return cnt;
}

int main()
{
        int array[9][9] = {0};

        int x = 0;
        int y = 0;

        for(y = 0; y <= 8 ; ++ y)
        {
                for(x = 0; x <= 8; ++ x)
                {
                        array[x][y] = reverse_xy(x-4 , y-4);
                        cout << array[x][y] << "\t";
                }
                cout << endl;
        }
}