实验指导书-实验1

算法设计与分析实验指导书（计算机科学与技术系）编写兰州交通大学电子与信息工程学院2018年3月目录实验1递归与分治法…………………………….........................................1实验一递归与分治法一、实验目的（1）理解递归程序运行过程中参数的变化情况，熟悉递归程序的复杂度分析与其他程序的区别。（2）通过实验掌握分治策略算法设计思想和方法；（3）培养学生的动手能力。二、实验仪器设备（1）计算机；（2）C++编译调试环境。三、实验原理掌握将算法转换为可运行程序的步骤。四、实验内容及注意事项（1）输出全排列。（2）正整数的划分个数。（3）汉诺塔问题。（4）二分查找。（5）大整数的乘法。（6）合并排序。（7）快速排序。（8）棋盘覆盖问题。（8）循环赛日程表。五、实验步骤（1）输出全排列问题。#includestdio.h#includestdlib.hvoidSwap(int&a,int&b){inttemp=a;a=b;b=temp;}voidPerm(int*list,intk,intm){if(k==m){for(inti=0;i=m;i++)printf(%d,list[i]);printf(\n);}else{for(inti=k;i=m;i++){Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}}intmain(){intlist[8]={1,2,3,4,5,7,8,9};Perm(list,0,5);system(pause);return0;}（2）大整数的划分数#includestdio.hintsplit(intn,intm){if(n1||m1)return0;if(n==1||m==1)return1;if(nm)returnsplit(n,n);if(n==m)return(split(n,m-1)+1);if(nm)return(split(n,m-1)+split((n-m),m));}intmain(){printf(%d,split(6,6));return0;}（3）汉诺塔问题#includeiostreamusingnamespacestd;voidTowersofHanoi(intn,charx,chary,charz){if(n){TowersofHanoi(n-1,x,z,y);coutFromxToyendl;TowersofHanoi(n-1,z,y,x);//}}intmain(){TowersofHanoi(3,'A','B','C');system(pause);return0;}（4）二分查找#includeiostreamusingnamespacestd;//非递归查找intBinarySearch(int*array,intaSize,intkey){if(array==NULL||aSize==0)return-1;intlow=0;inthigh=aSize-1;intmid=0;while(low=high){mid=(low+high)/2;if(array[mid]key)low=mid+1;elseif(array[mid]key)high=mid-1;elsereturnmid;}return-1;}//递归intBinarySearchRecursive(int*array,intlow,inthigh,intkey){if(lowhigh)return-1;intmid=(low+high)/2;if(array[mid]==key)returnmid;elseif(array[mid]key)returnBinarySearchRecursive(array,mid+1,high,key);elsereturnBinarySearchRecursive(array,low,mid-1,key);}intmain(){intarray[10];for(inti=0;i10;i++)array[i]=i;coutNorecursive:endl;coutposition:BinarySearch(array,10,6)endl;coutrecursive:endl;coutposition:BinarySearchRecursive(array,0,9,6)endl;system(pause);return0;}（5）大整数的乘法#includecstdio#includecmath#includeiostreamusingnamespacestd;#defineSIGN(A)((A0)?1:-1)intdivideConquer(intX,intY,intn){intsign=SIGN(X)*SIGN(Y);intx=abs(X);inty=abs(Y);if(x==0||y==0){return0;}elseif(n==1){returnsign*x*y;}else{intA=(int)x/pow(10,(int)(n/2));intB=x-A*pow(10,n/2);intC=(int)y/pow(10,(int)(n/2));intD=y-C*pow(10,n/2);intAC=divideConquer(A,C,n/2);intBD=divideConquer(B,D,n/2);intABDC=divideConquer((A-B),(D-C),n/2)+AC+BD;returnsign*(AC*pow(10,n)+ABDC*pow(10,(int)(n/2))+BD);}}intmain(){intx,y,n;printf(input2bignumbersandthedigitofthem,seperatewithblank:);scanf(%d%d%d,&x,&y,&n);printf(x和y的乘积为：%d,divideConquer(x,y,n));system(pause);}（6）合并排序#includeiostreamusingnamespacestd;voidMerge(int*array,intlow,intmiddle,inthigh)//合并{int*A=newint[high-low+1];//临时数组，存储个数为high-low+1个数据inti=low;intj=middle+1;intk=0;while(i=middle&&j=high)//直至前半部或后半部数据完全录入暂存{if(array[i]array[j])//如果前半部的数据小于后半部的，前半部数据暂存A[k++]=array[i++];else//否则后半部数据暂存，并下标自加A[k++]=array[j++];}while(i=middle)//保证前半部数据录入暂存A[k++]=array[i++];while(j=high)//保证后半部数据录入暂存A[k++]=array[j++];for(i=low;i=high;i++)//将暂存的数据重新填充至array[low]--array[high]中array[i]=A[i-low];}voidMergeSort(int*array,intlow,inthigh){intmiddle;//分割问题if(lowhigh){middle=(low+high)/2;//分割问题MergeSort(array,low,middle);//前半部MergeSort(array,middle+1,high);//后半部Merge(array,low,middle,high);//合并}}intmain(){intn;cout输入需要排列数据的个数：;cinn;//录入需要排列的个数int*array=newint[n];coutendl请输入数据：endl;for(inti=0;in;i++)cinarray[i];//录入未排序的数据MergeSort(array,0,n-1);//进行排序cout排列后数据：endl;for(intj=0;jn;j++)//输出排列结果coutarray[j];coutendl;system(pause);return0;}（7）快速排序#includeiostreamusingnamespacestd;voidquickSort(inta[],int,int);intmain(){intarray[]={34,65,12,43,67,5,78,10,3,70},k;intlen=sizeof(array)/sizeof(int);coutTheorginalarrayis:endl;for(k=0;klen;k++)coutarray[k],;coutendl;quickSort(array,0,len-1);coutThesortedarrayis:endl;for(k=0;klen;k++)coutarray[k],;coutendl;system(pause);return0;}voidquickSort(ints[],intl,intr){if(lr){inti=l,j=r,x=s[l];while(ij){while(ij&&s[j]=x)//从右向左找第一个小于x的数j--;if(ij)s[i++]=s[j];while(ij&&s[i]x)//从左向右找第一个大于等于x的数i++;if(ij)s[j--]=s[i];}s[i]=x;quickSort(s,l,i-1);//递归调用quickSort(s,i+1,r);}}（8）棋盘覆盖在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。问题:用4种不同形态的L型骨牌,覆盖给定特殊棋盘上除特殊方格以外的所有方格，且任何2个不得重叠。特殊方格在棋盘上出现的位置有4k种情形。因而对任何k=0，有4k种不同的特殊棋盘。易知，在任何一个2k*2k的棋盘中，用到的L型骨牌个数恰为(4k-1)/3。1)当k0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘,Figure(a)所示。2)特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。3)为将无特殊方格子棋盘转化为特殊棋盘，可以用一个骨牌覆盖3个较小棋盘的会合处，如Figure(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。4)递归地使用这种分割，直至棋盘简化为棋盘1×1。#includeiostream#includeiomanip//包含设置域宽的头文件#includestdlib.h//标准库usingnamespacestd;inttile=0;int*(*board)=NULL;//定义指向指针的指针用于动态的创建用于存储骨牌号的数组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