首页 > 代码库 > 九宫格----记网易游戏2015年研发类笔试题
九宫格----记网易游戏2015年研发类笔试题
最近一直在找工作,昨天参加了网易游戏的研发类笔试,题量比较大,大题有6个。
1.最小字典序字符串,
2.递归绘图函数转非递归
3.游戏编程中常用的数据结构4叉树,有三问,一问是写出如何判断点在矩形中和判断两矩形是否相交,第二问是写创建四叉树的实现,第三问是如何根据已知的矩形块,在四叉树中寻找包含的物体。
4.KD树,英文题,没怎么看,第一问问给出的一个算法的复杂度,并分析;第二问是自己实现算法(没怎么看)
5.求带权二叉树的最长路径,权值可以为负值
6.九宫格,就是手机手势密码。有三问,一问是如果只设置2位密码,有多少种满足的密码,密码不能穿越,比如1 3之间穿过2,这是不允许的;第二问,如果变成N*M格,判断一个2位密码是否是满足要求的密码(要求同1),第三问,如果设置密码位数为9位,有多少种合适的密码,给出算法思路,并给出伪代码。
当时最后一题写的有点仓促,写的用DFS实现,类似全排列实现,只不过递归过程中剔除不符合要求的即可(相当于剪枝吧),伪代码写的稀烂,今天周末自己在电脑上写出来了。跟大家分享一下。
分析一下九宫格如下图所示
1 2 3
4 5 6
7 8 9
不难看出,可以把所有点分成三类:
1 3 5 9为一类,2 4 6 8 为一类,5单独为1类。
第一类点,任意2点都不能互联,但是如果两点之间的已经用过,这时是可以互联的,这点一定要注意。
第二类点,2 8 是不能直接连的,4 6也是不行的,但是如果5已经用过,它们就变成可以连接的点了。
第三类点只有5一个,它与所有点之间都是可以直接连的。
求全排列的算法,网上有2中,一种是递归算法,另一种是非递归算法。不清楚的请百度之,博客园里也已经有很多大牛写过博客了,不再赘述。
我采用的是简单的递归算法,一是思路比较清晰,也好理解。并且此题深度不大,只有9,故DFS是可以的。
具体代码如下:
1 int dfs(int* a,bool* flag,int k,int n) 2 { 3 4 int sum = 0; 5 if (k>=n) 6 { 7 #if 0 8 for (int i=0;i<k;i++) 9 {10 cout<<a[i];11 }12 cout<<endl;13 #endif14 return 1;15 }16 else if (k<n)17 {18 for (int i=1;i<=9;i++)19 { 20 if (!flag[i])21 { //检测是否合适22 if(check(a,flag,i,k))23 {24 flag[i]=true;25 a[k]=i;26 sum+=dfs(a,flag,k+1,n);27 flag[i]=false;28 }29 }30 }31 return sum; 32 }33 }
其中数组a保存已经确定了的密码序列,flag数组flag[i]表示数字i是否已经使用过,flag[0]未用。#if 0 …… #endif代码段用于打印出合适的密码序列。
k表示已经确定了前k-1个数,现在准备确定第k个满足要求的数。n表示密码长度,如果要求满足要求的2位,3位等等密码,可以直接设置成相应的值即可。
最重要的算法就是其中的check函数,也就是检测密码是否满足题意。
check算法的思路我上面已经做过分析,这里直接给出实现。需要注意的是,我们只需要判断即将确定位置的数a[k]和前一个数a[k-1]的组合的合法性即可,
为什么呢?因为这是一个递归的算法,也就是说前k-1个数构成的序列是一步步确定合法的序列,所以只需要判断从a[k-1]到a[k]是否合法即可。代码如下:
1 bool check(int* a,bool* flag,int i,int k) 2 { 3 if (k==0)//确定第一个数字,任意数字都是合法的 4 { 5 return true; 6 } 7 if(i%2==1&&i!=5 && a[k-1]%2==1&&a[k-1]!=5)//a[k-]和i都属于1,3,7,9 8 { 9 return flag[(i+a[k-1])>>1];10 }11 else if (i%2==0 && a[k-1]%2==0) //a[k-]和i都属于2,4,6,812 {13 if (a[k-1]+i==10)14 {15 return flag[5];16 }17 return true;18 }19 else//其他情况20 { 21 return true;22 }23 }
好了,这道题就这么解决了,22分的题目,难度倒不是很难,还是值得分析一下的。而且通过这个可以清楚得到我们的手势密码一共有多少种(九宫格)。如果是破解的话,真的很简单,这里给出整个测试的源码。
#include <iostream>using namespace std;bool check(int* a,bool* flag,int i,int k){ if (k==0)//确定第一个数字,任意数字都是合法的 { return true; } if(i%2==1&&i!=5 && a[k-1]%2==1&&a[k-1]!=5)//a[k-]和i都属于1,3,7,9 { return flag[(i+a[k-1])>>1]; } else if (i%2==0 && a[k-1]%2==0) //a[k-]和i都属于2,4,6,8 { if (a[k-1]+i==10) { return flag[5]; } return true; } else//其他情况 { return true; }}int dfs(int* a,bool* flag,int k,int n){ int sum = 0; if (k>=n) {#if 0 for (int i=0;i<k;i++) { cout<<a[i]; } cout<<endl;#endif return 1; } else if (k<n) { for (int i=1;i<=9;i++) { if (!flag[i]) { //检测是否合适 if(check(a,flag,i,k)) { flag[i]=true; a[k]=i; sum+=dfs(a,flag,k+1,n); flag[i]=false;//此处注意恢复flag的标志 } } } return sum; }}int main(){#if 0 freopen("out.txt","w",stdout);#endif int a[9]={0}; bool flag[10]={false}; int sum = 0; for(int i=4;i<=9;i++) { sum+=dfs(a,flag,0,i); } cout<<sum<<endl;}
给出4位到9位手势密码总数389112,程序运行很快,有兴趣的可以运行看看,所以手势密码真的安全吗?留给大家去思考!
有兴趣的也可以做个GUI,然后看看所有的手势密码,肯定有一些比较霸气的!
九宫格----记网易游戏2015年研发类笔试题