Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1412237
  • 博文数量: 181
  • 博客积分: 3308
  • 博客等级: 中校
  • 技术积分: 2227
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-03 12:03
个人简介

我是zoro

文章分类

全部博文(181)

文章存档

2015年(1)

2013年(35)

2012年(39)

2011年(50)

2010年(56)

分类: LINUX

2010-11-28 22:47:27

网易的笔试题一道:
 
如图:
 
 
 
设“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]#
阅读(1459) | 评论(0) | 转发(0) |
0

上一篇:epoll机制

下一篇:Linux异步IO

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