天平和球 - 拼圖

※ 引述《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"....

--