计算机算法设计与分析基础(第五章减治法).ppt

例题1：课本123页第一题，摆渡的士兵。 解题：1、假设小孩与士兵在同一岸边 2、考虑起始情况，即士兵：1 孩子：2 和后续情况,士兵：2孩子：2 如图： 因此可以得到n个士兵时求解的公式如下： F(1) = 4????????????????????? n=1 F(n) = F(n-1) + 4 ????? n1 5.1插入排序 简介 插入排序的过程类似玩牌时整理手中纸牌的过程。就是对 n 个元素 A [ 0, ... , n-1 ] 排序的一种方法。它的基本思想是：每步将一个待排序的对象按照其关键字的大小，插到前面已经排好序的序列中的适当位置，直到全部对象插入完毕为止。 常用的插入排序有：直接插入排序、折半插入排序、链表插入排序和希尔排序，它们划分的依据是在排好序的序列中寻找插入位置所使用方法的不同。 直接插入排序举例 待排序序列{89,45,68,90,29,34,17} 插入过程: {89} 不需比较 {45,89} {45,68,89} {45,68, 89,90} {29,45,68, 89,90} {29,34,45,68 89, 90} {17,29,34,45,68, 89, 90} 插入次数=n-1=6 比较次数=? 5.4 生成组合对象的算法 1、生成排列 排列问题指的是对于给定的多个元素求其中各种可能的序列。为了简单起见，这里仅仅考虑1到n之间的整数的排列问题。 下面介绍三种生成方法： （1）插入法 （2）Johnson-Trotter 法 （3）字典顺序法 插入法生列排列 举例：求n=3的排列 方法：在n=2的排列中插入3， 在n=1的排列中插入2。 过程： 在 1 中从右到左插入2得到 12，21 在 12 中从右到左插入3得到 123，132，312 在 21 中从右到左插入3得到 213，231，321 于是得 {123，132，312，213，231，321} Johnson-Trotter 法生成排列 其实有的算法并不需要知道规模n-1的排列就可以直接得到规模n的排列结果，Johnson-Trotter算法就是其中一种。利用这一算法求得的排列序列还是相邻序列变化最小的一个序列集合，也就是说下一个序列与上一个序列仅仅交换了两个元素的位置 。 J-T方法举例 在排列的每一分量上画一个箭头。 求最大的移动整数k，不断移动元素，直到没有元素可移动为止，掉转所有大于k 的整数方向。 移动元素：如果分量k 的箭头指向一个相邻的较小元素，则该分量在排列中是移动的。 例n=3,从123开始： 字典顺序生成排列 尽管Johnson-Trotter算法非常高效，但是似乎不是那么直观，不太符合人们的思维习惯。事实上比较自然的算法称为“字典排序（lexicographic order）算法”，它是根据单词在字典中的排列顺序得到的算法。 字典生成顺序举例 例n=3 在{1，2，3}中按字典顺序选择： 123 132 213 231 312 321 减治法生成幂集 例n=3 方法：在n=2的幂集中加入元素3，在n=1的幂集中加入元素2 ? ? , {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} 选择问题特例——查找中值 1. 蛮力策略：—— 直接基于问题本身而设计算法 先对列表按非降序排序，然后选第 k 位置上的元素即中位值。该算法 时间效率显然取决于排序算法 的效率，若用合并排序等优秀算法，本算法效率类型属于 O(nlogn) 型。 2.