算法分析与设计-递归与分治策略

1、专业课程实验报告课程名称：算法分析与设计开课学期：2014 至 2015 学年第1 学期专业：软件工程年级班级：2012级03班学生姓名：李明洋 学号：222012321062053实验教师：曹严元计算机与信息科学学院软件学院实验项目名称递归与分治策略实验时间2014年10月31日|实验类型验证性设计性综合|性一、实验目的了解并掌握递归的概念，递归算法的基本思想；掌握分治法的基本思想方法；了解适用于用分治法求解的问题类型，并能用递归或非递归的方式设计相应的分治 法算法；掌握分治法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。二、实验要求预习实验指导书及教材的有关内容，掌握分治法

2、的基本思想；严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；认真听讲，服从安排，独立思考并完成实验。三、实验内容与设计(主要内容，操作步骤、算法描述或程序代码)用分治策略实现棋盘覆盖问题。选择合适的数据结构来表示问题；根据分治法的基本原理，写出棋盘覆盖问题的伪码算法；编制C+或JAVA等高级语言程序实现伪码算法；上机运行程序，验证算法的正确性，并分析算法的时空复杂性。用分治策略，可以设计解决棋盘问题的一个简介算法。当k0时，可以将2k *2飞棋盘分割为4个2k-1 * 2k-1子棋盘。由棋盘覆盖问题 得知，特殊方格必位于4个较小的子棋盘中，其余3个子棋盘中无特殊方格。为了将3个无 特

3、殊方格的子棋盘转化为特殊棋盘可以将一个L型骨牌覆盖这3个较小棋盘的会合处，所以， 这3个子棋盘上被L型覆盖的方格就成为给棋盘上的特殊方格，从而将原问题转化为4个较 小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1*1棋盘为止。1、数据说明：tr :棋盘上左上角方格的行号tc :棋盘上左上角方格的列号dr：特殊方格所在的行号dc：特殊方格所在的列号定义了全局变量tile，用于进行覆盖。区分4种不同L类型的骨牌，初始值为0. Board口 数组用来表示棋盘2、函数说明ChessBoard函数实现了递归的将棋盘划分为子棋盘，并将棋盘进行覆盖。main()函数用来进行输入棋盘的大小和特殊棋盘

4、的位置。使用 memset(Board,0,sizeof(Board)将 Board数组清零使用setw()函数控制输出格式C+代码如下：1.#include2.using namespace std;3.int tile=1;/L型骨牌的编号(递增)4.int board100100; 棋盘5./*6.*递归方式实现棋盘覆盖算法7.*输入参数：* tr-当前棋盘左上角的行号* tc-当前棋盘左上角的列号* dr-当前特殊方格所在的行号* dc-当前特殊方格所在的列号* size:当前棋盘的：2W13.13.14. void chessBoard ( int tr, int tc, int d

5、r, int dc, int size )if ( size=1 )棋盘方格大小为1,说明递归到最里层return;int t=tile+;每次递增 1int s=size/2;/棋盘中间的行、列号(相等的)检查特殊方块是否在左上角子棋盘中 TOC o 1-5 h z if ( drtr+s & dctc+s )在chessBoard ( tr, tc, dr, dc, s );else/不在，将该子棋盘右下角的方块视为特殊方块boardtr+s-1tc+s-1=t;chessBoard ( tr, tc, tr+s-1, tc+s-1, s );检查特殊方块是否在右上角子棋盘中if ( dr

6、=tc+s )在chessBoard ( tr, tc+s, dr, dc, s );else/不在，将该子棋盘左下角的方块视为特殊方块boardtr+s-1tc+s=t;chessBoard ( tr, tc+s, tr+s-1, tc+s, s );检查特殊方块是否在左下角子棋盘中if(dr=tr+s&dc=tr+s&dc=tc+s)在chessBoard ( tr+s, tc+s, dr, dc, s );else/不在，将该子棋盘左上角的方块视为特殊方块boardtr+stc+s=t;chessBoard ( tr+s, tc+s, tr+s, tc+s, s );53.void ma

7、in()int size;coutsize;int index_x,index_y;coutindex_xindex_y;chessBoard ( 0,0,index_x,index_y,size );for ( int i=0; isize; i+ )64.65.for ( int j=0; jsize; j+ )66.67.coutboardij/t;coutendl;68.69. 三、测试数据和执行结果（在给定数据下，执行操作、算法和程序的结果，可 使用数据、图表、截图等给出）E:program mi“g琪坦葛盖分治法.exe莆*%H豪臂京蠢擅坐标:2 333448893344889932248779526010107115566110111113131411181919131214141818171915121216201717211515161620202121Processreturned0 e?xection time = 10.726Pressf an0解得此递归方程可得T（k） =0（4飞）。由于覆盖一个2k*2k棋盘所需的L型骨牌个数为（4”k 1）/3,故算法ChessBoard是一个在渐进意义下最优的算法通过这次试验，更多的了解了分治法解题的思路就是将