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