经典智力题

一、微软58题

A.逻辑推理

1.你让工人为你工作7天，给工人的回报是金条。金条分为连接的7段
，你必须在每天结束时给他们一条金条。如果你只能断两次金条，你怎么给你？
工人付费？

2、请把一盒蛋糕切成8份，分给8个人，但蛋糕盒里还必须留有一份。

3、小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，
小明的弟弟3秒，小明的父亲6秒，小明的母亲8秒，小明的祖父12秒。
这座桥最多可以穿过两个人，过桥的速度取决于过桥最慢的速度，灯点燃后30秒就会亮起
熄灭。问:小明一家怎么过桥？

4、一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少
有一顶。每个人都能看到别人帽子的颜色，却看不到自己的。主持人先让大家看看。
看看别人头上戴什么帽子，然后关灯。如果有人认为他戴黑帽子，他们会打自己
一记耳光。第一次关灯，没有声音。所以再开灯，大家再看一遍，关灯的时候还是鸦。
雀无声。直到第三次关灯，才有劈劈啪啪的声音。问有多少人戴着黑色的衣服。
帽子？

5、请估算一下ＣＮ　ＴＯＷＥＲ电视塔的质量。

6、一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯
从一楼到十楼，每层电梯门都会打开一次，只能拿一次钻石，问怎么才能得到最好的
大的一个？

7、U2合唱团必须在17分钟内到达音乐会场，途中必须穿过一座桥，四个人从桥上走过
从同一端开始，你必须帮助他们到达另一端。天很黑，他们只有一个手电筒。
同时最多可以有两个人一起过桥，过桥的时候一定要拿手电筒，所以一定要有人把它拿走
手电筒带走，来回桥两端。手电筒不能丢失。四个人走路
速度不同，如果两个人同行，以慢的速度为准。Bono过桥需要1分钟，Edge需花
过桥2分钟，Adam过桥需要5分钟，Larry过桥需要10分钟。他们如何在17分钟内
过桥呢？

8、烧一根不均匀的绳要用一个小时，如何用它来判断半个小时 ?

9、为什么下水道的盖子是圆的？

10、美国有多少辆加油站（汽车）？

11、有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐
分为50克和90克一份？

12、有一辆火车以每小时15公里的速度离开洛杉矶直奔纽约，另一辆火车以第
以20公里的速度从纽约到洛杉矶。如果有一只鸟，每小时30公里以外的速度和
两列火车现在启动，从洛杉矶出发，遇到另一辆车后返回，依次飞往两列火车
行，火车在直道两侧相遇。这只鸟飞了多久？

13、你有两个罐子，50个红色弹球，50个蓝色弹球，随机选出一个罐子，随机
选择一个放在罐子里的弹球，如何给红色弹球最大的选择机会？在你的计划中，得到它
红球的准确率是多少？

14、想象你在镜子前，请问，为什么镜子中的影像可以颠倒左右，却不能颠倒
上下？

15、你有四人装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被
污染重量 1.只称一次，如何判断哪罐药被污染？

16、如果你有无穷多的水，一个3夸脱的和一个5夸脱的提桶，你如何准确称出
4夸脱的水？

17、你有一桶果冻，其中有黄色，绿色，红色三种，，闭上眼睛选出同样颜色
的两个，同一颜色的两个。你可以确定你必须有两个相同颜色的水果
冻？

18、将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁？

19、如果要你能去掉50个州的任何一个，那你去掉哪一个，为什么？

20、对一批编号为1~100 所有开关朝上打开的灯操作如下
凡1 倍数反方向拨打开关2 倍数反方向拨打开关3 倍数反方向
再次拨打开关。
问最后为关熄状态的灯的编号。

21、假设一张圆盘像唱机上的唱盘那样转动。这张盘一半是黑色，一半是白色
。假设你有一些无限数量的颜色传感器。为了确定圆盘旋转的方向，你需要在它周
周围有多少颜色传感器？它们应该放在哪里？

22、假设时钟到了12点。注意时针和分针重叠在一起。在一天之中，时针和分
针重叠多少次？你知道它们重叠的具体时间吗？

23、中间只隔一个数字的两个奇数被称为奇数对，比如17和19。证明奇数对之
间的数字总能被6整除（假设这两个奇数都大于6）。现在证明没有由三个奇数组成
奇数对。

24、一个屋子有一个门（门是关闭的）和3盏电灯。屋外有3个开关，分别与这
连接3盏灯。您可以随意操作这些开关，但一旦您打开门，您就更换开关。
确定每个开关的具体管道。

