《算法合集之《一类称球问题的解法》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《一类称球问题的解法》.ppt（32页珍藏版）》请在三一办公上搜索。
1、一类称球问题的解法,问题的提出,给定N个球有个比标准球重的次品混入其中你有一架天平，用最少的次数找出这个次品。,N=3,是次品,是次品,是次品,N=3时称1次就可以找出次品,N=9,次品在A中,次品在B中,A,B,通过一次称量，可以把次品可能存在的范围从9个，缩小到3个 N=3的时候一次就能称出次品,N=9时称2次,次品在C中,A,B,更一般的情况,N=3k,A,B,C,更一般的情况,次品在A中,次品在B中,次品在C中,范围缩小到原来的1/3,更一般的情况,n=3k+1,n=3k+2和n=3k类似，也是均分成三堆每次称量把范围大致缩小到原来的1/3因此：从n个球中找次品至多要称log3n次。（
2、统一表示取上整）,判定树,log3n无疑是可行解。,最优性,为什么三分？,因为天平只有三种可能：左偏、右偏、平衡,判定树,叶子代表结果非叶子代表一次称量每个非叶子节点都有三个孩子，表示天平左偏、右偏、平衡,判定树,判定树的深度就是称量次数一个有意义的判定树至少n个叶子节点,判定树,N个叶子的三叉树的深度h=log3n,log3n是最优解,小结,引进了有力工具：判定树。将主观的直觉严谨化。三分法是解决这类问题的根本着眼点。三分时必须充分的均匀,分配的均匀性,N个叶子的三叉树的深度h=log3n,深度很大，远超过其兄弟,问题2的提出,N个球，混入了一个轻重不详的次品手中有一架天平和一个标准球用最少
3、的次数称出次品并求出次品的轻重,问题2的基本分析,可得如下信息：次品若在中，则它偏重。次品若在中，则它偏轻。,引理的提出,已知两堆球，第一堆有a个、第二堆有b个。若次品在第一堆，必是重球若次品在第二堆，必是轻球,分析总共a+b个球每个球都有可能是次品判定树至少a+b个叶子树的深度h=log3(a+b),只要称log3(a+b)次就能找到次品,引理的分析,a=3p,A1,A2,A3,b=3q,B1,B2,B3,引理的分析,A3,B3,次品在A1 或者 B2范围被缩小到p+q个球里面,引理的分析,A1,B1,A2,B2,A3,B3,次品在B1 或者 A2范围被缩小到p+q个球里面,引理的分析,A3
4、,B3,次品在A3 或者 B3范围被缩小到p+q个球里面,子问题的分析,总共a+b=3(p+q)个球无论天平怎么偏，都可以把范围缩小到p+q个球中，即原来的1/3根据a,b mod 3的余数分类，上面讨论的是a mod 3=b mod 3=0的情况。其他情况可类似进行。关键要“均”分。,引理中问题称log3(a+b)次即可。,问题2的分析,n个球，每个球都有可能是轻球或者重球，有2n种不同的可能结果判定树至少要2n个叶子节点判定树的深度h=log3(2n),问题2的分析,比较S与1,=,1L,比较S与2,2L,/,=,2H,1H,N=2,接着对n归纳,问题2的分析,假设小于n的球都能在log3
5、(2n)次内称出次品,问题2的分析,A1中的球只可能重A2 中的球只可能轻。,A2中的球只可能重A1 中的球只可能轻。,天平不平衡，次品必在A1或者A2中,归结到引理，只要称log3(p+p)次,问题2的分析,A1,A2,次品在A3中，根据归纳假设，还要称log3(2p)次,无论天平怎么偏，称完一次后都还要称log3(2p)次共称log3(2p)+1=log3(6p)=log3(2n)次,问题2的分析,|A1|=|A2|=|A3|=p总共有6p个叶子节点,问题2的分析,n=3k+2分法|A1|=k+1|A2|=k+1|A3|=k6k+4个叶子节点分摊到每个孩子是：2k+2 2k+2 2k是均匀
6、的,问题2的分析,N=3k+1分法一：k，k，k+1分摊的叶子节点：2k，2k，2k+2分法二：k+标准球，k+1，k分摊的叶子节点：2k+1，2k+1，2k,问题2的小结,log3(2n)即是问题2的解。最优性和可行性均已证明判定树是一种估界和证明最优性的有力工具。通过对判定树的研究，衍生了一条重要的原则：均匀。均分的对象不是球，而是叶子节点（即不同的结果）。,其他形式,只要求次品，不求轻重。结论是log3(2n-1)问题2去掉标准球。第一次称的时候就不能保证一定均匀。结论是log3(2n+2),万变不离其宗，解决此问题的精髓在四个字：均匀三分,总结,1、从简单入手2、求同存异3、严谨细心,
