先来试解看看... 後面有别人做法更好再说 -v- 防雷页一页,现在後悔还来得及唷~ ※ 引述《EIORU ()》之铭言： : 某个天平有三端 一次可以知道三端的重量顺序 但无法得知重量差比例 : (1)★ : 有16个外观相同的砝码 其中一个重量不同 : 至少要使用几次天平 才能找到该砝码 --- Ans : 3次 --- 虽然我直觉上是两次, 但是如果第一次分堆後同重或同轻, 则该堆只能最多四个(三堆各放一个,同重则异常的是最後一个). 但是如果第一次秤三堆分别为 4 4 4, 同重则会剩下八种可能性(剩下四个或轻或重) 就无法一次秤完,所以只能三次 这是非正式证明,属於直觉描述,等待其他人补完完整证明 同样是三次解当中,下列方法两次秤完後不确定的球数最少 1.将三堆分别放置四个球 2-1.若三堆有一堆与其他两堆重量不同,较轻则该堆含有轻球,计重则该堆含有重球 此时将此四颗球其中三颗分别放置天平上 若重量不同则该球异常,若重量相同,则剩下的第四颗球重量异常 2-2.若步骤1.的三堆重量相同,也是将三颗球放置於天平上 由於至少两堆重量会相同,不同的那一堆就是异常球 如果三堆都相同,就是没秤到的最後一颗球异常 可是这颗球的异常是重是轻未知,所以要量第三次 但是也只有这颗球异常才需要秤三次,为秤三次解中次数期望值最低者 : (2)★★★ : 有1g,2g,...,20g砝码各一个 : 至少要测几次 能保证测到在210g范围内的任意物品重量(已知重量为正整数克) Ans : 6次 首先,该待秤物品只能放在三个秤盘其中之一,假定为Xg 因此,假定其他两盘法码重分别为Ag,Bg,A>B 每次秤只能秤得5种资讯(X>A,X=A,A>X>B,X=B,X<B) 其中只有X>A,A>X>B,X<B三种情形X有多於一种以上的可能 因此视资讯量上限为3+,3^5=243>210>3^4=81 可以知道最少要秤五次,五次为下限 详细计算的话,三元搜寻的话是 F(三元搜寻秤的次数)=能分辨最大数量, F(0)=1,F(1)=5,F(2)=17,F(3)=53,F(4)=161... F(k+1)=3*F(k)+2 但是这边要注意到,砝码的总重量只有1+2+...+20=210 因此将法码分AB两堆时,总重量 A+B不能大於210 这导致X大於105时,无法做三元搜寻,只能做二元搜寻 因此5次也近乎不可能,这若要证明....也只能待其他人补完 二元搜寻的话 G(二元搜寻秤的次数)=能分辨的最大数量 G(0)=1,G(1)=3,G(2)=7,.... G(k+1)=2*G(k)+1=2^(k+2)-1 以下是六次做法,(A,B)表示另外两堆分别为Ag,Bg 1.(147,63) X=147与X=63直接得到答案 若X<63,则使用三元搜寻,3^4=81<161=F(4),再秤4次之内可搜寻完 若X>147,则二元搜寻148~210,共有63个数,63=G(5),可以五次内秤完 若147>X>63,则继续下一步 2.(115,95) X=115或X=95同上 若X<95,64~94有31个数,31<53=F(3),再三次三元搜寻内结束 若X>115,116~146有31个数,31=G(4),可四次二元搜寻内结束 若115>X>95,继续下一步 3.(99,0) X=99不罗嗦 X>99,100~114有15个数,15=G(3),再三次二元结束 X<99,也只剩下98,97,96,庆蔡秤都码三次以内结束 所以至少秤六次就结束了~~ ※ 编辑: walkwall 来自: 140.117.168.84 (05/02 19:18)