25、假设你有8个球，其中一个略微重一些，但是找出这个球的惟一方法是将
将两个球放在天平上进行比较。找到这个重球至少需要多少次？

26、下面玩一个拆字游戏，所有字母的顺序都被打乱。你要判断这个字是什么
。假设这个被拆开的字由五个字母组成：
1.有多少种可能的组合方式？
2.假如我们知道是哪五个字母，那会发生什么？
3.找出解决这个问题的方法。

27、有4个女人要过一座桥。她们都站在桥的某一边，要让她们在17分钟内全
部通过这座桥。那是晚上。他们只有一个手电筒。最多只能让两个人同时过桥。
不管是谁过桥，不管是一两个人，都要带手电筒。手电筒必须传来
不能扔掉。每个女人过桥的速度都不一样，两个人的速度一定要慢一点
过桥速度。
第一个女人：过桥需要1分钟；
第二个女人：过桥需要2分钟；
第三个女人：过桥需要5分钟；
第四个女人：过桥需要10分钟。
比如，如果第一个女人与第4个女人首先过桥，等她们过去时，已经过去了10
分钟。如果第四个女人把手电筒送回去，那么当她到达桥的另一端时，她会一起去
20分钟后，行动失败。如何让这四个女人在17分钟内过桥？还有什么其他的？
法？

28、如果你有两个桶，一个装的是红色的颜料，另一个装的是蓝色的颜料。你
从蓝色油漆桶中舀一杯，倒入红色油漆桶中，然后从红色油漆桶中舀一杯，倒入蓝色油漆桶中
。两桶中红蓝颜料的比例哪个更高？算术证明了这一点。

B：疯狂计算

29、已知两个1~30之间的数字，A知道两数之和，B知道两数之积。
甲问乙："你知道是哪两个数吗？"乙说："不知道"；
乙问甲："你知道是哪两个数吗？"甲说："也不知道"；
于是，乙说："那我知道了"；
随后甲也说："那我也知道了"；
这两个数是什么？

30、4，4，10，10，加减乘除，怎么出24点？

31、1000!有几位数，为什么？

32、F(n)=1 n>8 n<12
F(n)=2 n<2
F(n)=3 n=6
F(n)=4 n=other
使用 - * /和sign(n)函数组合出F(n)函数
sign(n)=0 n=0
sign(n)=-1 n<0
sign(n)=1 n>0

33、编一个程序求质数的和例如F(7)=13 3 5 11 13 =58

34、。。。
请仅用一支笔画四根直线将上图9 各点全部连接

35、三层四层二叉树有多少种

36、1--100000 数列按一定顺序排列，有一个数字排错，如何纠错？写出最好
方法。两个数字呢？

37、链接表和数组之间的区别是什么？

38、做一个链接表，你为什么要选择这样的方法？

39、选择一种算法来整理出一个链接表。你为什么要选择这种方法？现在用
O(n)时间来做。

40、说说各种股票分类算法的优点和缺点。

41、用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍
。
42、用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。

43、用一种算法整理一个数组。你为什么选择这种方法？

44、用一种算法使通用字符串相匹配。

45、颠倒一个字符串，优化速度，优化空间。

46、颠倒一个句子中的词的顺序，比如将"我叫克丽丝"转换为"克丽丝叫我"，
实现最快，移动最少。

　　47、找到一个子字符串，优化速度，优化空间。 

　　48、比较两个字符串，用O(n)时间和恒量空间。
 
　　49、假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你 
知道所有的整数都在1到1000（包括1000）之间。此外，除一个数字出现两次外， 
其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重 
复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方 
式的算法吗？ 

　　50、不用乘法或加法增加8倍。现在用同样的方法增加7倍。 

C：创造性应用 

　　51、营业员小姐由于工作失误，将2万元的笔记本电脑以1.2万元错卖给李先生 
，王小姐的经理怎么写信给李先生试图将钱要回来？ 

　　52、如何将计算机技术应用于一幢100层高的办公大楼的电梯系统上？你怎样 
优化这种应用？工作日时的交通、楼层或时间等因素会对此产生怎样的影响？ 

　　53、你如何对一种可以随时存在文件中或从因特网上拷贝下来的操作系统实施 
保护措施，防止被非法复制？ 

　　54、你如何重新设计自动取款机？ 

　　55、假设我们想通过电脑来操作一台微波炉，你会开发什么样的软件来完成这 
个任务？ 

　　56、你如何为一辆汽车设计一台咖啡机？ 

　　56、如果你想给微软的Word系统增加点内容，你会增加什么样的内容？ 

