Chinaunix首页 | 论坛 | 博客
  • 博客访问: 283231
  • 博文数量: 54
  • 博客积分: 2756
  • 博客等级: 少校
  • 技术积分: 677
  • 用 户 组: 普通用户
  • 注册时间: 2009-12-16 22:51
文章分类

全部博文(54)

文章存档

2011年(30)

2010年(22)

2009年(2)

我的朋友

分类:

2011-09-04 16:06:07

原文地址:螺旋队列 作者:gaofei8530

21    22    23    24     25

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 层规定为中间的那个 1,第 1 层为 2 到 9,第 2 层为 10 到 25,注意到 1、9、25、……不就是平方数吗?而且是连续奇数(1、3、5、……)的平方数。这些数还跟层数相关,推算一下就可以知道第 t 层之内一共有 (2t-1)^2 个数,因而第 t 层会从 [(2t-1)^2] + 1 开始继续往外螺旋。给定坐标 (x,y),如何知道该点处于第几层?层数 t = max(|x|,|y|)。

  知道了层数,接下来就好办多了,这时我们就知道所求的那点一定在第 t 层这个圈上,顺着往下数就是了。要注意的就是螺旋队列数值增长方向和坐标轴正方向并不一定相同。我们可以分成四种情况——上、下、左、右——或者——东、南、西、北,分别处于四条边上来分析。

  东|右:x == t,队列增长方向和 y 轴一致,正东方向(y = 0)数值为 (2t-1)^2 + t,所以 v = (2t-1)^2 + t + y

  南|下:y == t,队列增长方向和 x 轴相反,正南方向(x = 0)数值为 (2t-1)^2 + 3t,所以 v = (2t-1)^2 + 3t - x

  西|左:x == -t,队列增长方向和 y 轴相反,正西方向(y = 0)数值为 (2t-1)^2 + 5t,所以 v = (2t-1)^2 + 5t - y

  北|上:y == -t,队列增长方向和 x 轴一致,正北方向(x = 0)数值为 (2t-1)^2 + 7t,所以 v = (2t-1)^2 + 7t + x

  其实还有一点很重要,不然会有问题。其它三条边都还好,但是在东边(右边)那条线上,队列增加不完全符合公式!注意 到东北角(右上角)是本层的最后一个数,再往下却是本层的第一个数,那当然不满足东线公式啊。所以我们把东线的判断放在最后(其实只需要放在北线之后就可 以),这样一来,东北角那点始终会被认为是北线上的点。

答案:代码如下:

#include
#define max(a,b) ((a)<(b)?(b):(a))
#define abs(a) ((a)>0?(a):-(a))
int foo(int x, int y)
{
    int t = max(abs(x), abs(y));
    int u = t + t;
    int v = u - 1;
    v = v * v + u;
    if (x ==  - t)
        v += u + t - y;
    else if (y ==  - t)
        v += 3 * u + x - t;
    else if (y == t)
        v += t - x;
    else
        v += y - t;
    return v;
}

int main()
{
    int x, y;
    for (y =  - 4; y <= 4; y++)
    {
        for (x =  - 4; x <= 4; x++)
            printf("%5d", foo(x, y));
            printf("\n");
    }
    while (scanf("%d%d", &x, &y) == 2)
        printf("%d\n", foo(x, y));
    return 0;
}
阅读(1352) | 评论(0) | 转发(0) |
0

上一篇:C中的整型提升

下一篇:函数调用--栈

给主人留下些什么吧!~~