小球称重

来自计算思维百科
跳转至: 导航搜索
小球称重.jpg

有6个外形一模一样的小球,但是其中有一个小球比其他小球都要重。现有一个天平,要求只称两次,找出不一样的这个球。

解决方案-分治法

给6个小球编上号分别为:a、b、c、d、e、f

每两个小球一组,把6个小球分成三组,(a,b)、(c,d)、(e,f)。先将(a,b)和(c,d)两组放到平的两端,出现以下两种情况:

(1)如果天平平衡,则不一样的小球在(e,f)组,第二次称量时将e、f两个小球放入天平两端,较重者为质量不一样的小球;

(2)如果天平不平衡,再用天平称量较重一端的两个小球,较重者为质量不一样的小球。

运用的计算思维

分治法体现的是一种规约的计算思维,它通过逐步对问题进行规约化简,将一个大的问题化成一个规模小的问题,缩小解空间,最终得到答案。

参考文献

http://blog.csdn.net/hackbuteer1/article/details/6728383