　　57、你会给只有一只手的用户设计什么样的键盘？ 

　　58、你会给失聪的人设计什么样的闹钟？

如有更好的解答，Kayven微博留言（E-mail）。

参考答案:

  1、day1 给1 段， 
　　day2 让工人把1 段归还给2 段， 
　　day3 给1 段， 
　　day4 归还1 2 段，给4 段。 
　　day5 依次类推…… 

　　2、面对这样的怪题，有些应聘者绞尽脑汁也无法分成；而有些应聘者却感到 
此题实际很简单，把切成的8份蛋糕先拿出7份分给7人，剩下的1份连蛋糕盒一起分 
给第8个人。 

　　4、假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就 
应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只 
看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白 
，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子 
，于是也会有耳光声响起；可事实是第三次才响起了耳光声，说明全场不止两顶黑 
帽，依此类推，应该是关了几次灯，有几顶黑帽。
 
　　5、比如你怎样快速估算支架和柱子的高度、球的半径，算出各部分的体积等 
等。招聘官的说法："就CNTOWER这道题来说，它和一般的谜语或智力题还是有区别 
的。我们称这类题为’快速估算题’，主要考的是快速估算的能力，这是开发软件 
必备的能力之一。当然，题目只是手段，不是目的，最终得到一个结果固然是需要 
的，但更重要的是对考生得出这个结果的过程也就是方法的考察。"Mr Miller为记 
者举例说明了一种比较合理的答法，他首先在纸上画出了CN TOWER的草图，然后快 
速估算支架和各柱的高度，以及球的半径，算出各部分体积，然后和各部分密度运 
算，最后相加得出一个结果。 
　　这一类的题目其实很多，如："估算一下密西西比河里的水的质量。""如果你 
是田纳西州州长，请估算一下治理好康柏兰河的污染需要多长时间。" 
　　"估算一下一个行进在小雨中的人5分钟内身上淋到的雨的质量。" 
　　Mr Miller接着解释道："像这样的题目，包括一些推理题，考的都是人的 
ProblemSolving(解决问题的能力)，不是哪道题你记住了答案就可以了的。" 
　　对于公司招聘的宗旨，Mr Miller强调了四点，这些是有创造性的公司普遍注 
重的员工素质，是想要到知名企业实现自己的事业梦想的人都要具备的素质和能力 
。 
　　要求一：RawSmart（纯粹智慧），与知识无关。 
　　要求二：Long-termPotential(长远学习能力)。 
　　要求三：TechnicSkills(技能)。 
　　要求四：Professionalism(职业态度)。 

　　6、她的回答是：选择前五层楼都不拿，观察各层钻石的大小，做到心中有数 
。后五层楼再选择，选择大小接近前五层楼出现过最大钻石大小的钻石。她至今也 
不知道这道题的准确答案，"也许就没有准确答案，就是考一下你的思路，"她如是 
说。 

　　7、分析：有个康奈尔的学生写文章说他当时在微软面试时就是碰到了这道题 
，最短只能做出在19分钟内过桥。
 
　　8、两边一起烧。 

　　9、答案之一：从麻省理工大学一位计算机系教授那里听来的答案，首先在同 
等用材的情况下他的面积最大。第二因为如果是方的、长方的或椭圆的，那无聊之 
徒拎起来它就可以直接扔进地下道啦！但圆形的盖子嘛，就可以避免这种情况了 
) 

　　10、这个乍看让人有些摸不着头脑的问题时，你可能要从问这个国家有多少小 
汽车入手。面试者也许会告诉你这个数字，但也有可能说："我不知道，你来告诉 
我。"那么，你对自己说，美国的人口是2.75亿。你可以猜测，如果平均每个家庭 
（包括单身）的规模是2.5人，你的计算机会告诉你，共有1.1亿个家庭。你回忆起 
在什么地方听说过，平均每个家庭拥有1.8辆小汽车，那么美国大约会有1.98亿辆 
小汽车。接着，只要你算出替1.98亿辆小汽车服务需要多少加油站，你就把问题解 
决了。重要的不是加油站的数字，而是你得出这个数字的方法。
 
　　12、答案很容易计算的： 
　　假设洛杉矶到纽约的距离为s 
　　那小鸟飞行的距离就是(s/(15+20))*30。 

　　13、无答案，看你有没有魄力坚持自己的意见。 

　　14、因为人的两眼在水平方向上对称。 

　　15、从第一盒中取出一颗，第二盒中取出2 颗，第三盒中取出三颗。 
　　依次类推，称其总量。
 
