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