实验二 递归与分治策略

实验二 递归与分治策略

（一）、实验目的

通过编程实现递归与分治策略的有关算法，理解递归与分治策略算法的原理，掌握递归与分治策略基本思想与应用技巧。

（二）、实验内容及要求

实验内容

1. 二分搜索算法

设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

实验提示：

public static boolean binarySearch(int []a,int x,int left,int right,int []ind)

1

{

int middle;

while (left <= right) {

middle = (left + right)/2;

if (x = = a[middle]) {

ind[0]=ind[1]=middle;

return true;

}

if (x > a[middle]) left = middle + 1;

else right = middle - 1;

}

2

ind[0]=right;

ind[1]=left;

return false;

}

返回的ind[0]是小于x的最大元素的位置，ind[1]是大于x的最小元素位置.

2. 合并排序

设a[0:n-1]是一个无序的数组，采用合并排序算法，对其进行从小到大排序。

实验提示：

#define n 10

int bridge[n]; /*归并排序算法用到的中间数组 */

public static void main()

3

{

int obj[n]；

输入排序前的n个数，存入数组obj；

mergeSort(obj, 0, obj.length - 1); //归并排序

输出排序后的数组obj；

}

public static void mergeSort(int obj[], int left, int right)

{

if (leftint i=(left+right)/2; //取中点

mergeSort(obj, left, i);

4

mergeSort(obj, i+1, right);

merge(obj, bridge,left, i, right); //合并到数组bridge

copy(obj, bridge,left, right); //复制回数组a

}

}

private void merge(int[] obj,int []bridge, int left, int center, int right)

{

int mid = center + 1;

int third = left;

int tmp = left;

while (left <= center && mid <= right)

5

{

//从两个数组中取出小的放入中间数组

if (obj[left]<=obj[mid]) bridge[third++] = obj[left++];

else bridge[third++] = obj[mid++];

}

//剩余部分依次置入中间数组

while (mid <= right) bridge[third++] = obj[mid++];

while (left <= center) bridge[third++] = obj[left++];

copy(obj, bridge,tmp, right); //将中间数组的内容拷贝回原数组

}

private void copy(int[] obj, int[] bridge, int left, int right)

6

{

while (left <= right)

{

obj[left] = bridge[left];

left++;

}

}

3. 快速排序

设a[0:n-1]是一个无序的数组，采用合并排序算法，对其进行从小到大排序。

实验提示：

#define n 10

7

int a[n]; /*快速排序算法用到的数组 */

public static void main()

{

输入排序前的n个数，存入数组a；qSort(0, a.length - 1); //归并排序

输出排序后的数组a；

}

private static void qSort(int p, int r)

{

if (pint q=partition(p,r);

8

qSort (p,q-1); //对左半段排序

qSort (q+1,r); //对右半段排序

}

}

private static int partition (int p, int r)

{

int i = p, j = r + 1;

int x = a[p];

while (true) {

while (a[++i] < x&(iwhile (a[--j] > x);

9

if (i >= j) break;

int tmp=a[i]; //交换a[i]和a[j]

a[i]=a[j];

a[j]=tmp;

}

a[p] = a[j];

a[j] = x;

return j;

}

4. 最接近点对问题

给定平面上的至少n个点（n〉=20），找出其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。输出具体的距离最小的两个点坐标以及最小距离值

10

实验提示：

参考教材p48－52

实验要求

1． 参照实验提示给出的部分程序代码，完善程序，实现算法。

2． 给出不同的输入，输出正确结果。

（三）、实验步骤

1．对于以上题目要认真分析和理解题意，任选2个题目设计出算法；

2．详细写出正确的高级语言源程序（java或c）；

3．上机录入并调试程序；

4．请指导教师审查程序和运行结果并评定成绩；

5．撰写并上交实验报告。

11

（四）、实验报告内容

1. 班级、学号、姓名、实验日期；

2. 实验题目；

3. 对于实验题目的理解与说明；

4. 程序功能与框架；

5. 设计说明（存储结构、特别构思等）；

6. 调试报告（调试过程中遇到的问题及如何解决此问题，程序设计的得失，对于改进程序的设想、经验、体会等）；

7. 对算法的时间复杂性进行分析；

8. 附录：源程序清单（加必要的注释）、测试数据及运行结果。

（五）、实验成绩考核方法

实验成绩由实验结果、问题回答以及实验报告综合评定。

12