Re: [問題] 天平和球
※ 引述《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)
推
08/21 00:18, , 1F
08/21 00:18, 1F
推
08/21 10:22, , 2F
08/21 10:22, 2F
推
08/21 14:11, , 3F
08/21 14:11, 3F
推
08/21 19:49, , 4F
08/21 19:49, 4F
推
08/21 21:59, , 5F
08/21 21:59, 5F
→
08/22 06:21, , 6F
08/22 06:21, 6F
→
08/22 06:23, , 7F
08/22 06:23, 7F
→
08/22 06:27, , 8F
08/22 06:27, 8F
推
08/22 23:53, , 9F
08/22 23:53, 9F
推
08/26 18:23, , 10F
08/26 18:23, 10F
推
08/29 13:54, , 11F
08/29 13:54, 11F
→
08/29 13:55, , 12F
08/29 13:55, 12F
→
08/29 13:57, , 13F
08/29 13:57, 13F
推
08/29 14:02, , 14F
08/29 14:02, 14F
討論串 (同標題文章)