　　16、比较复杂： 
　　Ａ、先用3 夸脱的桶装满，倒入5 夸脱。以下简称3->5) 
　　在5 夸脱桶中做好标记b1，简称b1)。 
　　B、用3 继续装水倒满5 空3 将5 中水倒入3 直到b1 在3 中做标记b2 
　　Ｃ、用5 继续装水倒满3 空5 将3 中水倒入5 直到b2 
　　Ｄ、空3 将5 中水倒入3 标记为b3 
　　Ｅ、装满5 空3 将5 中水倒入3 直到3 中水到b3 
　　结束了，现在5 中水为标准的4 夸脱水。 

　　20、素数是关，其余是开。 

　　29、允许两数重复的情况下 
　　答案为x=1，y=4；甲知道和A=x+y=5，乙知道积B=x*y=4 
　　不允许两数重复的情况下有两种答案 
　　答案1：为x=1，y=6；甲知道和A=x+y=7，乙知道积B=x*y=6 
　　答案2：为x=1，y=8；甲知道和A=x+y=9，乙知道积B=x*y=8 
　　解： 
　　设这两个数为x，y. 
　　甲知道两数之和 A=x+y； 
　　乙知道两数之积 B=x*y； 
　　该题分两种情况 ： 
　　允许重复， 有(1 <= x <= y <= 30)； 
　　不允许重复，有(1 <= x < y <= 30)； 
　　当不允许重复，即(1 <= x < y <= 30)； 
　　1)由题设条件：乙不知道答案 
　　<=> B=x*y 解不唯一 
　　=> B=x*y 为非质数 
　　又∵ x ≠ y 
　　∴ B ≠ k*k (其中k∈N) 
　　结论(推论1)： 
　　B=x*y 非质数且 B ≠ k*k (其中k∈N) 
　　即：B ∈(6，8，10，12，14，15，18，20...) 
　　证明过程略。 
　　2)由题设条件：甲不知道答案 
　　<=> A=x+y 解不唯一 
　　=> A >= 5； 
　　分两种情况： 
　　A=5，A=6时x，y有双解 
　　A>=7 时x，y有三重及三重以上解 
　　假设 A=x+y=5 
　　则有双解 
　　x1=1，y1=4； 
　　x2=2，y2=3 
　　代入公式B=x*y： 
　　B1=x1*y1=1*4=4；(不满足推论1，舍去) 
　　B2=x2*y2=2*3=6； 
　　得到唯一解x=2，y=3即甲知道答案。 
　　与题设条件："甲不知道答案"相矛盾 ， 
　　故假设不成立，A=x+y≠5 
　　假设 A=x+y=6 
　　则有双解。 
　　x1=1，y1=5； 
　　x2=2，y2=4 
　　代入公式B=x*y： 
　　B1=x1*y1=1*5=5；(不满足推论1，舍去) 
　　B2=x2*y2=2*4=8； 
　　得到唯一解x=2，y=4 
　　即甲知道答案 
　　与题设条件："甲不知道答案"相矛盾 
　　故假设不成立，A=x+y≠6 
　　当A>=7时 
　　∵ x，y的解至少存在两种满足推论1的解 
　　B1=x1*y1=2*(A-2) 
　　B2=x2*y2=3*(A-3) 
　　∴ 符合条件 
　　结论(推论2)：A >= 7 
　　3)由题设条件：乙说"那我知道了" 
　　=>乙通过已知条件B=x*y及推论(1)(2)可以得出唯一解 
　　即： 
　　A=x+y， A >= 7 
　　B=x*y， B ∈(6，8，10，12，14，15，16，18，20...) 
　　1 <= x < y <= 30 
　　x，y存在唯一解 
　　当 B=6 时：有两组解 
　　x1=1，y1=6 
　　x2=2，y2=3 (∵ x2+y2=2+3=5 < 7∴不合题意，舍去) 
　　得到唯一解 x=1，y=6 
　　当 B=8 时：有两组解 
　　x1=1，y1=8 
　　x2=2，y2=4 (∵ x2+y2=2+4=6 < 7∴不合题意，舍去) 
　　得到唯一解 x=1，y=8 
　　当 B>8 时：容易证明均为多重解 
　　结论： 
　　当B=6时有唯一解 x=1，y=6当B=8时有唯一解 x=1，y=8 
　　4)由题设条件：甲说"那我也知道了" 
　　=>　甲通过已知条件A=x+y及推论(3)可以得出唯一解 
　　综上所述，原题所求有两组解： 
　　x1=1，y1=6 
　　x2=1，y2=8 
　　当x<=y时，有(1 <= x <= y <= 30)； 
　　同理可得唯一解 x=1，y=4 

