算法实验一实验报告

武汉轻工大学数学与计算机学院算法分析实验报告指导老师：汤小月专业：信息管理与信息系统班级：信管1201班学号：姓名：实验一分治与递归（2学时）基本题一：基本递归算法一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。具体程序代码如下：#includeiostreamusingnamespacestd;intq(intn,intm)//正整数n的最大加数m的划分数{if((n1)||(m1))return0;//n，m需1if((n==1)||(m==1))return1;//正整数或者最大加数=1时，只有一种划分情况if(nm)returnq(n,n);//最大加数实际不能大于正整数本身if(n==m)returnq(n,m-1)+1;//递归，n的划分由其q（n，m-1）和n1=n组成returnq(n,m-1)+q(n-m,m);//正整数n的最大加数n1不大于m的划分由n1=m的划分和n1=m-1的划分组成}voidmain(){intn,m;cout请输入一个整数n（-1退出）：endl;cinn;while(n=1){cout请输入一个最大加数m：endl;cinm;cout正整数n的最大加数m的划分数为q(n,m)endl;cout请输入一个整数n（-1退出）：endl;cinn;}}进行编译如下：运行结果如下：四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。基本题二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、实验提示voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//分割棋盘//覆盖左上角子棋盘if(drtr+s&&dctc+s)//特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖右下角board[tr+s-1][tc+s-1]=t;//覆盖其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角子棋盘if(drtr+s&&dc=tc+s)//特殊方格在此棋盘中chessBoard(tr,tc+s,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角board[tr+s-1][tc+s]=t;//覆盖其余方格chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘if(dr=tr+s&&dctc+s)//特殊方格在此棋盘中chessBoard(tr+s,tc,dr,dc,s);else{//用t号L型骨牌覆盖右上角board[tr+s][tc+s-1]=t;//覆盖其余方格chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆盖右下角子棋盘if(dr=tr+s&&dc=tc+s)//特殊方格在此棋盘中chessBoard(tr+s,tc+s,dr,dc,s);else{//用t号L型骨牌覆盖左上角board[tr+s][tc+s]=t;//覆盖其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}编写程序代码如下:#includeiostreamusingnamespacestd;intboard[65][65],tile;/*tile为纸片编号*/voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//分割棋盘//覆盖左上角子棋盘if(drtr+s&&dctc+s)//特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖右下角board[tr+s-1][tc+s-1]=t;//覆盖其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角子棋盘if(drtr+s&&dc=tc+s)//特殊方格在此棋盘中chessBoard(tr,tc+s,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角board[tr+s-1][tc+s]=t;//覆盖其余方格chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘if(dr=tr+s&&dctc+s)//特殊方格在此棋盘中chessBoard(tr+s,tc,dr,dc,s);else{//用t号L型骨牌覆盖右上角board[tr+s][tc+s-1]=t;//覆盖其余方格chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆盖右下角子棋盘if(dr=tr+s&&dc=tc+s)//特殊方格在此棋盘中chessBoard(tr+s,tc+s,dr,dc,s);else{//用t号L型骨牌覆盖左上角board[tr+s][tc+s]=t;//覆盖其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}//输出最终的结果voidresult(intb[][65],intn){inti,j;for(i=1;i=n;i++){for(j=1;j=n;j++)coutb[i][j];coutendl;}}intmain(){intsize,dr,dc;cout选择输入4种不同形态的L型骨牌中的一种(4/8/16/64):endl;cinsize;cout请输入特殊的块的位置(x,y):endl;cindrdc;cout结果如下：endl;board[dr][dc]=-1;tile++;chessBoard(1,1,dr,dc,size);result(board,size);}运行调试结果如下:试运行结果如下:提高题一：二分搜索一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。2、设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标I，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。三、实验提示1、用I，j做参数，且采用传递引用或指针的形式带回值。boolBinarySearch(inta[],intn,intx,int&i,int&j){intleft=0;intright=n-1;while(leftright){intmid=(left+right)/2;if(x==a[mid]){i=j=mid;returntrue;}if(xa[mid])left=mid+1;elseright=mid-1;2}i=right;j=left;returnfalse;}intSearchTag(inta[],intn,intx){intleft=0;intright=n-1;while(leftright){intmid=(left+right)/2;if(x==a[mid])returnmid;if(xa[mid])right=mid-1;elseleft=mid+1;}return-1;}实验题1代码编写如下:#includeiostreamusingnamespacestd;voidBubbleSort(int*pData,intCount)//冒泡排序的函数，pData中从0位置处存了Count个数，该函数将数组中元素排序{intiTemp;for(inti=1;iCount;i++){for(intj=Count-1;j=i;j--){if(pData[j]pData[j-1]){iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp;}}}}boolBinarySearch(inta[],intn,intx,int&i,int&j)//数组a大小为n，数组中存放了已经排好序（升序）的数列{intleft=0;intright=n-1;intmid=0;while(leftright){mid=(left+right)/2;if(x==a[mid]){i=j=mid;returntrue;}if(xa[mid])left=mid+1;elseright=mid-1;}i=right;j=left;returnfalse;}intSearchTag(inta[],intn,intx){intleft=0;intright=n-1;while(leftright){intmid=(left+right)/2;if(x==a[mid])returnmid;if(xa[mid])right=mid-1;elseleft=mid+1;}return-1;}intmain(){inta[100];cout请输入数组中数的个数，小于100:;intnum=0;cinnum;cout请输入数组中的数：endl;for(inti=0;inum;i++)cina[i];//下面将数组a排成升序BubbleSort(a,num);cout下面输出排序后的数组：endl;for(i=0;inum;i++)printf(%4d,a[i]);coutendl;cout请输入要查找的数:;intx=0;cinx;intj=0;if(BinarySearch(a,num,x,i,j))cout找到了，位置为iendl;elsecout没找到,小于该数的最大元素位置为i大于该数的最小元素的位置为j（第一个元素的位置为0）endl;return0;}试运行调试结果如下:运行结果如下图所示:实验题2编写代码如下:#includeiostreamusingnamespacestd;/*根据题目中的隐含要求，现在将问题进行简化，假设数组中存放的数全部为整数*/voidBubbleSort(int*pData,intCount)//冒泡排序的函数，pData中从0位置处存了Count个数，该函数将数组中元素排升序{intiTemp;for(inti=1;iCount;i++){for(intj=Count-1;j=i;j--){if(pData[j]pData[j-1]){iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp;}}}}boolBinaryFind_iei(inta[],intn,int&i)//数组a大小为n，数组中存放了已经排好序（升序）的数列{intleft=0;intright=n-1;intmid=0;while(leftright){mid=(left+rig