算法实验一实验报告

1、武汉轻工大学数学与计算机学院算法分析实验报告指导老师： 汤小月 专 业： 信息管理与信息系统 班 级： 信管1201班 学 号： 姓 名： 实验一 分治与递归（2学时）基本题一：基本递归算法一、实验目的与要求1、 熟悉C/C+语言的集成开发环境；2、 通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。具体程序代码如下：#includeusing namespace std;int q(int n,int m) /正整数n的最大加数m的划分数if(n1)|(m1if(n

2、=1)|(m=1) return 1; /正整数或者最大加数=1时，只有一种划分情况if(nm) return q(n,n); /最大加数实际不能大于正整数本身if(n=m) return q(n,m-1)+1; /递归，n的划分由其q（n，m-1）和n1=n组成return q(n,m-1)+q(n-m,m); /正整数n的最大加数n1不大于m的划分由n1=m的划分和n1=m-1的划分组成void main()int n,m;cout请输入一个整数n（-1退出）：n;while(n=1)cout请输入一个最大加数m：m;cout正整数n的最大加数m的划分数为q(n,m)endl;cout请输

3、入一个整数n（-1退出）：n;进行编译如下：运行结果如下：四、实验步骤1 理解算法思想和问题要求；2 编程实现题目要求；3 上机输入和调试自己所编的程序；4 验证分析实验结果；5 整理出实验报告。基本题二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题： 盘覆盖问题：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、实验提示void chessBoard(int

4、tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr tr + s & dc tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖

5、右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上

6、角 boardtr + stc + s = t; / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 编写程序代码如下:#include using namespace std; int board6565,tile; /* tile 为纸片编号*/ void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr tr + s & dc

7、tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角 boardtr + s - 1tc + s = t; /

8、覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上角 boardtr + stc + s = t; / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); /输出最终的结果void result(int b65,int n) int i,j; for(i=1;i=n;i+

9、) for(j=1;j=n;j+) coutbij ; coutendl; int main() int size,dr,dc; cout选择输入4种不同形态的L型骨牌中的一种(4/8/16/64): size;cout请输入特殊的块的位置(x,y): drdc;cout结果如下：endl; boarddrdc=-1; tile+; chessBoard(1,1,dr,dc,size); result(board,size); 运行调试结果如下:试运行结果如下:提高题一：二分搜索一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a0:n-1是一个已排好序的数组。请改

10、写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。2、设有n个不同的整数排好序后存放于t0:n-1中，若存在一个下标I，0in，使得ti=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。三、实验提示1、用I，j做参数，且采用传递引用或指针的形式带回值。bool BinarySearch(int a,int n,int x,int& i,int& j) int left=0; int right=n-1; while(leftamid) left=mid

11、+1; else right=mid-1;2 i=right; j=left; return false;int SearchTag(int a,int n,int x) int left=0; int right=n-1; while(leftamid) right=mid-1; else left=mid+1; return -1;实验题1代码编写如下:#include using namespace std; void BubbleSort(int* pData,int Count) /冒泡排序的函数，pData中从0位置处存了Count个数，该函数将数组中元素排序 int iTemp;

12、 for(int i=1;i=i;j-) if(pDatajpDataj-1) iTemp = pDataj-1; pDataj-1 = pDataj; pDataj = iTemp; bool BinarySearch(int a,int n,int x,int& i,int& j) /数组a大小为n，数组中存放了已经排好序（升序）的数列 int left=0; int right=n-1; int mid=0; while(leftamid) left=mid+1; else right=mid-1; i=right; j=left; return false; int SearchTag

13、(int a,int n,int x) int left=0; int right=n-1; while(leftamid) right=mid-1; else left=mid+1; return -1; int main() int a100; coutnum; cout请输入数组中的数：endl; for(int i=0;iai; /下面将数组a排成升序 BubbleSort(a,num); cout下面输出排序后的数组：endl; for(i=0;inum;i+) printf(%4d,ai); coutendl; coutx; int j=0; if(BinarySearch(a,n

14、um,x,i,j) cout找到了，位置为iendl; else cout没找到,小于该数的最大元素位置为i大于该数的最小元素的位置为j（第一个元素的位置为0）endl; return 0; 试运行调试结果如下:运行结果如下图所示:实验题2编写代码如下:#include using namespace std; /*根据题目中的隐含要求，现在将问题进行简化，假设数组中存放的数全部为整数*/ void BubbleSort(int* pData,int Count) /冒泡排序的函数，pData中从0位置处存了Count个数， 该函数将数组中元素排升序 int iTemp; for(int i=

15、1;i=i;j-) if(pDatajpDataj-1) iTemp = pDataj-1; pDataj-1 = pDataj; pDataj = iTemp; bool BinaryFind_iei(int a,int n,int& i) /数组a大小为n，数组中存放了已经排好序（升序）的数列 int left=0; int right=n-1; int mid=0; while(leftamid) left=mid; else right=mid; return false; int main() int a100; coutnum; cout请输入数组中的数：endl; for(int

16、 ii=0;iiaii; /下面将数组a排成升序 BubbleSort(a,num); cout下面输出排序后的数组：endl; for(int i=0;inum;i+) printf(%4d,ai); coutendl; int j=0; if(BinaryFind_iei(a,num,j) cout找到了，位置为jendl; else cout不存在符合第i个位置等于i的元素。endl; return 0; 试运行调试结果如下:运行结果如下:结果分析：利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等素，而二分法，由于其划分的简单和均匀的特点，是经常采用的一种有效的方

17、法，例如二分法检索。提高题二： 用分治法实现元素选择一、实验要求与目的1、了解分治法的基本思想，掌握递归程序编写方法；2、使用分治法编程，求解线形序列中第k小元素。二、实验内容1、 给定线形序列集中n个元素和一个整数k，1kn，输出这n个元素中第k小元素的值及其位置。2、 简述该算法的原理、步骤。对该算法与直接排序查找进行比较。3、 编写并调试程序。测试要求：元素个数不少于100；分三种情况：k=1、k=n和k=中位数。编写程序代码如下所示：#include #include #include#includeint partition(int a,int p,int r) int z=p,x=

18、r+1; int y=ap; int t; while(1) while(a+zy&zy); if(z=x) break; t=az; az=ax; ax=t; ap=ax; ax=y; return x;void quicksort(int a,int p,int r) int q; if(pr) q=partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); int main() for(;) int k,*a,*b,n,i,d,s; printf(请输入数组个数:); scanf(%d,&n); printf(n); a=(int *)malloc(sizeof(int)*n); /给数组a分配空间 srand(unsigned)time(NULL); b=(int *)malloc(sizeof(int)*n); /给数组b分配空间 srand(unsigned)time(NULL); for(i=0 ;in;i+) ai=ra