问题的提出 给定N个球 有个比标准球重的次品混入其中 你有一架天平用最少的次数找出这个次品 N = 3 N = 9 更一般的情况 更一般的情况 更一般的情况 n = 3k+1, n = 3k+2和n=3k类似也是均分成三堆 每次称量把范围大致缩小到原来的1/3 因此从n个球中找次品至多要称[log3n]次[]统一表示取上整 判定树 判定树 叶子代表结果 非叶子代表一次称量 每个非叶子节点都有三个孩