分治算法设计与应用.doc

实验三 分治算法设计与应用 一．实验目的和要求 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型条块，显示其覆盖棋盘的情况。 程序： #include stdio.h #define M 8 int table[M][M]; int index; void LFill(int startx, int starty, int width,int x,int y) { 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+width/2) { if(ystarty+width/2) //左上 { table[startx+width/2-1][starty+width/2]=index; //左下 table[startx+width/2][starty+width/2-1]=index;//右上 table[startx+width/2][starty+width/2]=index;//右下 index++; LFill(startx,starty,width/2,x,y);//左上 LFill(startx,starty+width/