螺旋队列算法分析
时间：2010-10-24 来源：Tedunix
螺旋队列的样子如下图：
两大规律：
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)；
同理得其他俩区域的表达式。不再赘述。
程序实现：
1.#include <iostream>
2.#include <string>
3.
4.using namespace std;
5.#define abs(a) ((a)>0?(a):(-a)) 6.#define max(a,b) ((a)>(b)?(a):(b)) 7. 8. 9.int spiralval(int x,int y)
10.{
11.int t = max(abs(x),abs(y));
12.int vc = (t*2+1)*(t*2+1);
13.int u;
14. 15.if ( y == -t) //分别判断，点落在该圈4条边的哪条边上 16. u = vc+(x+y);
17.else if (x == -t)
18. u = vc+(3*x-y);
19.else if (y == t)
20. u = vc + (-x - 5*y);
21.else 22. u = vc+(-7*x+y);
23. 24.return u;
25.}
26. 27. 28.int main()
29.{
30. 31.int x,y;
32. 33.cout << endl;
34. 35.for(y=-5;y<=5;y++)
36. {
37. for(x=-5;x<=5;x++)
38. printf("%5d",spiralval(x,y));
39.
40. printf("\n");
41. 42. }
43.cin.get();
44.return 0;
45.}
46. 本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/yhmhappy2006/archive/2008/09/16/2934435.aspx
5.#define abs(a) ((a)>0?(a):(-a)) 6.#define max(a,b) ((a)>(b)?(a):(b)) 7. 8. 9.int spiralval(int x,int y)
10.{
11.int t = max(abs(x),abs(y));
12.int vc = (t*2+1)*(t*2+1);
13.int u;
14. 15.if ( y == -t) //分别判断，点落在该圈4条边的哪条边上 16. u = vc+(x+y);
17.else if (x == -t)
18. u = vc+(3*x-y);
19.else if (y == t)
20. u = vc + (-x - 5*y);
21.else 22. u = vc+(-7*x+y);
23. 24.return u;
25.}
26. 27. 28.int main()
29.{
30. 31.int x,y;
32. 33.cout << endl;
34. 35.for(y=-5;y<=5;y++)
36. {
37. for(x=-5;x<=5;x++)
38. printf("%5d",spiralval(x,y));
39.
40. printf("\n");
41. 42. }
43.cin.get();
44.return 0;
45.}
46. 本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/yhmhappy2006/archive/2008/09/16/2934435.aspx
相关阅读 更多 +