　　31、 
　　解：1000 
　　Lg(1000!)=sum(Lg(n)) 
　　n=1 
　　用3 段折线代替曲线可以得到 
　　10(0+1)/2+90(1+2)/2+900(2+3)/2=2390 
　　作为近似结果，好象1500~3000 都算对 

　　32、F(n)=1 n>8 n<12 
　　F(n)=2 n<2 
　　F(n)=3 n=6 
　　F(n)=4 n=other 
　　使用+ - * /和sign(n)函数组合出F(n)函数 
　　sign(n)=0 n=0 
　　sign(n)=-1 n<0 
　　：sign(n)=1 n>0 
　　解:只要注意[sign(n-m)*sign(m-n)+1]在n=m 处取1 其他点取0 就可以了 

　　34、米字形的画就行了 

　　59、答案是和家人告别. 

-------------------------------------------------------------------------

二、18题
1、考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币，每次必需且只能放置一枚硬币，要求硬币完全置于桌面内（不能有一部分悬在桌子外面），并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币，谁就输了。游戏的先行者还是后行者有必胜策略？这种策略是什么？
    答案：先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜。

    2、 用线性时间和常数附加空间将一篇文章的单词（不是字符）倒序。
    答案：先将整篇文章的所有字符逆序（从两头起不断交换位置相对称的字符）；然后用同样的办法将每个单词内部的字符逆序。这样，整篇文章的单词顺序颠倒了，但单词本身又被转回来了。

    3、 用线性时间和常数附加空间将一个长度为n的字符串向左循环移动m位（例如，"abcdefg"移动3位就变成了"defgabc"）。
    答案：把字符串切成长为m和n-m的两半。将这两个部分分别逆序，再对整个字符串逆序。

    4、一个矩形蛋糕，蛋糕内部有一块矩形的空洞。只用一刀，如何将蛋糕切成大小相等的两块？
    答案：注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线，这条线显然把两个矩形都分成了一半，它们的差当然也是相等的。

    5、 一块矩形的巧克力，初始时由N x M个小块组成。每一次你只能把一块巧克力掰成两个小矩形。最少需要几次才能把它们掰成N x M块1x1的小巧克力？
    答案：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的人就是女主人了。

 

    12、两个机器人，初始时位于数轴上的不同位置。给这两个机器人输入一段相同的程序，使得这两个机器人保证可以相遇。程序只能包含“左移n个单位”、“右移n个单位”，条件判断语句If，循环语句while，以及两个返回Boolean值的函数“在自己的起点处”和“在对方的起点处”。你不能使用其它的变量和计数器。
    答案：两个机器人同时开始以单位速度右移，直到一个机器人走到另外一个机器人的起点处。然后，该机器人以双倍速度追赶对方。程序如下。

