P1088解题分析.doc

计算机科学与技术系上机实验报告 课程名称：算法设计与分析 班级：计科081 实验日期：2010-10-15 姓名： 学号： 指导教师： 实验序号：一 实验成绩： 一、实验名称 动态规划算法 二、实验目的及要求 1、学会使用在线测评的算法题目评分系统； 2、通过直观的应用问题，加深对动态规划算法的理解； 三、实验环境 在C.C++编写调试工具，北京大学ICPC在线测评系统POJ 四、实验内容 1、注册POJ账号，找到题号为1088的题目-滑雪； 2、阅读题目，建立其最优解的递归表达式； 3、使用备忘录式的动态规划算法，实现本题； 4、进行简单测试，完成之后提交到POJ系统。 五、算法描述及实验步骤 动态规划算法原理： 分治算法将大的问题变成小的问题来解决，但是如果划分过程中出现重叠子问题，就可能导致大量的重复计算。为了避免这些重复的计算，可以考虑的一个办法就是动态规划算法。 为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含了子问题的最优解。 滑雪问题描述： Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。 int dy[]={0,0,-1,1}; int r,c;//输入的行和列 (2) dis(int i,int j)用来遍历矩阵找出最优路径 int dis(int i,int j){ int temp; if(dis_sk[i][j])//如果已经求出来了，直接返回 return dis_sk[i][j]; for(int k = 0; k 4; k++){ if(in_bound(i+dx[k],j+dy[k])){//如果没有越界 if(h[i][j] h[ i+dx[k] ][ j+dy[k] ]){//如果顺着该侧可以滑 temp = dis(i+dx[k],j+dy[k]);//递归求dis(i+dx[k],j+dy[k])，并保存在临时变量temp中 dis_sk[i][j] = dis_sk[i][j] temp ? dis_sk[i][j] : temp + 1;//如果dis_sk[i][j]比temp小，则取temp+1 } } } return dis_sk[i][j]; } 六、调试过程及实验结果 (1)当输入数据为 2 2 4 3 3 2 时，输出为3. (2)原来的程序B为二维有符号整形数组，致使在移位时出现算术移位（即带符号位移位），使行列信息为负值，经改成无符号整形数组该问题得以解决。 七、总结 通过这次实验，加深了我对动态规划算法的理解，对用备忘录自顶向下 八、附录 #include stdio.h #include iostream using namespace std; int h[101][101];//输入的高度值 int dis_sk[101][101];//记录了每个点可以滑行的最大距离 int dx[]={-1,1,0,0};//为了方便上下左右侧的滑行的最大距离而使用的方便数组 int dy[]={0,0,-1,1}; int r,c;//输入的行和列 bool in_bound(int i,int j){ return i = 0 i r j = 0 j c; } int dis(int i,int j){ int temp; if(dis_sk[i][j])//如果已经求出来了，直接返回 return dis_sk[i][j]; for(int k = 0; k 4; k++){ if(in_bo