算法设计实验报告15230

《算法设计实验报告15230》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：软件102实验日期：YYYY-MM-DD姓名：学号：1008060206指导教师：程欣宇实验序号：一实验成绩：一、实验名称分治算法实验-棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写；2、理解分治算法的特点；3、掌握分治算法的基本结构。三、实验环境VisualC++四、实验内容根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验；要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学尝试消去递归求解。五、算法描述及实验步骤分治算法原理：分治算法将

2、大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。棋盘覆盖问题描述：在一个2kx2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？六、调试过程及实验结果调试过程中，系统提示ChessBoard函数中Board为未声明标识符，仔细

3、检查后发现将Board数组声明在了main函数中，将Board函数声明为全局数组后调试通过。实验结果：七、总结通过本次实验，初步了解了分治算法的思想，将一个规模较大的问题细分为较小的子问题，然后逐个解决。八、附录#includeinttile=0;intBoard[4][4]={0};voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//棋盘分割//覆盖左上角子棋盘if(dr

4、&dc=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);}//覆盖

5、棋盘左下角if(dr>=tr+s&&dc=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,tc+s,s);}}voidmain(){inti

6、,j;for(i=0;i<4;i++){for(j=0;j<4;j++){printf("%d",Board[i][j]);}printf("");}ChessBoard(0,0,0,1,4);printf("覆盖后棋盘:");for(i=0;i<4;i++){for(j=0;j<4;j++){printf("%d",Board[i][j]);}printf("");}}贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日期：YYYY-MM-DD姓名：学号：指导教师：程欣宇实验序号：二实

7、验成绩：一、实验名称动态规划实验-滑雪问题二、实验目的及要求1、学会使用在线测评的算法题目评分系统；2、通过直观的应用问题，加深对动态规划算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、找到题号为1088的题目-滑雪,阅读题目，建立其最优解的递归表达式；3、使用备忘录式的动态规划算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤动态规划算法原理：分治算法将大的问题变成小的问题来解决，但是如果划分过程中出现重叠子问题，就可能导致大量的重复计算。为了避免这些重

8、复的计算，可以考虑的一个办法就是动态规划算法。为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含了子问题的最优解。滑雪问题描述：Michael喜欢滑雪百这并不奇怪