先來試解看看... 後面有別人做法更好再說 -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)