Re: [問題] 三臂天平

[walkwall (會走路的牆)]

先來試解看看...
後面有別人做法更好再說 -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:第一題如果第一次先測4 4 4呢？
→ newacc:如果同重就測剩下的任三個，反正題目只要找哪一個XD
→ walkwall:444秤完會剩下四個
→ walkwall:而且我的三次解也是第一步秤444
→ walkwall:喔...如果不需要知道輕重  那我也是兩次結束辣-x-
→ walkwall:對不起我自動腦補要判斷輕重
→ walkwall:   ┌─────┐   啊
→ walkwall:  ╱╲ 原PO鮮乳 ╲  啊
→ walkwall: │﹊│﹊﹊﹊﹊﹊│ 啊
→ walkwall: │  │ ′    ‵ │ 要
→ walkwall: │∪│    ▽    │ 壞
→ walkwall: │  │保存期限：│ 掉
→ walkwall: │  │  昨天    │ 了
→ walkwall: └─┴─────┘ ！
推 puzzlez::噗～走牆叔真搞笑.....
→ EIORU:           10年前
→ Maidanlaw:第一次測444 第二次測222 既能找出該法碼也能知道輕重
→ Maidanlaw:我耍笨了 囧rz
推 puzzlez:  沒關係，不要緊的，人生難得幾回走牆嘛～( ′-`)y-～
→ walkwall:-口-!