while(!at_other_robots_start) {
  move_right 1
}
while(true) {
  move_right 2
}

    13、 如果叫你从下面两种游戏中选择一种，你选择哪一种？为什么？
      a. 写下一句话。如果这句话为真，你将获得10美元；如果这句话为假，你获得的金钱将少于10美元或多于10美元（但不能恰好为10美元）。
      b. 写下一句话。不管这句话的真假，你都会得到多于10美元的钱。
    答案：选择第一种游戏，并写下“我既不会得到10美元，也不会得到10000000美元”。

      14、你在一幢100层大楼下，有21根电线线头标有数字1..21。这些电线一直延伸到大楼楼顶，楼顶的线头处标有字母A..U。你不知道下面的数字和上面的字母的对应关系。你有一个电池，一个灯泡，和许多很短的电线。如何只上下楼一次就能确定电线线头的对应关系？
       答案：在下面把2,3连在一起，把4到6全连在一起，把7到10全连在一起，等等，这样你就把电线分成了6个“等价类”，大小分别为1, 2, 3, 4, 5, 6。然后到楼顶，测出哪根线和其它所有电线都不相连，哪些线和另外一根相连，哪些线和另外两根相连，等等，从而确定出字母A..U各属于哪个等价类。现在，把每个等价类中的第一个字母连在一起，形成一个大小为6的新等价类；再把后5个等价类中的第二个字母连在一起，形成一个大小为5的新等价类；以此类推。回到楼下，把新的等价类区别出来。这样，你就知道了每个数字对应了哪一个原等价类的第几个字母，从而解决问题。

    15、某种药方要求非常严格，你每天需要同时服用A、B两种药片各一颗，不能多也不能少。这种药非常贵，你不希望有任何一点的浪费。一天，你打开装药片A的药瓶，倒出一粒药片放在手心；然后打开另一个药瓶，但不小心倒出了两粒药片。现在，你手心上有一颗药片A，两颗药片B，并且你无法区别哪个是A，哪个是B。你如何才能严格遵循药方服用药片，并且不能有任何的浪费？
    答案：把手上的三片药各自切成两半，分成两堆摆放。再取出一粒药片A，也把它切成两半，然后在每一堆里加上半片的A。现在，每一堆药片恰好包含两个半片的A和两个半片的B。一天服用其中一堆即可。

     16、 你在一个飞船上，飞船上的计算机有n个处理器。突然，飞船受到外星激光武器的攻击，一些处理器被损坏了。你知道有超过一半的处理器仍然是好的。你可以向一个处理器询问另一个处理器是好的还是坏的。一个好的处理器总是说真话，一个坏的处理器总是说假话。用n-2次询问找出一个好的处理器。
       答案：给处理器从1到n标号。用符号a->b表示向标号为a的处理器询问处理器b是不是好的。首先问1->2，如果1说不是，就把他们俩都去掉（去掉了一个好的和一个坏的，则剩下的处理器中好的仍然过半），然后从3->4开始继续发问。如果1说2是好的，就继续问2->3，3->4，……直到某一次j说j+1是坏的，把j和j+1去掉，然后问j-1 -> j+2；或者从j+2 -> j+3开始发问，如果前面已经没有j-1了（之前已经被去掉过了）。注意到你始终维护着这样一个“链”，前面的每一个处理器都说后面那个是好的。这条链里的所有处理器要么都是好的，要么都是坏的。当这条链越来越长，剩下的处理器越来越少时，总有一个时候这条链超过了剩下的处理器的一半，此时可以肯定这条链里的所有处理器都是好的。或者，越来越多的处理器都被去掉了，链的长度依旧为0，而最后只剩下一个或两个处理器没被问过，那他们一定就是好的了。另外注意到，第一个处理器的好坏从来没被问过，仔细想想你会发现最后一个处理器的好坏也不可能被问到（一旦链长超过剩余处理器的一半，或者最后没被去掉的就只剩这一个了时，你就不问了），因此询问次数不会超过n-2。

      17、一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向？
      答案：你可以把两个相机放在圆盘上相近的两点，然后观察哪个点先变色。事实上，只需要一个相机就够了。控制相机绕圆盘中心顺时针移动，观察颜色多久变一次；然后让相机以相同的速度逆时针绕着圆盘中心移动，再次观察变色的频率。可以断定，变色频率较慢的那一次，相机的转动方向是和圆盘相同的。

     18、有25匹马，速度都不同，但每匹马的速度都是定值。现在只有5条赛道，无法计时，即每赛一场最多只能知道5匹马的相对快慢。问最少赛几场可以找出25匹马中速度最快的前3名？（百度2008年面试题）

每匹马都至少要有一次参赛的机会，所以25匹马分成5组，一开始的这5场比赛是免不了的。接下来要找冠军也很容易，每一组的冠军在一起赛一场就行了（第6场）。最后就是要找第2和第3名。我们按照第6场比赛中得到的名次依次把它们在前5场比赛中所在的组命名为A、B、C、D、E。即：A组的冠军是第6场的第1名，B组的冠军是第6场的第2名……每一组的5匹马按照他们已经赛出的成绩从快到慢编号：

A组：1，2，3，4，5
B组：1，2，3，4，5
C组：1，2，3，4，5
D组：1，2，3，4，5
E组：1，2，3，4，5

从现在所得到的信息，我们可以知道哪些马已经被排除在3名以外。只要已经能确定有3匹或3匹以上的马比这匹马快，那么它就已经被淘汰了。可以看到，只有上表中粗体的那5匹马是有可能为2、3名的。即：A组的2、3名；B组的1、2名，C组的第1名。取这5匹马进行第7场比赛，第7场比赛的前两名就是25匹马中的2、3名。故一共最少要赛7场。

这道题有一些变体，比如64匹马找前4名。方法是一样的，在得出第1名以后寻找后3名的候选竞争者就可以了。

--------------------------------------------------------------------------------------------

三、16题
◆1． 有一个长方形蛋糕，切掉了长方形的一块（大小和位置随意），你怎样才能直直的一刀下去，将剩下的蛋糕切成大小相等的两块？

　　答案：将完整的蛋糕的中心与被切掉的那块蛋糕的中心连成一条线。这个方法也适用于立方体！请注意，切掉的那块蛋糕的大小和位置是随意的，不要一心想着自己切生日蛋糕的方式，要跳出这个圈子。

