智力题¶

这部分内容的题目侧重思维发散。

1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？

2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人?

有 4 张红色的牌和 4 张蓝色的牌，主持人先拿任意两张，再分别在 A、B、C 三人额头上贴任意两张牌， A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌， A 说不知道，B 说不知道，C 说不知道，然后 A 说知道了。请教如何推理，A 是怎么知道的。如果用程序，又怎么实现呢？

有 A、B、C、D 四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时 1、2、5、10 分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在 17 分钟内这四个人都过桥？

有 12 个小球,外形相同,其中一个小球的质量与其他 11 个不同，给一个天平,问如何用 3 次把这个小球找出来，并且求出这个小球是比其他的轻还是重

“十袋白色粉末，其中有一袋溶于水两分钟以后会变蓝，现在只有四个杯子，无限多的水，要求是在最短的时间内找出这袋特殊的粉末”

一二三四号粉末放第 1 个杯子，二三四号粉末分别放在第 234 个杯子里，五六七号粉末放到 2 号杯子里，六七号粉末分别放到 34 号杯子里，八九号粉末放到第 3 个杯子里，九十号粉末放到第 4 个杯子里，OK 了”

27.跳台阶问题题目：一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。求总共有多少总跳法，并分析算法的时间复杂度。

这道题最近经常出现，包括 MicroStrategy 等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。

1.设计一个魔方（六面）的程序。

1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用 x 次天平，最多可以从 y 个小球中找出较轻的那个，求 y 与 x 的关系式

26、有一根 27 厘米的细木杆，在第 3 厘米、7 厘米、11 厘米、17 厘米、23 厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。

编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

20、13 个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球?（http://zhidao.baidu.com/question/66024735.html ）。

1.烧一根不均匀的绳，从头烧到尾总共需要 1 个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？ 2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？（5 秒 -1 分钟） 3.如果你有无穷多的水，一个 3 公升的提捅，一个 5 公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出 4 公升的水？（40 秒 -3 分钟）一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问？（20 秒 -2 分钟）

