九枚中找偏重币:两次称量的完整策略
用三结果决策树叶子数和完整分组策略判断两次称量能保证区分的候选上限。
视频暂时无法加载。请检查网络后重试,或直接下载视频。
下载视频
展开视频文字稿
- 九枚硬币中八枚正常同重,一枚偏重。天平每次有左重、平衡、右重三种结果。
- 两次称量最多形成三乘三,也就是九个独立结果叶子,所以十枚候选不可能保证区分。
- 九枚先分成三、三、三。第一次称两组:左重、右重或平衡,都会把范围锁定到一组三枚。
- 第二次在锁定的三枚里称一枚对一枚;左重、右重、平衡分别定位三枚中的一枚。
- 这样两层各有三个分支,九条路径正好覆盖九枚硬币,所以九枚能够保证找出。
- 现在模拟第一次称量平衡:请指出偏重币在哪一组三枚,并安排第二次一对一称量。小宝贝到你了。
逻辑思维
叶子上界与全分支构造,并用反向检查确认。
看一个例子
9枚中8枚正常同重、1枚偏重。称2次能否保证找出?若有10枚能否保证?
9枚能;先分3、3、3,再在锁定的3枚中称1对1。10枚不能保证。两层各3分支完整覆盖9条路径;偏重方向已知。
马上试一题
三乘三等于九。