分治算法实验报告

一、实验目的1.加深对分治算法的基本思想、基本步骤和一般形式的理解，掌握分治算法设计的基本方法。2.用分治法设计L型组件填图问题的算法，分析其复杂性，并实现；3.用分治法设计求数列中的第1～k小元素的算法，分析其复杂性，并实现。二、实验内容（一）L型组件填图问题1.问题描述设B是一个n×n棋盘，n=2k,(k=1,2,3,…)。用分治法设计一个算法，使得：用若干个L型条块可以覆盖住B的除一个特殊方格外的所有方格。其中，一个L型条块可以覆盖3个方格。且任意两个L型条块不能重叠覆盖棋盘。例如：如果n=2，则存在4个方格，其中，除一个方格外，其余3个方格可被一L型条块覆盖；当n=4时，则存在16个方格，其中，除一个方格外，其余15个方格被5个L型条块覆盖。2.具体要求输入一个正整数n，表示棋盘的大小是n*n的。输出一个被L型条块覆盖的n*n棋盘。该棋盘除一个方格外，其余各方格都被L型条块覆盖住。为区别出各个方格是被哪个L型条块所覆盖，每个L型条块用不同的数字或颜色、标记表示。3.测试数据（仅作为参考）输入：8输出：A2337788221376684115996104455091010121213001718181211131317171618141111151916162014141515191920204.设计与实现的提示对2k×2k的棋盘可以划分成若干块，每块棋盘是原棋盘的子棋盘或者可以转化成原棋盘的子棋盘。注意：特殊方格的位置是任意的。而且，L型条块是可以旋转放置的。为了区分出棋盘上的方格被不同的L型条块所覆盖，每个L型条块可以用不同的数字、颜色等来标记区分。5.扩展内容可以采用可视化界面来表示各L型条块，显示其覆盖棋盘的情况。(二)求第k小项三、程序清单及实验过程和结果分析（一）#includestdafx.h#includestdio.h#defineM1024inttable[M][M];intindex;voidLFill(intstartx,intstarty,intwidth,intx,inty){inthalf=width/2;if(width==2){//填充if(table[startx][starty]==0)table[startx][starty]=index;if(table[startx+1][starty]==0)table[startx+1][starty]=index;if(table[startx][starty+1]==0)table[startx][starty+1]=index;if(table[startx+1][starty+1]==0)table[startx+1][starty+1]=index;index++;}else{//判断x，y方块位置//根据该位置用L填充if(xstartx+half){if(ystarty+half)//左上{table[startx+half-1][starty+half]=index;//左下table[startx+half][starty+half-1]=index;//右上table[startx+half][starty+half]=index;//右下index++;LFill(startx,starty,half,x,y);LFill(startx,starty+half,half,startx+half-1,starty+half);//左下LFill(startx+half,starty,half,startx+half,starty+half-1);//右上LFill(startx+half,starty+half,half,startx+half,starty+half);//右下}else{//左下table[startx+half-1][starty+half-1]=index;//左上table[startx+half][starty+half-1]=index;//右上table[startx+half][starty+half]=index;//右下index++;LFill(startx,starty,half,startx+half-1,starty+half-1);//左上LFill(startx,starty+half,half,x,y);LFill(startx+half,starty,half,startx+half,starty+half-1);//右上LFill(startx+half,starty+half,half,startx+half,starty+half);//右下}}else{if(ystarty+half)//右上{table[startx+half-1][starty+half]=index;table[startx+half-1][starty+half-1]=index;table[startx+half][starty+half]=index;index++;LFill(startx,starty,half,startx+half-1,starty+half-1);//左上LFill(startx,starty+half,half,startx+half-1,starty+half);//左下LFill(startx+half,starty,half,x,y);LFill(startx+half,starty+half,half,startx+half,starty+half);//右下}else{//右下table[startx+half][starty+half-1]=index;table[startx+half-1][starty+half-1]=index;table[startx+half-1][starty+half]=index;index++;LFill(startx,starty,half,startx+half-1,starty+half-1);//左上LFill(startx,starty+half,half,startx+half-1,starty+half);//左下LFill(startx+half,starty,half,startx+half,starty+half-1);//右上LFill(startx+half,starty+half,half,x,y);}}}}intmain(){index=1;intn,i,j,p,q;printf(输入n的大小(n=2^k):);scanf(%d,&n);for(i=0;in;i++)for(j=0;jn;j++)table[i][j]=0;printf(输入特殊位置坐标:);scanf(%d%d,&p,&q);table[p][q]=-1;LFill(0,0,n,p,q);for(i=0;in;i++){for(j=0;jn;j++){if(i==p&&j==q)printf(A);elseprintf(%5d,table[i][j]);}printf(\n);}}（二）#includestdafx.h#includestdio.h#defineM100voidsort(inta[],intn){inti,j,t;for(i=1;i=n;i++)for(j=i+1;j=n;j++)if(a[i]a[j]){t=a[i];a[i]=a[j];a[j]=t;}}intselect(inta[],intlow,inthigh,intk){intpp=low+high-1;if(pp44){sort(a,high);returna[k];}intb[50],c[50];inti=1,j=1,t=1;for(i=1;i=high;i++)//对每组排序后分别取中项存于数组c中，再对数组c排序{b[j++]=a[i];if(i%(high/5)==0||i==high){sort(b,j-1);c[t++]=b[j/2];j=1;}}intmid=t/2;sort(c,t-1);intaa[50],bb[50],cc[50];intp=1,q=1,r=1;for(i=1;i=high;i++){if(a[i]c[mid])cc[r++]=a[i];elseif(a[i]c[mid])aa[p++]=a[i];elseif(a[i]==c[mid])bb[q++]=a[i];}p--;q--;r--;if(p=k)returnselect(aa,1,p,k);elseif((p+q)=k)returnc[mid];elsereturnselect(cc,1,r,k-p-q);}intmain(){intn,a[100],i,k;scanf(%d,&n);for(i=1;i=n;i++)scanf(%d,&a[i]);scanf(%d,&k);printf(第%d小项为：%d\n,k,select(a,1,n,k));return0;}