Re: [問題] 三臂天平

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者walkwall (會走路的牆)時間14年前 (2011/05/02 19:07)推噓3(3推 0噓 17→)

留言20則, 5人參與討論串2/2 (看更多)

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

推

newacc

05/02 19:17, , 1^F

05/02 19:17, 1^F

→

newacc

05/02 19:18, , 2^F

05/02 19:18, 2^F

→

walkwall

05/02 19:18, , 3^F

05/02 19:18, 3^F