原创螺旋队列算法分析

 2011-9-5 13:58  2176 4 4 分类: 软件与OS

http://blog.csdn.net/yhmhappy2006/article/details/2934435

螺旋队列的样子如下图：
 
 
 
两大规律：
1。螺旋规律（红线）
2。奇数平方规律（紫线）
 
问题描述：
 
设1的坐标是（0，0），的方向向右为正，y方向向下为正，例如，7的坐标为（-1，-1），
2的坐标为（0，1）。编程实现输入任意一点坐标（x，y），输出所对应的数字！
 
 
问题解决：
从紫线突破。从图中不难发现，右上角vc=(2*t+1)(2*t+1),t为该圈x,y坐标的绝对值的最大值。例如vc=9、25、49、81........，算出vc后，就分4个判断区域，分别判断，点落在该圈4条边的哪条边上，从而计算出具体坐标点的值。
四个区域划分如下图：
 
 
4个区域内4条边上的值u与vc的对应关系为：
y=-t区：u = vc+(x+y);
x=-t区：u = vc+(3*x-y);
y=t区：u = vc + (-x - 5*y);
x=t区：u = vc+(-7*x+y);
 
那么这些关系是怎么得出来的呢？再看图中画上圈的数字：
 
 
在y=-t区，y坐标不变，x坐标变化步长为1。令x=0，此时，u=vc+y作为该边的基准值，其他值随x的变化而变化，得在该区域u=vc+(x+y)；
同理，在x=-t区，x坐标不变，y坐标变化步长为1。令y=0，此时，u=vc+3*x作为该边的基准值，其他值随y的变化而变化，得在该区域u=vc+(3*x-y)；
同理得其他俩区域的表达式。不再赘述。
 
 
程序实现：
#include <iostream>
#include <string>
using namespace std;
#define abs(a)    ((a)>0?(a)-a))
#define max(a,b) ((a)>(b)?(a)b))
int spiralval(int x,int y)
{
int t = max(abs(x),abs(y));
int vc = (t*2+1)*(t*2+1);
int u;
if ( y == -t) //分别判断，点落在该圈4条边的哪条边上
     u = vc+(x+y);
else if (x == -t)
    u = vc+(3*x-y);
else if (y == t)
     u = vc + (-x - 5*y);
else
     u = vc+(-7*x+y);
return u;
}
int main()
{
int x,y;
cout << endl;
for(y=-5;y<=5;y++)
    {
      for(x=-5;x<=5;x++)
    printf("%5d",spiralval(x,y));
      
      printf("/n");
    }
cin.get();
return 0;
}

分享到：

上一篇：C语言面试题大汇总之华为面试题下一篇：基于创建型模式的“迷宫”构造

查看评论

12楼 wodexinmingzi 2011-08-26 11:00发表 [回复]: 其实还有一点很重要，不然会有大 bug。其它三条边都还好，但是在东边（右边）那条线上，队列增加不完全符合公式！注意到东北角（右上角）是本层的最后一个数，再往下却是本层的第一个数，那当然不满足东线公式啊。但由于其它三条都满足公式，把东线的判断放在最后（其实只需要放在北线之后就可以），这样一来，东北角那点始终会被认为是北线上的点啦～～～楼主的程序是符合的噢，但没说明这一点