TC经典面试题1.赛马问题

WY经典面试题2.:烧香问题

砝码称重问题

有36匹马，6个跑道，在没有计时器的情况下，至少需要赛马多少次，才能比出前三名？

答案：至少需要比较8次。

解题思路：

先把36匹马平均分成6组，假设为A，B，C，D，E，F，让每组的马赛跑一次，假设各组的名次分别为A1>A2>A3>A4>A5>A6，其他组也是如此，决出每组的第一名，分别为A1,B1,C1,D1,E1,F1。

再让这六匹马比一次，假设这六匹马的先后顺序为A1>B1>C1>D1>E1>F1，决胜出第一名，假设为A1，此时A1已经是最快的马了，此时求出了第一名，对于第二第三名，需要重新选择其他马来比较，此时淘汰出了D1，E1，F1，这三匹马在这场比赛中，已经不是前三了，它不会再快了。此时剩下B1和C1两匹马，所以还需要选择4匹马来进行比赛， 既然D1，E1，F1都淘汰了，那么D组E组F组的所有马必定淘汰了。

剩下的马就从A组B组C组中选择，由于A1是最快的，所以从A组中选出 A2 和A3出来 ，从B组选出B1, B2来，从C组选出C1来。
选择出了5匹马：A2,A3,B1,B2,C1.

为什么只选择5匹马呢？是因为，C1在才刚好能够挤进第三名，后面的C2，C3等等这些马肯定不够B组和A组的快。

对于为什么要选择A2和A3，可以举个例子：

在一个年级中，学校把整个年纪最优秀的一批人放在了一班，一班就是尖子班，学校想要知道年纪前三分别是哪个班的，尖子班的第一第二第三名也很有可能是年级的第一第二第三名！

所以选择A2 和A3就是这样的原因，对于B1和B2，也完全有能力可以竞争第二第三名，因为B1是除了A1以外最快的，很有能力竞争第二名，B2是B组第二快的，很有能力竞争第三名，对于C1，它可能只能竞争第三名了，（不过也不敢保证有黑马！） 所以这五匹马已经足够竞选第二第三名了。

所以至少需要比赛6+1+1 = 8次。

有两根材质不均匀的香，每根香都能烧一个小时，试试如何确定烧15分钟的时间段。

解题思路：
对于烧香问题，其实也很简单。

先把第一根香的两端都同时点燃，把第二根香的一端点燃。

当第一根香烧完之后，花了30分钟，此时第二根香也同样烧了30分钟，剩下的香还能烧30分钟，然后再把第二根香的另一头点燃，这样第二根香剩下的就刚好能烧15分钟。

砝码称重问题

有9个砝码，其中有一个砝码的质量比其他8个砝码质量轻，试问需要用一个没有标识的天秤称几次才能找到那个轻的砝码？

答案是2次

解析：第一次一边放三个砝码，轻的那边就是轻砝码所在组，一样重就是在剩下的三个没有称的砝码中。
第二次一边放一个砝码，轻的那个就是要找的砝码，一样重就是剩下那个没称的砝码。