第5章_减治法.ppt

* 第5章 减治法 Page * 交换 筛选 交换 筛选 8 6 9 10 1 11 5 4 2 16 1 6 9 10 8 11 5 4 2 16 6 1 9 10 8 11 5 4 2 16 2 1 9 10 8 11 5 4 6 16 * 第5章 减治法 Page * 交换 筛选 交换 筛选 5 1 9 10 8 11 4 2 6 16 2 1 9 10 8 11 4 5 6 16 4 1 9 10 8 11 2 5 6 16 1 4 9 10 8 11 2 5 6 16 * 第5章 减治法 Page * 交换 2 4 9 10 8 11 1 5 6 16 1 4 9 10 8 11 2 5 6 16 堆排序小结 （1）建堆/堆调整方法： 筛选法：将结点与其孩子结点比较。 （2）堆排序方法： 先建堆； 取出堆顶； 剩下元素再调整为堆； 直至剩下一个元素为止。 * 第5章 减治法 Page * * Reduce and Conquer Method * 第5章 减治法 5.1 概述 5.2 查找问题中的减治法 5.3 排序问题中的减治法 5.4 组合问题中的减治法 阅读材料 假币问题的复杂版本 * Reduce and Conquer Method * 5.4 组合问题中的减治法 5.4.1 淘汰赛冠军问题 5.4.2 假币问题 * Reduce and Conquer Method * 淘汰赛冠军问题 [问题] 假设有n=2k个选手进行竞技淘汰赛，最后决出冠军的选手，请设计淘汰赛的过程。 [想法] 分治法是将所有选手分成两部分，每部分决出胜者后，让这些胜者再进行比赛，最后决出冠军。 减治法：将所有选手分成n/2组，每组两个选手比赛，败者被淘汰，然后再将剩余选手分成n/4组，每组两个选手进行比赛，…直到剩余最后两个选手决出冠军。 T（n）=O(n) * Reduce and Conquer Method * 算法5.8——淘汰赛冠军问题 string Game(string r[ ], int n) { i=n; while (i1) { i=i/2; for (j=0; ji; j++) if (Comp(r[j+i], r[j])) r[j]=r[j+i]; //胜者放在 r[j] 中, j=0,1,2,…,i/2 -1 } return r[0]; } 淘汰赛冠军问题 * Reduce and Conquer Method * [算法分析] 因为n=2k，所以，外层的while循环共执行k次，在每一次执行时，内层的for循环的执行次数分别是n/2，n/4，…，1，而函数comp可以在常数时间内完成，因此，算法5.8的执行时间为： 淘汰赛冠军问题 * Reduce and Conquer Method * 5.4 组合问题中的减治法 5.4.1 淘汰赛冠军问题 5.4.2 假币问题 * Reduce and Conquer Method * 假币问题? [问题] 在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，但不知道轻多少，假币问题是要求设计一个高效的算法来检测出这枚假币。 * Reduce and Conquer Method * 问题的解决是经过一系列比较和判断，可以用判定树来描述这个判定过程。 [想法] 解决这个问题的最自然的想法就是一分为二，也就是把硬币分成两组。（1）把n 枚硬币分成两组，每组有 枚硬币，如果 n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。（2）如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理，假币一定在较轻的那组里。 假币问题 * Reduce and Conquer Method * 在假币问题中，每次用天平比较后，只需解决一个规模减半的问题，所以，它属于一个减治算法。该算法在最坏情况下的时间性能有这样一个递推式： 求解这个递推式，得到T(n)=O(log2n)。 假币问题 * Reduce and Conquer Method * 硬币分成两组不一定最佳，考虑分成三组，前两组有 组硬币，其余的硬币作为第三组，将前两组硬币放到天平上，如果他们的重量相同，则假币一定在第三组中，用同样的方法对第三组进行处理；如果前两组