专栏首页C/C++基础多益网络2016春季实习校招笔试回顾(C++游戏后台开发)

多益网络2016春季实习校招笔试回顾(C++游戏后台开发)

2016.04.16晚中山大学大学城校区(东校区)参加了多益网络的C++游戏后台开发的笔试。有几道笔试题还是值得斟酌和记录的,特记录如下。比较可惜,因为回老家了,未能参加多益网络的面试。


1.试题汇总

题目一: 给定代码段int A[2][3]={1,2,3,4,5,6};那么A[1][0]和*(*(A+1)+1)的值分别是什么? 答: A[1][0]=4,*(*(A+1)+1)=5。 这里考察了对二维数组的理解和指针运算。A[1][0]=4比较好理解。但是对二维数组A进行指针运算时,我们要知道二维数组A的类型是什么,考察如下代码:

int A[2][3]={1,2,3,4,5,6};
cout<<"sizeof(A):"<<sizeof(A)<<“ ”<<typeid(A).name()<<endl;

VS2012中代码输出 sizeof(A):24 int [2][3]。可见二维数组A的类型是int[2][3],所以sizeof(A)=sizeof(int)*6=24。

知道了A的类型是int[2][3]之后,当我们对数组A进行指针运算时,那么A就会退化为指针,它的类型变为int(*)[3],验证代码如下:

cout<<"sizeof(A+1):"<<sizeof(A+1)<<" "<<typeid(A+1).name()<<endl;
cout<<"sizeof(*(A+1)):"<<sizeof(*(A+1))<<endl;

输出结果为: sizeof(A+1):4 int (*)[3] sizeof(*A):12 int [3]

所以*(A+1)表示的是二维数组的第二行,其类型是int[3]。可将*(A+1)取个别名,容易理解,*(A+1)=int a[3],此时在对变量*(A+1)进行指针运算时,就相当于对一维数组a进行进行指针运算。那么*(a+1)的值就是二维数组A的第二行的第二个数5。

是有点绕,不过一定要好好理解,才能掌握数组与指针之间的区别与联系。这里有一点一定要记住:当对数组进行指针运算时,其会退化为指针。

题目二: 下面代码的作用是什么?

double x,ret=0;
for(int i=1;scanf("%lf",&x)==1;++i){
    ret+=(x-ret)/i;
}

答: 这段代码真的很精妙,其作用就是求标准输入双精度浮点数和的平均值。按照顺序走几遍循环就可以了。比如输入的值为a,那么结果ret=a,第二次输入值为b,那么:

ret=b−a2+a=a+b2

ret=\frac {b-a} {2}+a=\frac {a+b}2 假如第三次输入的是c,那么:

ret=a+b2+c−a+b23=a+b+c3

ret=\frac {a+b}2+\frac{c-\frac {a+b}2}3=\frac{a+b+c}3

以此类推,可以知道上面的代码是求输入双精度浮点数和的平均值。

题目三: 在一个平面坐标系中,从方格(0,0)移动到方格(6,6),每次只能向上移动或者向右移动,且每次只能移动一个方格,且不能经过(2,3)和(4,4)两个方格,有多少种移动的方式。 答: 这道题本质是组合问题。解题思路: (1)算出从方格(0,0)到方格(6,6)总共有多少种移动的方式; (2)减去经过(2,3)和(4,4)的所有路径。

从方格(0,0)移动到方格(6,6)的移动次数是12次,每次都选择向右还是向上。因此向右只能选择6次,所以总的移动次数设为countAll=C612=924种。countAll=C_{12}^6=924种。

按照上面的计算方式,(0,0)到(2,3)有C25C_5^2种,再从(2,3)到(6,6)有C47C_7^4种。所以经过方格(2,3)从(0,0)移动到(6,6)的移动方式countA=C25C47=350countA=C_5^2C_7^4=350种。

同理,经过方格(2,3)从(0,0)移动到(6,6)的移动方式countB=C48C24=420countB=C_8^4C_4^2=420种。

同理,同时经过(2,3)和(4,4)的移动方式countAB=C25C13C24=180countAB=C_5^2C_3^1C_4^2=180种。

因为经过(2,3)的路径中有可能经过(4,4),反之亦然。所以减去countA和countB时,会多减去一次同时经过(2,3)和(4,4)的移动方式数countAB,所以最终结果是: count=countAll−countA−countB+countAB=924−350−420+180=334count=countAll-countA-countB+countAB=924-350-420+180=334$。

题目四: 这是一道代码理解题。给定如下代码片段:

void getmemoney(char** p,int num){
    *p=(char*)malloc(num);
}

void test(void){
    char* str=NULL;
    getmemoney(&str,1000);
    strcpy(str,"hello");
    printf(str);
}

问运行test函数有什么结果?

答: 这里考察了两点: 第一点:内存泄露; 第二点:strcpy函数的作用于特点。 运行test函数会打印输出hello,且出现内存泄露。strcpy函数与是C语言标准库函数,把从src地址开始且含有NULL结束符的字符串复制到以dest开始的地址空间。这里要注意的是字符串拷贝结束后,会在目的地址空间最后添加空字符’\0’。

题目五: 这是一道编程题。题目如下: 第五套人民币,中华人民共和国的纸币有1元、5元、10元、20元、50元和100元。共6种,凑齐100元的一种组合是:五张1元+一张5元+两张10元+一张20元+一张50元。请写一个算法,计算凑齐100元的组合的种类数。

答: 方法一:穷举法 解题思路: 我们可以列举所有可能情况。全部用1元来凑齐的话,需要一百张;全部用5元来凑的话,需要二十张;全部用10元,需要十张;全部用20元,需要五张;全部用50元,需要两张,全部用100元,需要一张。

