搜狐面试题：有12个球，外形都一样，其中有一个质量和其他的不一样，给你一架天平，请问最少称几次可以把那个不同的球找出来。
题目地址：http://www.cnblogs.com/sooner/p/3281382.html
答案：
先把小球从1到12任意编号
首先天平两边分别放1、2、3、4和5、6、7、8，有如下两种情况
（1）天平平衡，则次品在剩余的四个球里，称过的八个球为标准球，天平两边分别放1、2、3和9、10、11有如下三种情况
<1>天平平衡，则12为次品
<2>9、10、11轻，则这三个球里有一个球轻，天平两边分别放9和10，如果不平，轻的为次品，如果平衡，则11轻，11为次品
<3>9、10、11重，则这三个球里有一个球重，天平两边分别放9和10，如果不平，重的为次品，如果平衡，则11重，11为次品
（2）天平不平衡，假设1、2、3、4重（1、2、3、4轻的方法与其重的方法完全一样），则天平两边分别放1、2、3、5、6和4、9、10、11、12有如下三种情况
<1>天平平衡，则天平两边分别放7和9，平衡则8为次品，不平则7为次品
<2>1、2、3、5、6重，则1、2、3里有一个球重，天平两边分别放1和2，平衡则3重，3为次品，不平则重的为次品
<3>1、2、3、5、6轻，则5、6轻或者4重，天平两边分别放4、5和9、10，如果4、5重，则4重，4为次品，如果4、5轻，则5轻，5为次品，如果平衡，则6轻，6为次品
（完）
解析：
用天平N次称量唯一质量不同小球的问题，称量N次可以得出答案的极限小球个数是（3^n-1）/2 ,也就是说称量三次最多其实可以称量出13个小球，四次可以称量出40个小球，而既要找出不同小球，又要知道它是轻还是重，则N次最多可以称量（3^n-3）/2 个，也就是说三次可以称量12个，四次可以称量39个
网友评论