算法设计与分析实验指导书(2011)

算法设计与分析

实 验 指 导 书

实验一 C/C++环境及递归算法（4学时）

一、实验目的与要求

1、 熟悉C/C++语言的集成开发环境；

2、通过本实验加深对递归过程的理解

二、实验内容：

掌握递归算法的概念和基本思想，分析并掌握排列问题的递归算法和Hanoi塔问题的递归算法。

三、实验题

1、设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。任意输入一串整数或字符，输出结果能够用递归方法实现整数或字符的全排列。

2、设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。

四、实验步骤

1． 理解算法思想和问题要求；

2． 编程实现题目要求；

3． 上机输入和调试自己所编的程序；

4． 验证分析实验结果；

5． 整理出实验报告。

实验提示

1、#include <iostream.h>

inline void swap(int &a,int &b)

{

int temp=a;

a=b;

b=temp;

}

void perm(int list[],int k,int m)

{

if(k==m)

{

for(int i=0;i<=m;i++)

cout<<list[i];

cout<<endl;

}

else

for(int i=k;i<=m;i++)

{

swap(list[k],list[i]);

perm(list,k+1,m);

swap(list[k],list[i]);

}

}

void main()

{

int list[3]={1,2,3};

perm(list,0,2);

}

2、void hanoi(int n, int a, int b, int c)

{

if (n > 0)

{

hanoi(n-1, a, c, b);

move(a,b);

hanoi(n-1, c, b, a);

}

}

实验二 分治算法（4学时）

一、实验目的与要求

1、熟悉二分搜索算法和快速排序算法；

2、初步掌握分治算法；

二、实验题

1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标i，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。

2、在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。

三、实验提示

1、用I，j做参数，且采用传递引用或指针的形式带回值。

bool BinarySearch(int a[],int n,int x,int& i,int& j)

{

int left=0;

int right=n-1;

while(left<right)

{

int mid=(left+right)/2;

if(x==a[mid])

{

i=j=mid;

return true;

}

if(x>a[mid])

left=mid+1;

else

right=mid-1;

}

i=right;

j=left;

return false;

}

int SearchTag(int a[],int n,int x)

{

int left=0;

int right=n-1;

while(left<right)

{

int mid=(left+right)/2;

if(x==a[mid]) return mid;

if(x>a[mid])

right=mid-1;

else

left=mid+1;

}

return -1;

}

2、

template<class Type>

void QuickSort (Type a[], int p, int r)

{

if (p<r) {

int q=Partition(a,p,r);

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

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

}

}

template<class Type>

int Partition (Type a[], int p, int r)

{

int i = p, j = r + 1;

Type x=a[p];

// 将< x的元素交换到左边区域

// 将> x的元素交换到右边区域

while (true) {

while (a[++i] <x);

while (a[- -j] >x);

if (i >= j) break;

Swap(a[i], a[j]);

}

a[p] = a[j];

a[j] = x;

return j;

}

实验三 归并排序的分治策略设计（4学时）

[实验目的]

１. 熟悉二分检索问题的线性结构表示和二分检索树表示;

２. 熟悉不同存储表示下求解二分检索问题的递归算法设计;

３. 通过实例转换, 掌握将递归算法转换成迭代算法的方法;

４. 掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.

[预习要求]

１. 认真阅读算法设计教材和数据结构教材内容, 熟悉不同存储表示下求解二分检索问题的原理或方法;

２. 针对线性结构表示和二分检索树表示设计递归算法;

３. 参考教材和课堂教学内容, 根据将递归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应的迭代算法.

[算法或程序设计参考]

线性结构

int data[10]={ /* 10个互异的、无序的原始整数 */ };

typedef struct { int s[100]; int top;} STACK;

int Partition(int *data, int low, int high)

功能: 将data[low, high]进行快速分类划分, 返回枢轴记录关键字的位置索引. int QSort1(int *data, int low, int high)

功能: 将data[low, high]进行快速分类的递归算法.

int QSort2(int *data, int low, int high)

功能: 将data[low, high]进行快速分类的迭代算法.

int BSearch1(int *data, int key)

功能: 在data数组中检索key的二分检索递归算法, 成功时返回位置索引, 否则返回-1. int BSearch2(int *data, int key)

功能: 在data数组中检索key的二分检索迭代算法, 成功时返回位置索引, 否则返回-1. 树结构

typedef struct NODE{ int key; struct NODE *lch, *rch; }TNODE, *BT;

int TSearch1(BT *t, int key, BT f, BT *p)

功能: 用递归算法在二分检索树t中查找关键字为key的元素, 成功时返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL. typedef struct Parameters { BT *t; int key; BT f; BT *p } PARA; typedef struct { PARA s[100]; int top;} STACK; int InsertBT(BT *t, int key) 功能: 在二分检索树t中插入关键字为key的元素, 成功时返回1, 否则返回0.

int TSearch2(BT *t, int key, BT f, BT *p)

功能: 用迭代算法在二分检索树t中查找关键字为key的元素, 成功时返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL.

[实验步骤]

1. 调试线性结构表示下的快速分类与二分检索递归程序, 直至正确为止;

2. 调试线性结构表示下的快速分类与二分检索迭代程序, 直至正确为止;

3. 待各功能子程序调试完毕, 去掉测试程序, 将程序整理成功能模块存盘备用.

[实验报告 …… 此处隐藏：7664字，全部文档内容请下载后查看。喜欢就下载吧 ……