一些挺有意思的笔试题

明天就要去腾讯的实习生笔试了,感觉现在是十分的没底啊~

这几天一直在网上找往年的实习题,可惜大公司的保密工作都做得很好,所以只能找来不少乱七八糟的题目,个人感觉影印版是最靠谱的,可惜来来去去只找到了一份而已。其中有不少挺有意思的题目,有智力也有编程方面的,在这里摘录一下吧~

先是一道智力题:

转自http://www.cnblogs.com/selfstudy/archive/2012/04/10/2441518.html

题目:给定1到100的数, 选手A猜,裁判B给提示,当A给出的数小于Ans时,B提示A所说的数偏小,当A给出的数大于Ans时,B从此只告诉A这个数是否Ans.问需要多少次才能肯定的猜中Ans.

解答:这里的答案是14.从14,27,39,50...的顺序猜,在往大数猜的同时,又保证到时候往回猜小数的时候能尽可能的少猜。

这里只知道答案的解释,但是没找到思路。


下面还是一道智力题:

转自http://blog.csdn.net/yahohi/article/details/7453005

题目:1-20的两个数把和告诉A,积告诉B,A说不知道是多少,B也说不知道。

这时A说我知道了,B接着说我也知道了,问这两个数是多少?

解答

设和为S,积为M。

首先,A:我不知道。

说明:S可以分解成多个组合,而2=1+1,3=1+2,40=20+20,39=19+20,只有一种分解方式,因此S应属于[4,38]集合。

其次,B:我也不知道。

说明:M也可以分解成多个组合,因此M不是质数。

再者,A:我现在知道了。

说明:S分解方式中只有一个相乘之后是合数,其他分解方式相乘之后都是质数。这样,A才能根据B说不知道,而排出所有相乘是质数(M是质数,分解方式只有一种:1*质数)的可能,剩下的一个相乘之后是合数的组合就是A所得到的解。

而相乘之后是质数的:只有1*质数 = 质数!

1-20的所有质数:T = {2, 3, 5, 7, 11, 13, 17, 19}。

设x为T中的任意一个质数。那么,S的可能取值集合:{2+1, 3+1, 5+1, 7+1, 11+1, 13+1, 17+1, 19+1},即:SS = {3, 4, 6, 8, 12, 14, 18, 20}

S= 3时:3不在【4,38】集合,排除;

S= 4时:4=2+2=1+3,(2,2)相乘为4(非质数,满足条件),(1,3)相乘为3(质数,排除);

S= 6时:6=1+5=2+4=3+3,相乘分别为5,8,9,出现两个合数,排除;

其他值都是存在多个合数分解的情况,因此均排除了。

因此,A得到的解是2和2.

最后,B:我也知道了。

说明:B根据自己已知的M值,站在A的立场思考,能够获得M=4的结果,现在验证如下:

M=4=22=14,相加结果为4,5.而5不在SS集合之中,因此结果为2和2.

因此,最终答案为2和2.

 

以上给出的分析是假设这两个数是可以相同的。

如果认为这两个数不同,那又应该是哪两个数呢?

还是按照上面的步骤来进行分析:

首先,A:我不知道。

说明:S有多个分解方式。S属于【5,37】.

其次,B:我不知道。

说明:M有多种分解方式。

再者,A:我知道这两个数了。

说明:S分解方式中只有一个相乘之后是合数,其他分解方式相乘之后的积仅有一种分解方式!这样,A才能根据B说不知道,而排出所有相乘是质数(M是质数,分解方式只有一种:1*质数)的可能,剩下的一个相乘之后是合数的组合就是A所得到的解。

那么,S的可能取值集合:{3,4,5,......,37}

S= 3时:3不在【5,38】集合,排除;

S= 4时:4=1+3,只有一种分解方式,排除;

S=5时:5=1+4=2+3,相乘分别为4,8,4=14仅有一种分解方式排除,8=18=2*4满足,得到一个解。

S= 6时:6=1+5=2+4,相乘分别为5,8,显然也满足。

其他值都是存在多个合数分解的情况,因此均排除了。

因此,解为2和3 或 2和4

最后,B:我也知道了。

说明:B站在A立场得知结果。验证如下:

如果为2和3,则积为6,和为5。此时,5=1+4=2+3,4仅有一种分解方式,A能够确定为2和3;6=16=23,相加为7,5,此时7=1+6=2+5=3+4,相乘后为6,10,12,无法确定唯一解,舍掉1,6的解;而5=1+4=2+3,相乘后为4,6,舍掉4,有解2和3.

如果为2和4,则积为8,和为6.此时,6=1+5=2+4,5仅有一种分解方式,A能够确定为2和4. 8=18=24,相加为9,6,此时9=1+8=2+7=3+6=4+5,无法确定唯一解,舍掉1和8的解;而6=1+5=2+4,相乘后为5,6,舍掉5,有解2和4.

因此,最终解为2和3 或 2和4 。


一道编程题:

转自http://www.cppblog.com/izualzhy/archive/2012/04/09/170654.html

题目

给定一个数组a[N],我们希望构造数组b[N],其中b[i]=a[0]a[1]...*a[N-1]/a[i]。在构造过程: 不允许使用除法; 要求O(1)空间复杂度和O(n)时间复杂度; 除遍历计数器与a[N] b[N]外,不可使用新的变量(包括栈临时变量、对空间和全局静态变量等);

解答

#include <stdio.h>  
#include <stdlib.h>  
#define LEN 6  

int main(){  
        int a[LEN] = {1,2,3,4,5,6};
        int b[LEN];
        int i;

        b[0]= 1;  
        for(i= 1; i < LEN; i++){  
               b[i] = b[i - 1] * a[i - 1];   //初始化数组b
        }  
        for(i = LEN - 2; i > 0; i--){  //把b[i]后面的部分相乘放到b[0],然后和b[i]相乘
               b[0] *= a[i + 1];  
               b[i]*= b[0];  
        }  
        b[0] *= a[1];  
        for(i = 0; i < LEN; i++){  
               printf("%d ", b[i]);  
        }  
        return0;  
}

 由于空间复杂度为O(1),所以这里巧妙地用了b[0]作为中间变量。

« 返回