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

《算法分析与设计-递归与分治策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、专业课程实验报告课程名称：算法分析与设计开课学期：2014至2015学年第1学期专业：软件工程年级班级：2012级03班学生姓名:李明洋学号:222012321062053实验教师：曹严元计算机与信息科学学院软件学院实验项目名称递归与分治策略实验时间2014年10月31日实验类型□验证性□设计性□综合

2、性一、实验目的1.了解并掌握递归的概念，递归算法的基木思想；2.掌握分治法的基本思想方法；3.了解适用于用分治法求解的问题类型，并能用递归或非递归的方式设计相应的分治法算法；4.掌握分治法复杂性分析方法，比

3、较同一个问题的递归算法与循环迭代算法的效率。二、实验要求1.预习实验指导巧及教材的冇关内容，学握分治法的基木思、想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。2.3.4・5・6.三、实验内容与设计（主要内容，操作步骤、算法描述或程序代码）用分治策略实现棋盘覆盖问题。（1）选择合适的数据结构来表示问题；（2）根据分治法的基木原理，写出棋盘覆盖问题的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确

4、性，并分析算法的时空复杂性。用分治策略，町以设计解决棋盘问题的一个简介算法。当k>0时,可以将2"*2"棋盘分割为4个24-1*21子棋盘。由棋盘覆盖问题得知，特殊方格必位于4个较小的了棋盘中，其余3个了棋盘中无特殊方格。为了将3个无特殊方格的了棋盘转化为特殊棋盘可以将一个L型骨牌覆盖这3个较小棋盘的会合处，所以,这3个了棋盘上被L型覆盖的方格就成为给棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1*1棋盘为止。1、数据说明：tr：棋盘上左上饬方格的行号

5、tc：棋盘上左上饬方格的列号dr：特殊方格所在的行号de：特殊方格所在的列号定义了全局变量t订e,用于进行覆盖。区分4种不同L类型的骨牌，初始值为0.Board[]数组用来表示棋盘2、函数说明ChessBoard函数实现了递归的将棋盘划分为子棋盘，并将棋盘进行覆盖。mainO函数用来进行输入棋盘的人小和特殊棋盘的位置。使用memset（Board,0,sizeof（Board））将Board[]数组清冬使用setw（）函数控制输出格式C++代码如下：#includeusingnames

6、pacestd;inttile=l;//L型骨牌的编号（递增）intboard[100][100];//棋盘*递川方式实现棋盘覆盖算法*输入参数：*****************************************************tr■■当前棋盘左上角的行号tc■■当前棋盘左上角的列号dr■■当前特殊方格所在的行号de—当前特殊方格所在的列号size：当前棋盘的：2U*****************************************************/if(si

7、ze==l)return;intt=tile++;ints=size/2;〃棋盘方格人小为1,说明递归到故里层〃每次递增1〃棋盘中间的行、列号(和等的)〃检查特殊方块是否在左上角子棋盘中if(dr

8、dc>=tc+s)//在chessBoard(tr,tc+s,dr,de,s);else//不在，将该子棋盘左下角的方块视为特殊方块board[tr+s-l][tc+s]=t;chessBoard(tr，tc+s,tr+s-l^tc+s,S);}〃检查特殊方块是否在左下角子棋盘中if(dr>=tr+s&&dc

9、,tc,tr+s，tc+ss);}〃检查特殊方块是否在右下角子棋盘中if(dr>=tr+s&&dc>=tc+s)//在chessBoard(tr+s^tc+s,drde,s);else//不在，将该子棋盘左上角的方块视为特殊方块board[tr+s][tc+s]=t;chessBoard(tr+s,tc+s，tr+s^tc+s，s);voidchessBoard(inttr，inttc，intdr，intde，intsize