网易的笔试题一道:
如图：
设“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]#
|
