Re: [問題] 天平和球

[LPH66 ((short)(-15074))]

※ 引述《EIORU ()》之銘言：
: 之前都是只有一個球不一樣 這次來個都不一樣的
: 如果有10顆大小外觀相同但重量完全不一樣的球
: 至少要使用多少次天平可以保證找到
: (1)最重的球
9次

最重的球必須直接或間接和其他所有球量過

一個方法是簡單的淘汰賽

: (2)最重和最輕的球
13次

無論如何  在選出最重的之後

所有第一次被秤就被淘汰的球集合起來找最輕  (因為最輕的只會在這裡面)

這些球至少有5個  因為如果有更少  表示多於5個球第一次被稱是比較重的

但能夠比那些球輕的球只有不足5個  矛盾

於是這些球套(1)的想法  至少要再4次才能找出最輕  故一共13次

一個方法是先秤5次分出重組和輕組  再分別做淘汰賽  恰好13次

: (3)所有球的輕重順序
無論如何  稱的方法總是能夠列成一棵(二元的)決策樹

這棵樹的最大高度即為此種方法所需要的次數

(高度即為由最上走到某個最下結果的最長距離)

顯然  高度為k的決策樹最多只能分出有2^k種結果

由於10球的順序結果一共有10!=3628800種  且2^21<10!<2^22

因而任何排序10球的決策樹高度都至少為22  即所求次數的下限是22

至於上限

一個明顯的上限是45次  只需要簡單的每次都找出最大(或最小)的排起來即是

(這在演算法中稱為選擇排序法 Selection Sort)

另外一個排序法稱做合併排序法(Merge Sort)的

A\
  1,AB\
B/     \
        3,ABCD-----------\
C\     /                  \
  1,CD/                    \
D/                          \
E\                           \
  1,EF\                       9,ABCDEFGHIJ
F/     \                     /
        3,EFGH\             /
G\     /       \           /
  1,GH/         \         /
H/               5,EFGHIJ/
                /
I\             /
  1,IJ--------/
J/

數字寫的是合併成逗號右邊那組需要的最多次數  等於合起來的那組個數減1

這給出了1*5+3+3+5+9=25次的上限

至於正確答案是22~25之中的哪一個我就不知道了

--
本來第一個想到的是快速排序法(Quick Sort)

但快排在最差情形也會用到45次  所以只好退而求其次拿Merge Sort出來說嘴了XD

--
資料結構與演算法啊...(遠目)  想當初高中玩資訊競賽就在和這些東西打交道 orz

--
"LPH" is for "Let Program Heal us"....

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.121.26.88
※ 編輯: LPH66           來自: 122.121.26.88        (08/20 22:50)
推 FOXSMALL:詳細！~~推
推 rehearttw:強！推！
推 o99:厲害! 推!
推 puzzlez:推推推～^^
推 xx5236294roy:推~
→ joeyeh:關於計算機與實際生活,計算機一次只能針對兩個單元最運算
→ joeyeh:但在日常的生活中,我們可以將球任意分組然後用天平做一判定
→ joeyeh:但qs在n很小時遇上最差n^2的機率是高的
推 hcldesmond:推!
推 Huntermagic:推
推 EricTao:問一下 若找最重的過程剛好第一次就選到最重
→ EricTao:那麼在第二輪就有9個球要測，這樣要保證測得
→ EricTao:不就要8次? 第二輪只測5顆應該是在運氣好的情況吧?
推 EricTao:感覺1、2題要"保証"測得只有分別9＆8次 也不會更多了