有趣的智力题测验,你答对了吗
1. 考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币,每次必需且只能放置一枚硬币,要求硬币完全置于桌面内(不能有一部分悬在桌子外面),并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币,谁就输了。游戏的先行者还是后行者有必胜策略?这种策略是什么?
答案:先行者在桌子中心放置一枚硬币,以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样,只要后行者能放,先行者一定也有地方放。先行者必胜。
2. 用线性时间和常数附加空间将一篇文章的单词(不是字符)倒序。
答案:先将整篇文章的所有字符逆序(从两头起不断交换位置相对称的字符);然后用同样的办法将每个单词内部的字符逆序。这样,整篇文章的单词顺序颠倒了,但单词本身又被转回来了。
3. 用线性时间和常数附加空间将一个长度为n 的字符串向左循环移动m 位(例如,”abcdefg”移动3位就变成了”defgabc”)。
答案:把字符串切成长为m 和n-m 的两半。将这两个部分分别逆序,再对整个字符串逆序。
4. 一个矩形蛋糕,蛋糕内部有一块矩形的空洞。只用一刀,如何将蛋糕切成大小相等的两块?
答案:注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线,这条线显然把两个矩形都分成了一半,它们的差当然也是相等的。
5. 一块矩形的巧克力,初始时由N x M个小块组成。每一次你只能把一块巧克力掰成两个小矩形。最少需要几次才能把它们掰成N x M块1×1的小巧克力? 答案:N x M - 1次显然足够了。这个数目也是必需的,因为每掰一次后当前巧克力的块数只能增加一,把巧克力分成N x M块当然需要至少掰N x M - 1次。
6. 如何快速找出一个32位整数的二进制表达里有多少个”1″?用关于”1″的个数的线性时间?
答案1(关于数字位数线性):for(n=0; b; b >>= 1) if (b & 1) n++; 答案2(关于”1″的个数线性):for(n=0; b; n++) b &= b-1;
7. 一个大小为N 的数组,所有数都是不超过N-1的正整数。用O(N)的时间找出重复的那个数(假设只有一个)。一个大小为N 的数组,所有数都是不超过N+1的正整数。用O(N)的时间找出没有出现过的那个数(假设只有一个)。
答案:计算数组中的所有数的和,再计算出从1到N-1的所有数的和,两者之差即为重复的那个数。计算数组中的所有数的和,再计算出从1到N+1的所有数的和,两者之差即为缺少的那个数。
8. 给出一行C 语言表达式,判断给定的整数是否是一个2的幂。
答案:(b & (b-1)) == 0
9. 地球上有多少个点,使得从该点出发向南走一英里,向东走一英里,再向北走一英里之后恰好回到了起点?
答案:“北极点”是一个传统的答案,其实这个问题还有其它的答案。事实上,满足要求的点有无穷多个。所有距离南极点1 + 1/(2π) 英里的地方都是满足要求的,向南走一英里后到达距离南极点1/(2π) 的地方,向东走一英里后正好绕行纬度圈一周,再向北走原路返回到起点。事实上,这仍然不是满足要求的全部点。距离南极点1 + 1/(2kπ) 的地方都是可以的,其中k 可以是任意一个正整数。
10. A、B 两人分别在两座岛上。B 生病了,A 有B 所需要的药。C 有一艘小船和一个可以上锁的箱子。C 愿意在A 和B 之间运东西,但东西只能放在箱子里。只要箱子没被上锁,C 都会偷走箱子里的东西,不管箱子里有什么。如果A 和B 各自有一把锁和只能开自己那把锁的钥匙,A 应该如何把东西安全递交给B ? 答案:A 把药放进箱子,用自己的锁把箱子锁上。B 拿到箱子后,再在箱子上加一把自己的锁。箱子运回A 后,A 取下自己的锁。箱子再运到B 手中时,B 取下自己的锁,获得药物。
11. 一对夫妇邀请N-1对夫妇参加聚会(因此聚会上总共有2N 人)。每个人都和所有自己不认识的人握了一次手。然后,男主人问其余所有人(共2N-1个人)各自都握了几次手,得到的答案全部都不一样。假设每个人都认识自己的配偶,那么女主人握了几次手?
答案:握手次数只可能是从0到2N-2这2N-1个数。除去男主人外,一共有2N-1个人,因此每个数恰好出现了一次。其中有一个人(0)没有握手,有一个人(2N-2)和所有其它的夫妇都握了手。这两个人肯定是一对夫妻,否则后者将和前者握手(从而前者的握手次数不再是0)。除去这对夫妻外,有一个人(1)只与(2N-2)
握过手,有一个人(2N-3)和除了(0)以外的其它夫妇都握了手。这两个人肯定是一对夫妻,否则后者将和前者握手(从而前者的握手次数不再是1)。以此类推,直到握过N-2次手的人和握过N 次手的人配成一对。此时,除了男主人及其配偶以外,其余所有人都已经配对。根据排除法,最后剩下来的那个握手次数为N-1的人就是女主人了。
********************************************************************1
12. 小明和小强都是张老师的学生,张老师的生日是M 月N 日,2人都不知道张老师的生日是下列10组中的一天,张老师把M 值告诉了小明,把N 值告诉了小强,张老师问他们知道他的生日是那一天吗?
3月4日 3月5日 3月8日
6月4日 6月7日
9月1日 9月5日
12月1日 12月2日 12月8日
小明说:如果我不知道的话,小强肯定也不知道
小强说:本来我也不知道,但是现在我知道了
小明说:哦,那我也知道了
请根据以上对话推断出张老师的生日是哪一天?
*************************************************************