算法-第5章-减治法(李静).ppt

* * Nim Games：/ActivityDetail.aspx?ID=140 Nim：/Nim.html Nim Game：/robban/nim1.htm 2、生成子集 集合A的“幂集”是指以集合A的所有子集为元素组成的集合。 降低规模的减治法可以用来求幂集。 减治法的缺点也是在求解规模为n的问题时，需要得到规模为n-1的问题的解。这一过程是可以避免的，使用位串法求解集合幂集就是其中的一种解决方案。 减治法生成幂集 例n=3 方法：在n=2的幂集中加入元素3，在n=1的幂集中加入元素2， 在n=0的幂集中加入元素1 ? ? , {1} //n=1 ? , {1}, {2}, {1,2} //加入元素2 ? , {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3} //加入元素3 位串法生成幂集 例n=3,元素为{a1,a2,a3} 方法： 每一个子集与一个3位二进制串b1b2b3对应，ai属于该子集时，bi=1,否则 bi=0 二进制串： 000, 001, 010, 011, 100, 101, 110, 111 对应子集： ? , {a3}, {a2}, {a2,a3}, {a1}, {a1,a3}, {a1,a2}, {a1,a2,a3} 我们可以产生从0到2n-1的二进制数来生成长度为n的所有二进制串 5.5 减常因子法 1、假币问题 有n个金币，其中一个是假币。这个假币的重量比真币的重量要轻一点，所有n-1个金币的重量是一样的。现在你有一架天平，设计高效的算法（用最少的使用天平次数）找出那个假的金币。 假币问题解法 1、用减治法（减半） 把n个硬币分为两堆，每堆?n/2?个，每次称两堆。 易见 W(1)=0 W(n)=W(?n/2?)+1 解得 W(n)= ?log2n? 假币问题解法 2、用减治法(减n/3） 把n个硬币分为三堆，每堆?n/3?个，每次称任意二堆。易见 W(1)=0 当n=1 W(n)=W(?n/3?)+1 当n1 解得 W(n)=O(?log3n?)，结果比减半法更好。 假币问题实例：n=9 用方法1（减半法）需要称 3 次。 用方法2（减n/3法）需要称 2 次。 过程： 将9个金币分为3个组，每组3个金币。 将其中的两组放在天平的两边，如果有一边轻，说明假的金币就在这个组里。如果两边一样重，说明假的金币在第三个组里。 在有假币的组中，拿出两个金币，放在天平的两边，如果有一个轻，则这个轻的就是假币，如果两个一样重，则剩下的一个就是假币。 2、俄式乘法/俄国农民法 设n、m是整数，以n为实例规模的度量。 若n为偶数，则 n·m=(n/2)· 2m 若n为奇数，则 n·m=((n-1)/2)· 2m+m 以1·m=m为算法停止的条件。 俄国农民法举例: 50×65 n m 分析 . 50 65 50×65=25×130 25 130 +130 25×130=12×260+130 12 260 6 520 3 1040 +1040 1 2080 +2080 = 3250 3、约瑟夫斯问题 约瑟夫斯是公元1世纪的犹太历史学家，他领导了反抗罗马人的武装起义，但是失败了。他和四十名犹太士兵被罗马人围困在一个山洞中。这四十个士兵宁死不屈，决定杀身成仁。但约瑟夫斯不想，但又不便公开反对，于是提出一个方法，就是四十一个人站成一个圈，从某人开始数起，凡数到三的人就让大家成全他升天，这样下去直到剩下最后一个人，这个人就自杀。大家都没有意见，于是约瑟夫斯就挑选了第31号的位置。结果所有人都死了，剩下他一个活下来投降了罗马人。这也是约瑟夫斯问题的最初提法。 约瑟夫斯问题 约瑟夫斯问题的一般提法： 设有n个以1、2、