理解递归的概念
掌握设计有效算法的分治策略：分治法的基本思想
通过范例学习分治策略的算法分析及设计技巧
二分搜索技术、大整数的乘法、Strassen矩阵乘法
合并排序和快速排序
2021-11-10 19:34:28
1.48MB
1
二维空间的最接近点对问题
下面来考虑二维的情形。
选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。
递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2 ，如图2-9所示。
能否在线性时间内找到p,q？
考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中，如图2-10所示。
由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。
图2-9距离直线l小于d的所有点
图2-10包含q的d×2d矩形R
2021-11-05 10:39:25
1.69MB
1
【问题描述】每次都是优化选出一个元素（分组后的中位数）为划分基准，在线性时间内寻找第i小元素。提示：分组时的组的个数为n/5的向下取整；分组后的中位数取第（num_group/2向上取整）小的元素。
【输入形式】在屏幕上输入若干整数，各数间都以一个空格分隔。再输入要寻找的元素是数组从小到大顺序中第几个位置。
【输出形式】第一次划分基准元素，和数组从小到大顺序中要寻找的那个位置的元素。
【样例1输入】
2 9 8 0 7 10 1 12 3 14 5 13 6 11 4
3
【样例1输出】
7
2
【样例1说明】
输入：15个整数，以空格分隔。要寻找第3小元素。
输出：7表示第一划分基准元素为7，2表示第3小元素为2。
2021-10-28 22:31:30
871B
1