智力题 #16
Description
智力题
-
烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子， 问如何来计时一小时十五分钟？
先用2根绳子，其中1根一头点火，另1根两头点火，当第2根烧完的时候（即半小时），把第1根的另一头也点火，则当第1根烧完的时候，时间为45分钟；再另外用第3根绳子两头同时点火，烧完为30分钟，加起来为1小时15分钟 -
9棵树栽10行，每行3棵，如何栽？
摆成3*3的方阵，把中间一行两侧的点分别向里移两点间距离的二分之一
可画出十条直线，每条直线上三点 -
你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？
四个,如果抓取三个,有可能会是黄色，绿色，红色, 如果抓取四个那么一定有两个颜色是相同的（鸽笼原理） -
如果你有无穷多的水,一个3公升的提捅,一个5公升的提捅,两只提捅形状上下都不均匀,问你如何才能准确称出4公升的水?
3升装满;3升-〉5升(全注入);3升装满;3升-〉5升(剩1升);5升倒掉;3升-〉5升(注入1升);3升装满;3升-〉5升;完成(另:可用回溯法编程求解) -
一个岔路口分别通向诚实国和说谎国。来了两个人,已知一个是诚实国的,另一个是说谎国的。诚实国永远说实话,说谎国永远说谎话。现在你要去说谎国,但不知道应该走哪条路,需要问这两个人。请问应该怎么问?
问其中一人:另外一个人会说哪一条路是通往诚实国的?回答者所指的那条路必然是通往说谎国的。 -
12个球一个天平,现知道只有一个和其它的重量不同,问怎样称才能用三次就找到那个球。13个呢?(注意此题并未说明那个球的重量是轻是重,所以需要仔细考虑)
12个球:
第一次:4,4 如果平了:
那么剩下的球中取3放左边,取3个好球放右边,称:
如果左边重,那么取两个球称一下,哪个重哪个是次品,平的话第三个重,是次品,轻的话同理
如果平了,那么剩下一个次品,还可根据需要称出次品比正品轻或者重
如果不平:
那么不妨设左边重右边轻,为了便于说明,将左边4颗称为重球,右边4颗称为轻球,剩下4颗称为好球
取重球2颗,轻球2颗放在左侧,右侧放3颗好球和一颗轻球
如果左边重
称那两颗重球,重的一个次品,平的话右边轻球次品
如果右边重
称左边两颗轻球,轻的一个次品
如果平
称剩下两颗重球,重的一个次品,平的话剩下那颗轻球次品
13个球:
第一次:4,4,如果平了
剩5颗球用上面的方法仍旧能找出次品,只是不能知道次品是重是轻
如果不平,同上 -
在一天的24小时之中,时钟的时针、分针和秒针完全重合在一起的时候有几次?都分别是什么时间?你怎样算出来的?
23次,因为分针要转24圈,时针才能转1圈,而分针和时针重合两次之间的间隔显然> 1小时,它们有23次重合机会,每次重合中秒针有一次重合机会,所以是23次
重合时间可以对照手表求出,也可列方程求出 -
怎么样种植4棵树木,使其中任意两棵树的距离相等?
在地球表面种树,做一个地球内接的正四面体,内接点即为所求。 -
为什么下水道的盖子是圆的?
1，因为圆的不管朗个转， 都是圆的， 不会因哪一边窄一点会掉下去，
2，运输方便， 可以打滚儿，
3，节约材料， 相同大的面积， 用更少的材料， -
将汽车钥匙插入车门,向哪个方向旋转就可以打开车锁?
顺时针 -
火车运煤：你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨煤，而到目的地有1000公里，而火车最多只能装1000吨媒。如果你的火车可以全部装下，到目的地也会被全部烧光，一丁点也不剩。所以，很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话，这是很正常的。不过我不知道你还会不会继续思考下去，如果你不想思考下去了，那么我很为你担忧，因为你可能并不是一个不善于思考的人，而是一个畏难的人，还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能，后来想了一想，想到一个解法可以最多运送500吨煤到市场，方法如下：（希望你先自己想一想再查看这个答案）
装1000吨煤，走250公里，扔下500吨煤，回矿山。
装1000吨煤，走到250公里处，拿起250吨煤继续向前到500公里处，扔下500吨煤，回矿山。此时火车上还有250吨，再加上在250公里处还有250吨煤，所以，火车是可以回矿山的。
装上最后1000吨煤，走到500公里处，装上那里的500吨煤，然后一直走到目的。
于是，你最多可以运送500吨煤到市场（当然，火车也回不去了，因为那矿山没有煤了） -
赛马问题：一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问，最少得比多少场才能知道跑得最快的5匹马？（不能使用撞大运的算法）
很明显这是一个算法题，网上有很多贴子在讨论这个问题，不过都没有给出一个明确的答案。我想了想，想到下面的一个算法：
1）分成5组A，B，C，D，E，比五场。然后根据每场结果分别给这五组内的五匹马排序（从快到慢）。
2）每组的头名再赛一场，取走第一名，然后该组第二名顶上。
3）重复第二步，直到选出前5名。
这个算法是比较笨的算法，总计需要赛10次，这个算法应该是万无一失的。现在的问题的就，如何优化这个算法，想了想，的确是有优化的空间的。也就是说，是可以少于10次的。
想了一想，上面的那个算法自从第6次开始就使用5个排序数组的头名做“冒泡法”，总是挑一个最优秀的出来，其实，在第6次以后除了挑出最优秀的，我们还可以在每次比赛后淘汰一些速度不行的，淘汰的马匹数自然会比选出的更多，所以，一方面在找，另一方面在淘汰，找出前5名的速度应该会更快。
比如：我们假设比赛完第六场后，我们得到下面的排序：（每组排序是——快马从左到右，各组头名的排序是——快马从上到下）
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5
这样，我们不但知道，A1是25匹马里最快的马，而且我们可以淘汰近一半的马，比如E2，E3，E4，E5就可以全部淘汰了，为什么呢，因为比E2快的马有A1,B1,C1,D1,E1这五匹马，所以，E2后面的马是无法进入前五名了；同理，D3和其后面的也进入不了前5；同理，C4，C5，B5都可以淘汰。
于是，在第六轮后我们可以得知，除了A1外的Top 4必然在下面这些马中：
A组 A2 A3 A4 A5
B组 B1 B2 B3 B4
C组 C1 C2 C3
D组 D1 D2
E组 E1
接下来的过程应该不必我多说了。重复前面的方法，尽可能淘汰无法进前N名的马，于是后面的马就越来越少，你所需要的比赛也会越来越少。
那么，对于这个题，聪明的你知道最少要比赛几场了吗？
举一反三，如果有64匹马，8个赛道呢？不失一般性，如果有N匹马，M个赛道呢？N = M*M，那么公式是什么呢？ -
火柴棍面试题：有时候，有些面试题是很是无厘头，这不，又有一个，还记得小时候玩的的“火柴棍游戏”吗，就是移动一根火柴棍改变一个图或字的游戏。程序面试居然也可以这么玩，看看下面这个火柴棍式的程序面试题吧。
下面是一个C程序，其想要输出20个减号，不过，粗心的程序员把代码写错了，你需要把下面的代码修改正确，不过，你只能增加或是修改其中的一个字符，请你给出三种答案。int n = 20; for(int i = 0; i < n; i--){ printf("-"); }不要以为这题不是很难，我相信你并不那么容易能找到3种方法。我觉得，如果你能在10分钟内找出这三种方法，说明你真的很聪明，而且反应很快。当然，15分钟内也不赖。不过，你要是30分钟内找不到三种方法，当然，不说明你笨了，最多就是你的反应还不够快。嘿嘿。就当是玩玩吧。
//第一种解法：在for循环中给 i 加一个负号 for(int i = 0; -i < n; i--) //第二种解法：在for循环中把 i-- 变成 n-- for(int i = 0; i < n; n--) //第三种解法：把for循环中的 < 变成 + for(int i = 0; i + n; i--)其它相关的变种题如下：
通过修改、增加一个字符，让其输出21个减号
通过修改、增加一个字符，让其只输出1个减号
通过修改、增加一个字符，让其不输出减号 -
有一辆火车以每小时15公里的速度离开北京直奔广州，同时另一辆火车每小时20公里的速度从广州开往北京。如果有一只鸟，以30公里每小时的速度和两辆火车同时启动，从北京出发，碰到另一辆车后就向相反的方向返回去飞，就这样依次在两辆火车之间来回地飞，直到两辆火车相遇。请问，这只鸟共飞行了多长的距离？
火车相遇耗费的时间为t，北京到广州的距离为L，则有15t+20t=L => t=L/35
鸟飞行的距离为30t=30/35L -
你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，你必须在每天结束的时候给他们一段金条。如果只允许你两次把金条弄断，你如何给你的工人付费？
切两刀，分为1/7、2/7、4/7三段。第一天给1/7；第二天给2/7，要回1/7；第三天给1/7 ；第四天给4/7 要回1/7+2/7；第五天给1/7；第六天给2/7，要会1/7；第七天给1/7 -
一道关于飞机加油的问题，已知： 每个飞机只有一个油箱， 飞机之间可以相互加油（注意是相互，没有加油机） 一箱油可供一架飞机绕地球飞半圈， 问题： 为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）
如果机场本身不可以加油的话 那么最少需要４架 ３架同时起飞，到1/6圈时，两架飞机把各自油箱中的1/3加给另外一架，这两架剩的油正好可以原路飞回，被加油机可以飞到5/6圈处。 第４架飞机在环球飞机飞到4/6圈时起飞去接应，两飞机在5/6圈处相遇，环球机刚好用完油，加油机把1/3的油给环球机，两飞机刚好都能飞回 -
你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的药丸的重量+1。只称量一次，如何判断哪个罐子的药被污染了？
依次从四个罐子中取出1、2、3、4个药丸，设第一丸子应重为X，称得的重量是10X+t,t是几就是第几个罐子污染了。 -
门外三个开关分别对应室内三盏灯，线路良好，在门外控制开关时候不能看到室内灯的情况，现在只允许进门一次，确定开关和灯的对应关系？
先开一个，开很长时间。然后关掉，再开另一个。出去看，亮着的那个不用说。剩下的两个不亮的，按照灯泡的温度来进行判断。 -
某手机厂家由于设计失误，有可能造成电池寿命比原来设计的寿命短一半（不是冲放电时间），解决方案就是免费更换电池或给50元购买该厂家新手机的折换券。请给所有已购买的用户写信告诉解决方案
告诉用户我公司为答谢广大顾客长时间以来的厚爱，顾客可以持原电池免费更换使用寿命为原电池一倍的新型电池。或者可以持购买发票，获得50元购买该厂家新手机的折换券。 -
来自《编程之美》的概率题：一个桶里面有白球、黑球各100个，现在按下述规则取球：的
i 、每次从通里面拿出来两个球；
ii、如果取出的是两个同色的求，就再放入一个黑球；
ii、如果取出的是两个异色的求，就再放入一个白球。
问：最后桶里面只剩下一个黑球的概率是多少？
100%，异或，小规模
1 每次操作都会减少一球，所以最后剩下黑球或者白球
2 由于白球每次操作要么不变，要么成对减少，所以最后不可能剩余一个白球，那么必然是剩余黑球了 -
101个硬币中有一个假币，有一个无砝码的天平，称两次，判断假币比真币重还是轻。
这个题比较简单吧，比较快的想出了一种方法（逻辑题是强项，不虚…）。
我的方案是分33，33，35三堆，先33与33称，如果相同，那么假币在35那堆里，然后去35枚真币与有假币那堆的称，就知道结果了。如果33与33重量不相等，记录哪一堆更重，然后可以知道35枚硬币都只真的，从中取33枚，与其中33个中的一堆对比，如果相等，另一堆就是假，不相等，那么这一堆就是假，根据之前记录的轻重比，就知道结果了。
另一个方案是50,50,1三堆，推理方式类似，不赘述了。 -
五只猴子分桃。半夜，第一只猴子先起来，它把桃分成了相等的五堆，多出一只。于是，它吃掉了一个，拿走了一堆； 第二只猴子起来一看，只有四堆桃。于是把四堆合在一起，分成相等的五堆，又多出一个。于是，它也吃掉了一个，拿走了一堆；.....其他几只猴子也都是 这样分的。问：这堆桃至少有多少个？（朋友说，这是小学奥数题）。
参考答案：先给这堆桃子加上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个。 -
给你5个球，每个球被抽到的可能性为30、50、20、40、10，设计一个随机算法，该算法的输出结果为本次执行的结果。输出A，B，C，D，E即可。