实验报告
课程 算法设计与分析实验 实验名称 分治算法设计与应用 第 1 页
一、实验目的
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型条块，显示其覆盖棋盘的情况。 (二) 求数列中的第1～k小元素
1.问题描述
设计算法实现在一个具有在n各互不相同元素的数组A[1?n]中找出所有前k个最小元素的问题，这里k不是常量，即它是输入数据的一部分。要求算法的时间复杂性为Θ(n)。
2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1764题
输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由三行组成，其中其中，第一行输入一个正整数n，表示元素的个数；第二行输入n个整数，整数之间用一个空格隔开。第三行输入一个正整数k，表示求该组测试例中的前k个最小元素。（设给出的每个整数序列中的元素是唯一的。）
输出：对于每个测试例输出一行，由k个整数组成，表示输入的n个整数中前k个最小元素。整数之间用一个空格隔开。两个测试例的输出数据之间用一个空行隔开，最后一个测试例后无空行。
若在ACM平台上提交程序，输出的两个新整数集合要求按照从小到大排序后输出。该排序步骤对算法时间复杂性的影响在此不计。
3. 测试数据 输入：2
19
56 34 22 7 16 95 46 37 81 12 73 26 19 31 68 42 3 72 51 8 26
8 33 28 17 51 57 49 35 11 25 37 14 3 2 13 52 12 6 2 32 54 5 16 22 23 7 13
输出：3 7 12 16 19 22 26 31
2 3 5 6 7 8 11 12 13 14 16 17 22 4. 设计与实现的提示
注意题目中算法时间复杂性的限制。如果采用排序算法解决此问题并返回A[1?k],则耗费时间为O(nlogn),超出要求；如果运行算法SELECT k次，耗费Θ(kn)= O(n2),因为k不是常量，因此不能简单地运行算法SELECT k次。
若在ACM平台上提交程序，输出的两个新整数集合要求按照从小到大排序后输出。该排序步骤对算法时间复杂性的影响在此不计。
三、实验环境
硬件：Windows XP计算机、鼠标、键盘、显示器 开发环境：Microsoft Visual C++ 6.0
四、实验步骤
（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）
①、 点击开始菜单中的程序-Microsoft Visual C++ 6.0
点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入“实验三.(1).cpp”,再点击确定.
②、 编写程序如下：
#include
int A[MAX][MAX];
void qipan(int h,int l,int row,int lin,int m) {
if(m==1) return; int p=line++, f=m/2;
if(row qipan(h,l,row,lin,f);//特殊方格在此盘中 else { A[h+f-1][l+f-1]=p; //此盘中无特殊方格 qipan(h,l,row+f-1,lin+f-1,f); //覆盖其余方格 } if(row qipan(h,l+f,row,lin,f); else { A[h+f-1][l+f]=p; qipan(h,l+f,row+f-1,lin+f,f); } if(row>=h+f&&lin qipan(h+f,l,row,lin,f); else { A[h+f][l+f-1]=p; qipan(h+f,l,row+f,lin+f-1,f); } if(row>=h+f&&lin>=l+f)//以N为8举例，f=4，那么此时相当于在第四象限，递归 qipan(h+f,l+f,row,lin,f); else { A[h+f][l+f]=p; qipan(h+f,l+f,row+f,lin+f,f); } } void main() { int i,j,n,hen,zong; printf(\输入棋盘大小格局：\\n\ scanf(\ printf(\输入特殊格的横纵坐标：\\n\ scanf(\ scanf(\ if(hen<0||hen>n||zong<0||zong>n) { printf(\输入不正确！请重新输入！\\n\ return; } qipan(0,0,hen,zong,n); for(i=0;i for(j=0;j if((i==hen)&&(j==zong)) printf(\ else printf(\ } printf(\ } } ③、 点击开始菜单中的程序-Microsoft Visual C++ 6.0 点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入“实验三.(2).cpp”,再点击确定. ④、 编写程序如下： #include int number; int elem[MAX]; int k; int output[MAX]; }Data[MAX]; /*-----------------输出前K小元素-------------*/ void find(int A[],int n,int k) { int i,j; int s=0; int B[MAX]; for(i=1;i for(j=0;j if(A[j]==A[i]) break; if(j==i-1) B[s++]=A[i]; } } for(i=0;i printf(\} /*--------------------排序--------------------*/ void sort(int n,int* a) { int i,temp,j; for(i=0;i for(j=i+1;j temp=a[i]; a[i]=a[j]; a[j]=temp; } } } } /*----------------求第K小元素--------------------*/ int select(int k,int* S,int num) { int num1,num2,i,j,m,n1,n2,n3; int temp[5],M[MAX],S1[MAX],S2[MAX],S3[MAX]; if(num<44) { sort(num,S); return S[k-1]; }