算法设计与分析实验指导书
实验一 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;。