九枚中找偏重幣:兩次稱量的完整策略
用三結果決策樹葉子數和完整分組策略判斷兩次稱量能保證區分的候選上限。
影片暫時無法載入。請檢查網絡後重試,或直接下載影片。
下載影片
展開影片文字稿
- 九枚硬币中八枚正常同重,一枚偏重。天平每次有左重、平衡、右重三种结果。
- 两次称量最多形成三乘三,也就是九个独立结果叶子,所以十枚候选不可能保证区分。
- 九枚先分成三、三、三。第一次称两组:左重、右重或平衡,都会把范围锁定到一组三枚。
- 第二次在锁定的三枚里称一枚对一枚;左重、右重、平衡分别定位三枚中的一枚。
- 这样两层各有三个分支,九条路径正好覆盖九枚硬币,所以九枚能够保证找出。
- 现在模拟第一次称量平衡:请指出偏重币在哪一组三枚,并安排第二次一对一称量。小宝贝到你了。
邏輯思維
葉子上界與全分支構造,並用反向檢查確認。
看一個例子
9枚中8枚正常同重、1枚偏重。稱2次能否保證找出?若有10枚能否保證?
9枚能;先分3、3、3,再在鎖定的3枚中稱1對1。10枚不能保證。兩層各3分支完整覆蓋9條路徑;偏重方向已知。
立即試一題
三乘三等於九。