100.第 4 组微软面试题，挑战思维极限 1.12 个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。 13 个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）（5 分钟 -1 小时） 2.在 9 个点上画 10 条直线，要求每条直线上至少有三个点？（3 分钟 -20 分钟） 3.在一天的 24 小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？（5 分钟 -15 分钟） 1.一道著名的毒酒问题有 1000 桶酒，其中 1 桶有毒。而一旦吃了，毒性会在 1 周后发作。现在我们用小老鼠做实验，要在 1 周内找出那桶毒酒，问最少需要多少老鼠。 2.有趣的石头问题有一堆 1 万个石头和 1 万个木头，对于每个石头都有 1 个木头和它重量一样，把配对的石头和木头找出来。 1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高 (两人身高一样认为是合适的), 那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列: 176, 178, 180, 170, 171 这些捣乱分子对为 <176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>, 那么,现在给出一个整型序列,请找出这些捣乱分子对的个数 (仅给出捣乱分子对的数目即可,不用具体的对) 要求：输入: 为一个文件 (in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。输出：为一个文件 (out)，每行为一个数字，表示捣乱分子的对数。详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的代码，并分析时间复杂度。限制：输入每行的最大数字个数为 100000 个，数字最长为 6 位。程序无内存使用限制。

29、有 A、B、C、D 四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时 1、2、5、10 分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在 17 分钟内这四个人都过桥？

30、有 12 个小球,外形相同,其中一个小球的质量与其他 11 个不同，给一个天平,问如何用 3 次把这个小球找出来，并且求出这个小球是比其他的轻还是重

创新工场面试题：abcde 五人打渔，打完睡觉，a 先醒来，扔掉 1 条鱼，把剩下的分成 5 分，拿一份走了；b 再醒来，也扔掉 1 条，把剩下的分成 5 份，拿一份走了；然后 cde 都按上面的方法取鱼。问他们一共打了多少条鱼，写程序和算法实现。提示：共打了多少条鱼的结果有很多。但求最少打的鱼的结果是 3121 条鱼（应该找这 5 个人问问，用什么工具打了这么多条鱼）。（http://blog.csdn.net/nokiaguy/article/details/6800209）。我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在 5 分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有 5 只小白鼠，请问一下，我们用这五只小白鼠，5 分钟的时间，能够检测多少瓶液体的成分？淘宝 2012 笔试（研发类）：http://topic.csdn.net/u/20110922/10/e4f3641a-1f31-4d35-80da-7268605d2d51.html（一参考答案）。

华为面试 2：1 分 2 分 5 分的硬币，组成 1 角，共有多少种组合。

43、Smith 夫妇召开宴会，并邀请其他 4 对夫妇参加宴会。在宴会上，他们彼此握手，并且满足没有一个人同自己握手，没有两个人握手一次以上，并且夫妻之间不握手。然后 Mr. Smith 问其它客人握手的次数，每个人的答案是不一样的。

求 Mrs Smith 握手的次数

44、有 6 种不同颜色的球，分别记为 1,2,3,4,5,6，每种球有无数个。现在取 5 个球，求在一下的条件下： 1、5 种不同颜色， 2、4 种不同颜色的球， 3、3 种不同颜色的球， 4、2 种不同颜色的球，它们的概率。

45、有一次数学比赛，共有 A，B 和 C 三道题目。所有人都至少解答出一道题目，总共有 25 人。在没有答出 A 的人中，答出 B 的人数是答出 C 的人数的两倍；单单答出 A 的人，比其他答出 A 的人总数多 1；在所有只有答出一道题目的人当中，答出 B 和 C 的人数刚好是一半。求只答出 B 的人数。

12 个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? 这个笔试题,很 YD,因为把某个递归关系隐藏得很深.

47、金币概率问题（威盛笔试题）

题目：10 个房间里放着随机数量的金币。每个房间只能进入一次，并只能在一个房间中拿金币。一个人采取如下策略：前四个房间只看不拿。随后的房间只要看到比前四个房间都多的金币数，就拿。否则就拿最后一个房间的金币。?

编程计算这种策略拿到最多金币的概率。

22、有 5 个海盗，按照等级从 5 到 1 排列，最大的海盗有权提议他们如何分享 100 枚金币。但其他人要对此表决，如果多数反对，那他就会被杀死。他应该提出怎样的方案，既让自己拿到尽可能多的金币又不会被杀死？（提示：有一个海盗能拿到 98% 的金币）

五只猴子分桃。半夜，第一只猴子先起来，它把桃分成了相等的五堆，多出一只。于是，它吃掉了一个，拿走了一堆；第二只猴子起来一看，只有四堆桃。于是把四堆合在一起，分成相等的五堆，又多出一个。于是，它也吃掉了一个，拿走了一堆；.....其他几只猴子也都是这样分的。问：这堆桃至少有多少个？（朋友说，这是小学奥数题）。参考答案：先给这堆桃子加上 4 个,设此时共有 X 个桃子,最后剩下 a 个桃子.这样: 第一只猴子分完后还剩:(1-1/5)X=(4/5)X; 第二只猴子分完后还剩:(1-1/5)2X; 第三只猴子分完后还剩:(1-1/5)3X; 第四只猴子分完后还剩:(1-1/5)4X; 第五只猴子分完后还剩:(1-1/5)5X=(1024/3125)X; 得:a=(1024/3125)X; 要使 a 为整数,X 最小取 3125. 减去加上的 4 个,所以,这堆桃子最少有 3121 个。

已知有个 rand7() 的函数，返回 1 到 7 随机自然数，让利用这个 rand7() 构造 rand10() 随机 1~10。（参考答案：这题主要考的是对概率的理解。程序关键是要算出 rand10，1 到 10，十个数字出现的考虑都为 10%.根据排列组合，连续算两次 rand7 出现的组合数是 7*7=49，这 49 种组合每一种出现考虑是相同的。怎么从 49 平均概率的转换为 1 到 10 呢？方法是： 1.rand7 执行两次，出来的数为 a1=rand7()-1，a2=rand7()-1. 2.如果 a1*7+a2<40,b=(a1*7+a2)/4+1；如果 a1*7+a2>=40, 重复第一步。参考代码如下所示：

int rand7()  
{  
  return rand()%7+1;  
}  

int rand10()  
{  
  int a71,a72,a10;  
  do   
  {  
    a71= rand7()-1;  
    a72 = rand7()-1;  
    a10 = a71 *7 + a72;  
  } while (a10>= 40);  
  return (a71*7+a72)/4+1;  
}

2) 一串首尾相连的珠子 (m 个)，有 N 种颜色 (N<=10)，设计一个算法，取出其中一段，要求包含所有 N 中颜色，并使长度最短。并分析时间复杂度与空间复杂度。

41.求固晶机的晶元查找程序晶元盘由数目不详的大小一样的晶元组成，晶元并不一定全布满晶元盘，

照相机每次这能匹配一个晶元，如匹配过，则拾取该晶元，若匹配不过，照相机则按测好的晶元间距移到下一个位置。求遍历晶元盘的算法求思路。