南邮ACM算法与数据结构设计(2010-2011-2第5讲)1.ppt

ACM算法与数据结构设计 班 级 ：仙林校区ACM选修班 上课地点和时间 理论：教2－402：星期3 （18:30开始） 实践：（仙林）计算中心 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 第5讲:ACM竞赛之高效算法设计 5.5 再谈排序与检索 归并排序 程序：归并排序（从大到小） void merge_sort(int *A, int x, int y, int *T) { if(y-x1) { int m=x+(y-x)/2; //划分 int p=x, q=m, i=x; merge_sort(A, x, m, T); //递归求解 merge_sort(A, m, y, T); //递归求解 while( pm || qy ){ if( q = y || ( p m A[p] = A[q] )) T[i++]=A[p++]; //从左半数组复制到临时空间 else T[i++] = A[q++]; //从右半数组复制到临时空间 } for ( i=x ; iy; i++) A[i]=T[i]; //从辅助空间复制回A数组 } } 归并排序的时间复杂度：O(nlogn) 第5讲:ACM竞赛之高效算法设计 5.5 再谈排序与检索 快速排序 快速排序算法 划分问题：把数组的各个元素重排后分成左右两部分，使得左边的任意元素都小于或等于右边的任意元素。 递归求解：把左右两部分分别排序。 合并问题：不用合并，因为此时数组已经完全有序。 求第k小的数 输入n个整数和一个正整数k（1 ≤ k ≤ n），输出这些整数从小到大排序后的第k个。n ≤ 107 时间复杂度为O(n)。 第5讲:ACM竞赛之高效算法设计 5.5 再谈排序与检索 二分查找 逐步缩小范围法是一种常见的思维方法。二分查找便是基于这种思路，它遵循分治三步法，把原序列划分成元素个数尽量接近的两个子序列，然后递归查找。二分查找只适用于有序序列。 二分查找一般写成非递归形式。 第5讲:ACM竞赛之高效算法设计 5.5 再谈排序与检索 二分查找 迭代法 int bserch(int *A, int x, int y, int v) { int m; while (xy) { m = x+(y-x)/2; if (A[m] == v) return m; else if (A[m] v) y=m; else x=m+1; } return -1; } 第5讲:ACM竞赛之高效算法设计 5.6 递归和分治 棋盘覆盖问题 有一个2k*2k的方格棋盘，恰有一个方格式黑色的，其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖，且任意一个白色方格不能同时被两个或更多牌覆盖。如图所示为L型牌的4中旋转方式。 L型牌 第5讲:ACM竞赛之高效算法设计 5.6 递归和分治 棋盘覆盖问题 采用分治法：把棋盘切为4块，则每一块都是2k-1*2k-1的。有黑格的那一块可以用递归解决，但其他3块并没有黑格子，可以构造出一个黑格子，如图所示。递归边界也不难看出：k=1时一块牌子就够了。 棋盘覆盖问题的递归解法 第5讲:ACM竞赛之高效算法设计 5.7 贪心法 贪心法是通过分步决策(stepwise decision)的方法来求解问题。 贪心