　　◆2． 有三筐水果，一筐装的全是苹果，第二筐装的全是橘子，第三筐是橘子与苹果混在一起。筐上的标签都是骗人的，（比如，如果标签写的是橘子，那么可以肯定筐里不会只有橘子，可能还有苹果）你的任务是拿出其中一筐，从里面只拿一只水果，然后正确写出三筐水果的标签。

　　提示：从标着“混合”标签的筐里拿一只水果，就可以知道另外两筐装的是什么水果了。

　　◆3． 你有八个球。其中一个有破损，因此比其他球轻了一些。你有一架天平用来比较这些球的重量。如果只称两次，如何找出有破损的那个球？

　　◆4． 为什么下水道的井盖是圆的？

　　提示：方形的对角线比边长！

　　其他答案：1圆形的井盖可以由一个人搬动，因为它可以在地上滚。2圆形的井盖不必为了架在井口上而旋转它的位置。

　　◆5． 美国有多少辆车？

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

　　◆7． 一列时速15英里的火车从洛杉矶出发，驶向纽约。另外一列时速20英里的火车从纽约出发，驶向洛杉矶。如果一只鸟以每小时25英里的速度飞行，在同一时间从洛杉矶出发，在两列火车之间往返飞行，到火车相遇时为止，鸟飞了多远？

　　提示：想想火车的相对速度。

　　◆8． 你有两个罐子，分别装着50个红色的玻璃球和50个蓝色的玻璃球。随意拿起一个罐子，然后从里面拿出一个玻璃球。怎样最大程度地增加让自己拿到红色球的机会？利用这种方法，拿到红色球的几率有多大？

　　◆9． 假设你站在镜子前，抬起左手，抬起右手，看看镜中的自己。当你抬起左手时，镜中的自己抬起的似乎是右手。可是当你仰头时，镜中的自己也在仰头，而不是低头。为什么镜子中的影像似乎颠倒了左右，却没有颠倒上下？

　　◆10． 你有5瓶药，每个药丸重10克，只有一瓶受到污染的药丸重量发生了变化，每个药丸重9克。给你一个天平，你怎样一次就能测出哪一瓶是受到污染的药呢？

　　答案：

　　1 给5个瓶子标上1、2、3、4、5。

　　2 从1号瓶中取1个药丸，2号瓶中取2个药丸，3号瓶中取3个药丸，4号瓶中取4个药丸，5号瓶中取5个药丸。

　　3 把它们全部放在天平上称一下重量。

　　4 现在用1×10＋2×10＋3×10＋4×10＋5×10的结果减去测出的重量。

　　5 结果就是装着被污染的药丸的瓶子号码。

　　◆11． 如果你有一个容量为5夸脱的水桶和一个容量为3夸脱的水桶，怎样准确地量出4夸脱的水？
　　1.装满5夸脱水，并把部分水倒入3跨脱水桶，剩下2夸脱。
　　2.把3夸脱水倒掉
　　3.将5夸脱桶中的2夸脱水倒入3夸脱桶中。
　　4.将5夸脱桶再次装满
　　5.将5夸脱桶中的水倒入已有2夸脱水的3夸脱桶中，这样5夸脱桶中剩下的水刚好是4夸脱

◆12． 在开汽车的锁时，应该往哪个方向旋转钥匙？

　　◆13． 如果你可以移动50个州中的任何一个，你会挑哪个，为什么？

　　◆14． 有4条狗（4只蚂蚁或4个人）分别在一个广场的4个角落里。突然，它们同时以同样的速度追赶在自己顺时针方向的一个人，而且会紧追这个目标不放。它们需要多少时间才能相遇，相遇地点在哪里？

　　提示：它们将在广场中央相遇，所跑的距离与它们跑的路线无关。

　　◆15．从空中放下两列火车，每列火车都带着降落伞，降落到一条没有尽头的笔直的铁道上。两列火车之间的距离不清楚。两列车都面向同一个方向。在落地后，降落伞掉在地上，与火车分离。两列火车都有一个微芯片，可以控制它们的运动。两个芯片是相同的。两列火车都不知道自己的位置。你需要在芯片中写入编码，让这两列火车相遇。每行编码都有一定的执行命令的时间。

　　你能使用以下指令（而且只能用这些指令）：

　　MF—让火车朝前开

　　MB—让火车朝后开

　　IF（P）—如果火车旁边有降落伞，这个条件就得到了满足。

　　GOTO

　　答案：

　　A：MF

　　IF（P）

　　GOTO B

　　GOTO A