迭代实现: 因此我们可以采用多重循环迭代的方式来求出组成100元的所有可能性。参考如下代码:

int main(){
    int count=0; //组合种类数
    for(int a=0;a<=100;++a){
        for(int b=0;b<=20;++b){
            for(int c=0;c<=10;++c){
                for(int d=0;d<=5;++d){
                    for(int e=0;e<=2;++e){
                        for(int f=0;f<=1;++f){
                            if(1*a + 5*b + 10*c + 20*d + 50*e + 100*f==100)
                                count++;
                        }//end f:100元
                    }//end e:50元
                }//end d:20元
            }//end c:10元
        }//end b:5元
    }//end a:1元

    cout<<"count:"<<count<<endl;
}

程序输出: count:344。表明有344种组合方式。

递归实现: 列举所有可能的组合,我们可以采用递归的方式来实现。将所有可能的组合可以列举成如下的六叉树形结构:

我们深度遍历这棵六叉树,来统计凑够100元的组合数。但是以递归的方式来深度遍历这棵六叉树时需要注意两点:

第一点:回溯。对于每种面值累加厚,在退出当前节点回到上一层节点时需要进行回溯,即减去这一层节点的纸币面值。

第二点:避免重复。在深度遍历时,如果全部遍历的话,会出现重复组合的情况。比如以面值1开始递归遍历,有一种组合方式是1,1,1…1,5,从头结点开始再以5开始递归遍历会出现5,1,1,1…1。这两种组合其实是同一种组合方式,如何避免这种重复计数呢?

以1开始遍历,其实是统计了所有包含1组成100的左右可能情况。这时候,再以5开始遍历的时候,我们就不应该再去遍历包含1的所有可能的组合。所以要给定节点内的下标,表示当前遍历时节点内的起始值是什么。比如再以头结点的5开始遍历时,下面每一层节点内的遍历起点都是从5开始,而不能从1开始。

参考如下代码:

int rmb[6]={1,5,10,20,50,100};
int count=0;//组合数

//index:表示第几个纸币,即节点内下标
void getCombinationNum(int& sum,int index){
    for(int i=index;i<6;++i){
        sum+=rmb[i];
        if(sum<100)
            getCombinationNum(sum,i);
        if(sum==100){
            ++count;
        }
        sum-=rmb[i]; //回溯
    }
}

int main(){
    int sum=0; //币值累加和
    getCombinationNum(sum,0);
    cout<<"count:"<<count<<endl;
}

程序输出:count:344种。

递归与迭代实现的对比: 使用递归的方式来实现穷举所有可能的组合,代码实现上较为简洁,但是递归带来的多重的函数调用增加了运行时开销,效率次于迭代实现,并且不太容易理解。所以建议使用迭代的方式来实现穷举。

方法二:动态规划法 考察组成100元的方式,可以从高面值往低面值开始拆分。对于100元面值的纸币,组成100元的方式要么包含100元面值的纸币,要么不包含这两种情况。

所以可以设f(n,j)表示价值为n的金额由包含第0到第j种面值组成的所有情况数。那么f(n,j)分为两种情况,包含第j种面值,和不包含第j种面值情况,那么f(n,j)=f(n-v[j],j)+f(n,j-1)。其中f[n,j-1]表示没有第j种纸币的情况的总和,f(n-v[j],j)表示去掉一张第j中纸币面值后剩余面值由第0到第j种面值组成的所有情况数。特别的,当n=0时,f(0,j)=1。

有了上面的递归式,我们知道f(100,5)就是我们要求的组成100元由第0种纸币1元到第5种纸币100元组成的种类数。

实现参考如下代码:

const int v[6] = {1,5,10,20,50,100};

int f(int n, int w)
{
    if(n<0) return 0;
    if(n==0) return 1;
    if(w<0) return 0;

    return f(n, w-1) + f(n-v[w], w);
}

int main(){
    cout<<"count:"<<f(100,5)<<endl;
}

输出结果:count:344。

小结

终于写完了,历时两天。里面的一些东西还是不错的。尤其是最后一个编程题。包含了一些算法思想,值得大家深思。在编程时,思路很重要,有了正确的思路,才能写出正确的代码。


参考文献

[1]http://blog.csdn.net/meifage2/article/details/6612257#comments. [2]41楼.http://bbs.csdn.net/topics/270082525.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基数排序简介及其并行化

      基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

    Dabelv
  • 二路归并排序简介及其并行化

    归并排序是分治法(Divide and Conquer)的一个典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若...

    Dabelv
  • 网易游戏技术岗在线编程题(二)

    小v今年有n门课,每门都有考试,为了拿到奖学金,小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成,满分为r。现在他知道每门课的平时成绩为ai...

    Dabelv
  • POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

    最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,...

    ShenduCC
  • agc007B - Construct Sequences(构造)

    attack
  • C++ template的一些高级用法(元编码,可变参数,仿函数,using使用方法,. C++ 智能指针)

    1 .  通用函数可变参数模板      对于有些时候,我们无法确切的知道,函数的参数个数时,而又不想过多的使用所谓的函数重载,那么就可以效仿下面的例子: 1...

    Gxjun
  • 04:最长公共子上升序列

    总时间限制: 10000ms内存限制: 65536kB描述给定两个整数序列,写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候,我们将长度为N的序列S...

    attack
  • Leetcode 第 167 场周赛题解

    BBuf
  • Day3上午解题报告

    预计分数:100+40+50=190 实际分数:100+40+50=190 T1 https://www.luogu.org/problem/show?pid=...

    attack
  • 【CCF】相邻数对

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk

扫码关注云+社区

领取腾讯云代金券