分治算法实验报告.doc
- 格式：doc
- 大小：73.00 KB
- 文档页数：6
一、实验目的 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 输出：A 2 3 3 7 7 8 8 2 2 1 3 7 6 6 8 4 1 1 5 9 9 6 10 4 4 5 5 0 9 10 10 12 12 13 0 0 17 18 18 12 11 13 13 17 17 16 18 14 11 11 15 19 16 16 20 14 14 15 15 19 19 20 20
4. 设计与实现的提示 对2k×2k的棋盘可以划分成若干块，每块棋盘是原棋盘的子棋盘或者可以转化成原棋盘的子棋盘。 注意：特殊方格的位置是任意的。而且，L型条块是可以旋转放置的。 为了区分出棋盘上的方格被不同的L型条块所覆盖，每个L型条块可以用不同的数字、颜色等来标记区分。 5. 扩展内容 可以采用可视化界面来表示各L型条块，显示其覆盖棋盘的情况。
(二) 求第k小项 三、程序清单及实验过程和结果分析 （一） #include "stdafx.h" #include "stdio.h" #define M 1024 int table[M][M]; int index; void LFill( int startx , int starty , int width , int x , int y ) { int half=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( x < startx+half ) { if( y < starty+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( y{ 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); } } } } int main() { index=1; int n,i,j,p,q; printf("输入n的大小(n=2^k):"); scanf("%d",&n); for(i=0;ifor(j=0;jtable[i][j]=0; printf("输入特殊位置坐标:"); scanf("%d%d",&p,&q); table[p][q]=-1; LFill(0,0,n,p,q); for(i=0;i{ for(j=0;j{ if(i==p&&j==q) printf(" A"); else printf("%5d",table[i][j]); } printf("\n"); } }
（二） #include "stdafx.h" #include "stdio.h" #define M 100 void sort(int a[],int n) { int i,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; } } int select(int a[],int low,int high,int k) { int pp=low+high-1; if(pp<44) { sort(a,high); return a[k]; } int b[50],c[50]; int i=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; } } int mid=t/2; sort(c,t-1); int aa[50],bb[50],cc[50]; int p=1,q=1,r=1; for(i=1;i<=high;i++) { if(a[i]>c[mid]) cc[r++]=a[i]; else if(a[i]else if(a[i]==c[mid]) bb[q++]=a[i]; } p--;q--;r--; if(p>=k) return select(aa,1,p,k); else if( (p+q) >=k) return c[mid]; else return select(cc,1,r,k-p-q);
} int main() { int n,a[100],i,k;