　　B：MF

　　GOTO B

　　解释：第一行只是让它们离开各自的降落伞。必须让它们离开自己的降落伞，这样后面的火车才能发现前面火车的降落伞，这样就满足了一个条件，它们就可以跳出起初遵守的编码。它们起初都在A这部分循环，直到后面的火车发现前面火车的降落伞，这时就转入B：并陷入B的循环。前面的火车还是没有找到降落伞，所以就不停地在A里面循环。由于每行编码都有一定的执行命令时间，完成A循环就比完成B费时，因此后面的火车（在B循环中）最终将赶上前面的火车。

　　16.有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐分成50、90克各一份？
　　（1） 把2克重的砝 放在天平左端，分盐于天平两端直到平衡，此时，左端有盐69克，右端有盐71克。（2）取下天平左端的2克砝码换上7克重的砝码， 端重（69+7）76克，右端仍重71克，从左端取出5克盐后，天平两端平衡，这时左端 余64克盐。在取下天平两端物品。
　　（3） 用刚才称出的5克盐当作砝码，与2克、7克砝码合成14克砝码。从64克盐 取出14克，恰好剩下50克盐。则其余盐的重量就是90克

----------------------------------------------------------------------------------------------------------------------------
四、18题

1.有A、B两个水杯，都没有刻度，也不允许做刻度。A杯装满水是5升，B杯装满水是3升。不借助别的任何工具，只用这两个杯子如何精确的得到4升水
         1.先用B倒进A三升水
         2.B再盛满，将A倒满：B内剩1升。
         3.将A倒空：将B内的一升倒进A。
         4.B再盛满3升。倒进A，则得4升。 
2.给你一盒蛋糕，请你切成八份，分给在场的八个人，但蛋糕盒里还要有一份。
   首先先把蛋糕切成八份，讲其中的七份分给在场的七个人，然后把蛋糕盒和其中的一分蛋糕分给没有蛋糕的人，就可以达到目的。

3.有一个说谎岛，上面居住着人还有吸血鬼，有一年岛上流行瘟疫，有一半的人和吸血鬼疯了，于是岛上有神志清醒的人和精神错乱的人，还有神志清醒的吸血鬼和精神错乱的吸血鬼，其中神志清醒的人和精神错乱的吸血鬼只说真话，而精神错乱的人和神志清醒的吸血鬼只说假话，并且他们回答问题只说“是”或“不是”；有一天岛上来了一位“逻辑博士”在岛上遇见了P，博士问了一个问题就分出他是人还是吸血鬼，博士又问了一个问题就分辨出他是神志清醒的还是精神错乱的。请写出博士问得两个问题；写出你的思路。
条件是：神志清醒的人和精神错乱的吸血鬼只说真话
        精神错乱的人和神志清醒的吸血鬼之说假话
4.一天有个年轻人来到王老板店里买了一件礼物,这件礼物成本18元,标价21元。结果这个年轻人掏出100元来买这件礼物,王老板当时没有零钱,用那100元向街坊换了100元的零钱,找给年轻人79元,但是街坊后来发现那100元是**,王老板无奈还了街坊100元,问题是:王老板在这次交易中到底损失了多少钱?????
礼物成本价：18元
标  价：21元
老板找了79元给年轻人，而年轻人的100元是假的这样的话年轻人是得了一件成本价18元的礼物外加79元一共得到97元老板在这次的交易中损失了97元

5、一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少 
　　有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看 
　　看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自 
　　己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦 
　　雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑 
　　帽子？ 
        假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就 
　　应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只 
　　看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白 
　　，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子 
　　，于是也会有耳光声响起；可事实是第三次才响起了耳光声，说明全场不止两顶黑 
　　帽，依此类推，应该是关了几次灯，有几顶黑帽。
6.烧一根不均匀的绳要用一个小时，如何用它来判断半个小时 ?
                两头一起烧、从绳子中间烧、将绳子对折烧

7.想象你在镜子前，请问，为什么镜子中的影像可以颠倒左右，却不能颠倒 
　　上下？ 
        因为人的两眼在水平方向上对称

-----------------------------------------------------------------------------------------------------

1．一个粗细均匀的长直管子，两端开口，里面有4个白球和4个黑球，球的直径、两端开口的直径等于管子的内径，现在白球和黑球的排列是wwwwbbbb，要求不取出任何一个球，使得排列变为bbwwwwbb。
　　2．一只蜗牛从井底爬到井口，每天白天蜗牛要睡觉，晚上才出来活动，一个晚上蜗牛可以向上爬3尺，但是白天睡觉的时候会往