《算法设计与分析》实验二09770106刘东辉

《《算法设计与分析》实验二09770106刘东辉》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学号09770106《算法设计与分析》实验报告二学生姓名刘东辉专业、班级软件一班指导教师唐国峰成绩电子与信息工程系2011年11月17日实验二：典型算法的理解与应用一、实验目的本次实验是针对书上各章节所阐述的算法的相关应用练习，旨在加深学生对该部分知识的理解，提高学生运用该算法解决问题的能力。二、实验步骤与要求1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2．学生独自完成实验指定内容；3．实验结束后，用统一的实验报告模板编写实验报告。4．提交说明：（1）电子版提交说明：a需要提交Winrar压缩包，文件名为“《算法设计与分析》实验二_学号

2、_姓名”，如“《算法设计与分析》实验二_07770101_张三”。b压缩包内为一个“《算法设计与分析》实验二_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。（2）打印版提交说明：a不可随意更改模板样式。b字体：中文为宋体，大小为10号字，英文为TimeNewRoman，大小为10号字。c行间距：单倍行距。（3）提交截止时间：2011年11月17日16:00。三、实验项目【分治策略】1．采用分治策略算法实现棋盘覆盖问题的求解；2．运用冒泡排序算法、合并排序算法

3、、快速排序算法实现对给定数字序列的排序。【动态规划】1．运用动态规划算法求解矩阵连乘问题；2．运用动态规划算法求解最长公共子序列问题；3．运用动态规划算法求解最大子段和问题；4．运用动态规划算法求解0-1背包问题。【贪心算法】1．运用贪心算法求解找零钱问题。【回溯算法】1．运用回溯算法求解0-1背包问题；2．运用回溯算法求解4城市旅行商问题；3．运用回溯算法求解N后问题。【分支限界算法】1．运用分支限界算法求解0-1背包问题；2．运用分支限界算法求解4城市旅行商问题。【其他搜索算法】1．运用深度优先搜索算法求解马走棋盘问题；2．运用A*算法求解九宫问题

4、。三、实验过程【分治策略】　1题目分析和算法构造在此论证算法设计中的一些必要的设计依据。将棋盘平分四部分，一直分，知道含有特殊方格，看特殊方格在那一部分中，在延边用L型骨牌覆盖。2算法实现程序源代码（请写入必要的注释）。棋盘#include#includeusingnamespacestd;/******************************************************参数含义：*tr--当前棋盘左上角的行号*tc--当前棋盘左上角的列号*dr--当前特殊方格所在的行号*dc--当前特殊方

5、格所在的列号*****************************************************/intBoard[100][100];//用来存放棋盘元素的数组inttile=1;//L型骨牌的投放序号voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1){//棋盘方格大小为,说明递归到最里层return;}intt=tile++;//每次递增ints=size/2;//分割棋盘if(dr

6、Board(tr,tc,dr,dc,s);}else{//不在，将该子棋盘右下角的方块视为特殊方块Board[tr+s-1][tc+s-1]=t;ChessBoard(tr,tc,tr+s-1,tc+s-1,s);}if(dr=tc+s){//检查特殊方块是否在右上角子棋盘中ChessBoard(tr,tc+s,dr,dc,s);}else{//不在，将该子棋盘左下角的方块视为特殊方块Board[tr+s-1][tc+s]=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}if(dr>=tr+s&&dc

7、+s){//检查特殊方块是否在左下角子棋盘中ChessBoard(tr+s,tc,dr,dc,s);}else{//不在，将该子棋盘右上角的方块视为特殊方块Board[tr+s][tc+s-1]=t;ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}if(dr>=tr+s&&dc>=tc+s){//检查特殊方块是否在右下角子棋盘中ChessBoard(tr+s,tc+s,dr,dc,s);}else{//不在，将该子棋盘左上角的方块视为特殊方块Board[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s

8、,tc+s,s);}}voidmain(){intn;intsize;//棋盘大小cout<<