杭州某IT上市公司笔试题目

1.现在有12个金币,其中一个有质量问题(或重或轻),还有一个无砝码的天平,让你称三次怎么样找到那个有质量问题的金币?

2.现在有一壶水(大于2L)和2个空杯子,一只500ml,另一只300ml,怎么样使每个杯子都含100ml的水?

3.一块园型蛋糕分给3个人,怎么样分他们感觉都公平?

4.还有一个奇怪的题目:现在有三组数据推理:6384>183,3258>108,3194>413,请问 6192>?

大家看看,给出几过好的解决方案..

1. 这个是有名的乒乓球问题。但是实际上，称3次是可以分辨13个球，甚至14个球（如果还有一个标准重量的球的话）。这可以由信息论推导出来的。

2. 给一种解如下：

pot   300ml   500ml
1000+     0       0
500+      0     500
500+    300     200
800+      0     200
800+    200       0
300+    200     500
300+    300     400
0       300     400
400     300       0
400       0     300
100     300     300
100     100     500
100     100       0
0       100     100

第一个题目是比较经典的智力题，俺记得第一次解这个题目是学二叉树的时候，俺当时死活要跟二叉树联系起来，汗

一种解法：

第一个量重比较是 4 对 4

考虑以下两个可能：

A) 左边比较重
B) 两边一样重

若是 A)，那么假的金币就在天秤上，即是说余下的金币全都是真的，为了方便，把金币命名如下：

H1, H2, H3, H4, L1, L2, L3, L4, R1, R2, R3, R4

当中 H1, H2, H3, H4 是在重的一端的金币； L1, L2, L3, L4 是在轻的一端的金币；而 R1, R2, R3, R4 就是余下的真金币。在这情形下，有两个可能性：假的金币较重而且是 H1, H2, H3, H4 的其中一个；或者假的金币较轻而且是 L1, L2, L3, L4 的其中一个

第二个量重比较是这样的：

H1,H2,L1,L2 对 H3,L3,R1,R2

有 3 个可能性：

C) 左边较重
D) 右边较重
E) 两边一样重

若是 C)，那么假金币只可能是 H1, H2 或 L3 ，最后的量重是 H1 对 H2，就可以得出答案了

若是 D)，那么假金币只可能是 L1, L2 或 H3，最后的量重是 L1 对 L2，就可以得出答案了

若是 E)，那么假金币只可能是 H4 或 L4，最后的量重是 H4 对 R1，就可以得出答案了

到此 A) 这个可能是完成了

现在处理 B)，这时天秤上的金币都是真的，假的金币就在余下的金币內，以以下方法把金币命名：

R1, R2, R3, R4, R5, R6, R7, R8, U1, U2, U3, U4

当中 R 是真的金币，U 是余下的金币。

第二次量重是这样的：

R1, R2, R3 对 U1, U2, U3

有两个可能：

F) 左边较轻
G) 两边一样重

若是 F)，那么假金币就是较轻的，而且是在 U1, U2, U3 之中。最后比较 U1 和 U2 就知道答案了。

若是 G)，那么 U4 就是假金币但还未知道这个金币是较重还是较轻，只需把它和其中一个真金币比较一下就知道了。

我知道第三个题，哈哈，如果不是奶油蛋糕的话，那么就横着切三份呗

好像楼上都说的有问题，呵呵

我来补充一下怎么称14个球（设为A1-A14）。前提是有多一个标准球A0。

A0-A4 vs A5-A9
如果相等，则坏球在A10-A14这5个球中。

5球（重新记做A1-A5外加一个A0为标准球）的称法如下：
A0,A1 vs A2,A3
如果相等，则坏球是A4或A5，取其中一个与A0再称一次即可判断（这个不用说了，人人都知道怎么称）。
如果不等，假设A0,A1 > A2,A3（<的话，下面的判断都反一反即可），则再称一次：
A2 vs A3
如果相等，则坏球是A1，否则A1就是好球，坏球在A2、A3中，根据上一次称量结果可以判断出，坏球比标准球轻，所以A2 vs A3的结果，轻的那个就是坏球。

如果第一次称量不等，则坏球在A1-A9这9个球中，并且你知道一个不等关系，我们假设是A0-A4 > A5-A9（<的话，下面的判断都反一反即可）。

然后测A1,A2,A5 vs A3,A4,A6
如果相等，则坏球在A7,A8,A9中，并且可以推导出其中轻的那个是坏球，再称一次肯定能找出坏的那个。
如果A1,A2,A5 > A3,A4,A6
则坏球在A1,A2,A6中，并且可以推导出A1,A2 > A0,A6
反之坏球在A5,A3,A4中，并且可以推导出A5,A0 < A3,A4
不难看出这两种情况实际是等价的，只需比较两个同处一侧的球就可以判断哪个是坏球了。


如果没有标准球A0的话，那第一次称量就不能5对5了，只能4对4，所以最多只能称13个球。第一次相等的情况跟前面完全一样，如果不等，就是那8个球有问题，比前面的9个还少一个，所以你肯定可以称出来。

这个称球问题可以推广，比如4次最多可以称量27+14=41个。前提也是你多一个标准球，这样第一次称量就是14 vs 13+1，如果相等，坏球就在剩下的14个里，就转化为了前面描述的14球称量问题。如果不等，则坏球在27个里，通过合理调配，你肯定可以把它们区别成3组分别9个，通过一次称量判断出坏球到底是在哪9个球中。因为一次称量有3种状态，可以把一堆球分成3组。以下每次都是3组1分，所以27=3的3次方就是表示3次称量就可以区分出来了。

不难看出，如果5次的话，可以最多称量27*3+41=122个，以下可以逐级类推，有兴趣的同志可以求出它的公式。

最后是一个思考题，既然可以3个一组分，为什么3次称量只能称14个而不是27个呢？

我也给想成二叉树了...

第二题答案：

其他题呢

现在国内的面试题考智力，还是脑筋急转弯啊。。我晕。。。99。99%的项目恐怕是用不到的吧。