阿里巴巴2014年校园招聘试题解答

时间:2022-05-11 18:50:07

        说来有些惭愧,这个题目是夸张的说法。目前我只做了一道题,觉得挺有意思,自己思考了一下,就想写到博客上。我对这类题目很感兴趣,如果以后能多碰到这类的题目,我会一一记录下来。

        阿里巴巴2014校招北京笔试题第29题:

        在黑板上写下50个数字,1到50,。在接下来的49轮操作中,每次做如下动作:选取黑板上的两个数字a和b,擦去,在黑板上写下|a-b|。请问最后一次动作之后,写下的数可能是什么?为什么?

        一道数学类的分析题,分析起来,却挺有意思。下面是我的分析,如果有不对的地方,万望指正!

        首先我们要做的,是猜测出,这些到底是哪一类的数。1到50,有点多,好吧,我们降低一点难度。不妨设n = 50,就是1到n的连续的数字。问题则成为,n = 50的时候,最后剩下的应该是什么数字。如果n = 1,那么最后只能是1,如果n = 2,也很明显,最后结果是1,。都是奇数。且慢,我们看一下n = 3的情况,结果是0,2;那么n = 4呢?结果是0,2,4。都是偶数。继续,n = 5和6的时候,结果,是奇数。好了,数量开始多了,不过,我们已经能够看出规律了。

        规律:n = 2k-1或2k,如果k是奇数,那么最后剩余的数是奇数,而且所有不大于n的奇数,都能够出现。如果k是偶数则最后余下的是偶数,而且所有不大于n的偶数都能够出现。规律是否正确,下面需要我们的证明。要证明上述的规律,我们需要找到上述规律的充分条件和必要条件。

        这里不讨论分类的情况,我们的n = 50。则,k = 25,是个奇数,那么我们只讨论k是奇数的时候的情况。要证明“k是奇数,最后剩余的数是奇数,且所有小于n的奇数都有可能。”证明这个,需要证明两条(注意前提:n = 2k,k是奇数):

        1、最后的数一定是个奇数。

        2、任意一个小于n的奇数,我们能够给出一个擦除数的流程,使得最后剩下的数等于这个奇数。

        证明1:从所有书中选出两个数,我们有三种选法,两个奇数、两个偶数、一个奇数和一个偶数。两个奇数的情况,最后结果是奇数的个数减去2,偶数的个数加上1。两个偶数,最终的结果是偶数的个数减去1。一个奇数,一个偶数,最终结果也是偶数的个数减去1。我将两个奇数的情况成为A类操作,其它情况成为B类操作,这样,还需要证明:A类操作和B类操作的顺序的不同对于最终的奇偶数的个数不产生影响。这个结论证明比较简单。于是,开始k个奇数,k个偶数,我们可以先通过(k-1)/2次A类操作,将奇数的数量降低到1,在通过B类操作,去掉所有的偶数,于是,只剩下一个奇数了。从而,证明最终剩下的一定是一个奇数。

        证明2:只要找到中擦除过程就可以。这里画个图吧。

阿里巴巴2014年校园招聘试题解答

        按照图片方式排列所有数字,如果我要最后留下数字2i - 1,则将2i和1单独拿出来,剩下的按照箭头所示进行结合,每次去掉箭头连接的数字,这样剩下的是1,由于k是个奇数,这样,我们得到的1的个数是有偶数个,每两个1相结合,这样,共得到(k-1)/2个0,可知,0与任何数结合,比如|x - 0|,结果还是x。因此,这些0都可以去掉。最后剩下1和2i这两个数,|2i-1|的最终结果是2i-1。第2个问题证明完毕。

        一道题说了这么多话,有点繁琐,不过数学是严密的,每一个小结论,都需要严格的逻辑说明。