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

《算法设计与分析实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析实验指导书实验一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上，并仍按同

2、样顺序叠置。四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。实验提示1、#includeinlinevoidswap(int&a,int&b){inttemp=a;a=b;b=temp;}voidperm(intlist[],intk,intm){if(k==m){for(inti=0;i<=m;i++)cout<

3、1,m);swap(list[k],list[i]);}}voidmain(){intlist[3]={1,2,3};perm(list,0,2);}2、voidhanoi(intn,inta,intb,intc){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。当搜索元

4、素在数组中时，I和j相同，均为x在数组中的位置。设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标i，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。2、在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。三、实验提示1、用I，j做参数，且采用传递引用或指针的形式带回值。boolBinarySearch(inta[],intn,intx,int&i,int&j){   int

5、left=0;   intright=n-1;   while(lefta[mid])         left=mid+1;      else         right=mid-1;   }   i=right;   j=left;   returnfalse;} intSearchTag(inta[],intn,intx){   intle

6、ft=0;   intright=n-1;   while(lefta[mid])         right=mid-1;      else         left=mid+1;   }   return-1;} 2、templatevoidQuickSort(Typea[],intp,intr){if(p

7、左半段排序QuickSort(a,q+1,r);//对右半段排序}}templateintPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将x的元素交换到右边区域while(true){while(a[++i]x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x