贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：软件101 实验日期：2012-10-23 姓名：学号：指导教师：实验序号：一实验成绩：一、实验名称分治算法实验- 棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写；2、理解分治算法的特点；3、掌握分治算法的基本结构。
三、实验环境Visual C++四、实验内容根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验；要求完成棋盘覆盖问题的输入、分治求解、输出。
有余力的同学尝试消去递归求解。
五、算法描述及实验步骤分治算法原理：分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。
棋盘覆盖问题描述：在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。
实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
通过对本实验的学习，对分治算法有了进一步的认识，对棋盘覆盖问题和其他分治问题进行了对比。
八、附录源程序（核心代码）清单或使用说明书，可另附纸①#include<iostream>#include<cmath>using namespace std;int board[100][100],tile=1;void chessboard(int tr,int tc,int dr,int dc,int size)//tr 棋盘左上角方格的行号，tc棋盘左上角方格的列号。
dr特殊方格所在的行号。
dc特殊方格所在的列号。
size棋盘的大小2^k.{int s;if(size==1)return ;int t=tile++;s=size/2;//覆盖左上角棋盘if(dr<tr+s&&dc<tc+s)chessboard(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<tr+s&&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);} ②//覆盖左下角子棋盘if(dr>=tr+s&&dc<tc+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,tc+s,s); }}int main(){int k,tr,tc,size,i,j;cin>>k>>tr>>tc;size=pow(2,k);chessboard(0,0,tr,tc,size);for(i=0;i<size;i++){for(j=0;j<size;j++)cout<<board[i][j]<<" ";cout<<endl;}return 0;}贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：软件101 实验日期：2012-11-6姓名：学号：指导教师：实验序号：二实验成绩：一、实验名称动态规划实验- 滑雪问题二、实验目的及要求1、学会使用在线测评的算法题目评分系统；2、通过直观的应用问题，加深对动态规划算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、找到题号为1088的题目-滑雪,阅读题目，建立其最优解的递归表达式；3、使用备忘录式的动态规划算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。
五、算法描述及实验步骤动态规划算法原理：分治算法将大的问题变成小的问题来解决，但是如果划分过程中出现重叠子问题，就可能导致大量的重复计算。
为了避免这些重复的计算，可以考虑的一个办法就是动态规划算法。
为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含了子问题的最优解。
滑雪问题描述：Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。
可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。
Michael想知道载一个区域中最长底滑坡。
区域由一个二维数组给出。
数组的每个数字代表点的高度。
下面是一个例子1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。
在上面的例子中，一条可滑行的滑坡为24-17-16-1。
当然25-24-23-...-3-2-1更长。
事实上，这是最长的一条。
Input输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。
下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output输出最长区域的长度。
实验步骤：1、建立滑雪问题的解的递归表达式递归表达式如下：if(dp[i][j] < DP(i+a[k][0],j+a[k][1]) + 1)dp[i][j] = DP(i+a[k][0],j+a[k][1]) + 1;2、构造算法框架①首先定义一个状态转移函数，用来遍历搜索所需的最长路径int DP(int i,int j){...}②在主函数中调用DP（i,j）函数，将所求最长路径的存放在变量ans中int main(){...}3、分析出算法复杂度因为DP（int i,int j）函数每调用一次，都要对i,j周围的四个数进行比较，这样的工作要重复进行，故需要O（n2）的时间。
六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
输入5行5列数，结果如下：七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
通过本实验的学习，我对递归算法有了进一步的了解，在验证试验结果时，首先输入5行5列的数组大小和数据，主函数调用DP（int i,int j）函数，求出最长的路径；该算法的在时间复杂度上得进一步改进，如果对于大一点的数据，遍历效率就不高了。
八、附录源程序（核心代码）清单或使用说明书，可另附纸#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int M = 110;int a[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};int dp[M][M];int map[M][M];int ans,tmp;int R,C;int DP(int i,int j){if(dp[i][j] > 0)return dp[i][j];for(int k = 0; k < 4; k++){if( (i+a[k][0] >= 1) && (i+a[k][0] <= R) && (j+a[k][1] <= C) &&(j+a[k][1] >=1) && map[ i+a[k][0] ][j+a[k][1] ] < map[i][j] ){if(dp[i][j] < DP(i+a[k][0],j+a[k][1]) + 1)dp[i][j] = DP(i+a[k][0],j+a[k][1]) + 1;}}return dp[i][j];}int main(){int i;memset(dp,0,sizeof(dp));cin >> R >>C;for(i = 1; i <= R; i++)for(int j = 1; j <= C; j++)scanf("%d",&map[i][j]);for(i = 1; i <= R; i++)for(int j = 1; j <= C; j++){int aa = DP(i,j);if(ans < aa)ans = aa;}cout << ans + 1<<endl;return 0;贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：软件101 实验日期：2012-10-20姓名：学号：1008060028 指导教师：实验序号：三实验成绩：一、实验名称贪心算法实验- 包装问题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对贪心算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1017的题目-包装；2、阅读题目，分析出求解该问题的思路；3、使用贪心算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。
五、算法描述及实验步骤贪心算法原理：贪心算法通过一系列的选择来达到子问题的解。
它所做的每一步选择都是当前状态下局部最好选择，即贪心选择。
这种启发式的策略虽不能总是奏效，但大多数情况下确能达到预期目的，得到最优解。
要使用贪心算法，问题必须具备两个基本要素。
贪心选择性质和最优子结构性质。
贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
通常采用自顶向下的方式进行，这样每做一次贪心选择就将所求问题化为规模更小的子问题。
当然，前提是所求问题本身的最优解包含其子问题的最优解，即具有最优子结构性质。