网易笔试题

网易的笔试题一道:

 

如图：

 

 

　

设“1”的坐标为（0，0） “7”的坐标为（－1，－1） 编写一个小程序，使程序做到输入坐标（X,Y）之后显示出相应的数字。

 

这个图有点像螺旋，它是按顺时针方向（由1->2->3->4->5…），逐渐向外膨胀。显然，如果以1为原点（0，0），以向右为x轴的正方向，以向下为y轴的正方向：

那么用人眼很容易就看出7的坐标为（－1，－1），这正与题目的假设一致。其他，如5的坐标应为（－1，1）。

但是，怎么让计算机知道呢？我的大脑突然不知所措，我在想，如果真出了这道题我挂定了^_^。但是，既然现在我是安然的坐在自己的卧室里，我绝对不会向它投降。

于是，躺在床上，望着天花板，想象着从这个螺旋的原点1出发，一起来看看：

Step1：从1向左走1步到达2。坐标（0，0）－>（1，0），即x加1。

Step2：从2向下走1步到达3，坐标（0，1）－>（1，1），即y加1。

Step3：从3向右走1步到达4，坐标（1，1）－>（0，1），即x减1。

Step4：从4向右走1步到达5，坐标（0，1）－>（－1，1），即x减1。

Step5：从5向上走1步到达6，坐标（－1，1）－>（－1，0），即y减1。

Step6：从6向上走1步到达7，坐标（－1，0）－>（－1，－1），即y减1。

……

当在大脑中想象着这一步一步的异同，一个灵感闪灵了。你是否发现了其中的规律？好吧，让我总结一下它的规律：

1、每向左(left)走一步，x就加1。每向右(right)走一步，x就减1。每向下(down)走一步，y就加1。每向上(up)走一步，y就减1。

这一条规律，只要有点直角坐标的知识，是显而易见的。当我们用程序去模拟这样一步一步地行走的时候，另外一个问题，就浮出水面了：怎样告诉计算 机，让它按照一个顺时针的螺旋方式，去遍历每一个结点？比如，当计算机来到结点2的时候，它怎么知道，下一步应该往下走呢？当计算机来到结点5的时候，它 怎么知道，下一点应该往上走呢？其实，这里还藏着另一条规律：

我把它叫做状态转换的规律。这个规律包含两个方面：

2.1、从结点1开始，

A、向右走

B、向下走

C、向左走

D、向上走

又回到A。形成一个循环，即：A－>B－>C－>D－>A－>B……。

在每一个方向上，应该走多少步，才改变方向呢？现假设，现在开始改变方向，且已知上一次向右走了rNum步，向下走了dNum步，向左走了lNum步，向上走了uNum步。那么从现在开始，

2.2、沿新方向所走的步数，应该等于上一次相反方向所走的步数加1。例如，现在处于结点3，刚才从2－>3的时候是往下走，现在要改变方向，向左走了。这个时候，由于上一次向右走了1步（即由1－>2）。所以，这次应该向左走1＋1＝2步。

 

找到以上的两个规律，就可以写程序了。

我们可以用枚举类型，来标识四个方向（right,down,left,up）。

用四个整形变量，来记录上一次各个方向所走的步数（rNum,dNum,lNum,uNum）。

用四个整形变量，来记录在每一个方向累积所走的步数（rSum,dSum,lSum,uSum）。

这样，结点值就由这个公式确定：nodeVal = lSum+dSum+rSum+uSum+1。之所以加1，是因为原点的值为1，而不是0。

而坐标值可以这样确定：因为向右为x轴正方向，故x = rSum-lSum。因为向下为y轴的正方向，故y = dSum-uSum。

[root@mip-123456 163]# cat 163.c
#include<stdio.h>
#include<stdlib.h>

int find_res(int x,int y)
{
  int num = 1;

  if((x == 0)&&(y == 0))
    return 1;
  int flag = 1;
  int tmp_x = 0;
  int tmp_y = 0;
  int r_num = 0;
  int l_num = 0;
  int u_num = 0;
  int d_num = 0;
  int i;
  
  enum state{right,left,up,down};
  enum state state = right;

  while(flag)
  {
   switch(state)
    {
     case right:
         r_num = 0;
         for(i=0;i<l_num+1;i++)
           {
            r_num++;
            tmp_x++;
            num++;
           // printf("right num is %d\n",num);

            if((tmp_x == x)&&(tmp_y == y))
               {
                flag = 0;
                break;
               }
            }
            state = down;
           break;
     case down:
         d_num = 0;
         for(i=0;i<u_num+1;i++)
           {
            d_num++;
            tmp_y++;
            num++;
           // printf("down num is %d\n",num);

            if((tmp_x == x)&&(tmp_y == y))
               {
                flag = 0;
                break;
               }
            }
            state = left;
           break;
     case left:
         l_num = 0;
         for(i=0;i<r_num+1;i++)
           {
            l_num++;
            tmp_x--;
            num++;
           // printf("left num is %d\n",num);

            if((tmp_x == x)&&(tmp_y == y))
               {
                 flag = 0;
                 break;
                }
            }
            state = up;
           break;
     case up:
         u_num = 0;
         for(i=0;i<d_num+1;i++)
           {
            u_num++;
            tmp_y--;
            num++;
           // printf("up num is %d\n",num);

            if((tmp_x == x)&&(tmp_y == y))
               {
                flag = 0;
                break;
               }
            }
            state = right;
           break;
    default:
           break;
     }
  }
    return num;
}

int main(int argc,char* argv[])
{
 int i = 0;
 int j = 0;
 
  for(i=-1;i<=2;i++)
   {
    for(j = -1;j<=2;j++)
     {
        printf("(%d,%d) is %d\n",i,j,find_res(i,j));
      }
  }
 return 0;
}
[root@mip-123456 163]# ./163
(-1,-1) is 7
(-1,0) is 6
(-1,1) is 5
(-1,2) is 16
(0,-1) is 8
(0,0) is 1
(0,1) is 4
(0,2) is 15
(1,-1) is 9
(1,0) is 2
(1,1) is 3
(1,2) is 14
(2,-1) is 10
(2,0) is 11
(2,1) is 12
(2,2) is 13
[root@mip-123456 163]#