[数学]第五章 减治法包含作业.ppt

* * * * * * * * * * * * * * * * * 在排列的每一分量上画一个箭头。 移动元素：如果分量k 的箭头指向一个相邻的较小元素，则该分量在排列中是移动的。 While 存在可移动元素 求最大的移动整数k，不断移动元素，直到没有元素可移动为止，掉转所有大于k 的整数方向。 例n=3,从123开始： 5.4.1 生成排列-JT * * 5.4.1 生成排列-字典序 尽管Johnson-Trotter算法非常高效，但是似乎不是那么直观，不太符合人们的思维习惯。事实上比较自然的算法称为“字典排序（lexicographic order）算法”，它是根据单词在字典中的排列顺序得到的算法。 * * 5.4.1 生成排列-字典序 基本思想： 从右到左扫描一个当前排列，寻找第一对连续的元素ai和ai+1，aiai+1 在ai+1及后面的元素中寻找大于ai的最小数字 放到i的位置上 ai ， ai+1 ，aj按升序从i+1位置排到n 在{1，2，3}中按字典顺序选择： 123 132 213 231 312 321 * * 5.4.2 生成子集-减一法 考虑如何用减一法生成规模为n的集合的所有子集？ 如何建立n规模和n-1规模的关系 在n-1规模集合的所有子集中添加第n个元素 * * 5.4.2 生成子集-减一法 例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 * * 5.4.2 生成子集-位串法 这是一个直接解决该问题的方法，可以对较小的集合生成幂集 例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} * * 5.1-5.4小结（减常量） 核心思想 建立一座桥梁，沟通规模为n-1的问题的解和规模为n的问题的解。 * * 5.5 减常因子法 已有例子 折半查找、用平方求幂 注意： 不要指望有许多这种类型的例子，因为这种算法的效率常常是对数的，速度非常快，并不会时常出现，不以2为因子化简的情况更是少之又少。 * * 5.5 减常因子法-假币问题 1、假币问题 有n个金币，其中一个是假币。这个假币的重量比真币的重量要轻一点，所有n-1个金币的重量是一样的。现在你有一架天平，设计高效的算法（用最少的使用天平次数）找出那个假的金币。 考虑用蛮力法，如何解？时间效率类型是？ 减治法？可类比于折半查找。 * * 1、用减治法(减半） 把n个硬币分为两堆，每堆?n/2?个，每次称一堆。 请写出递推式 易见 W(1)=0 W(n)=W(?n/2?)+1 解得 W(n)= ?log2n? 5.5 减常因子法-假币问题 * * 2、用减治法(减n/3） 把n个硬币分为三堆，每堆?n/3?个，每次称任意二堆。 易见 W(1)=0 W(n)=W(?n/3?)+a 解得 W(n)= ?log3n? 结果比减半法更好。 是否分堆数越多越好？ 5.5.1 减常因子法-假币问题 * * n m 分析 . 50 65 25 130 12 260 +130 6 520 3 1040 1 2080 +1040 2080 +2080 = 3250 整个算法只包括 折半 加倍 相加 5.5.2 减常因子法-俄式乘法 以n为实例规模的度量,则一次变换以后规模为n/2 * * 5.5.3 减常因子法-约瑟夫斯问题 约瑟夫斯