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 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更长。事实上，这是最长的一条。(1)int h101101;/输入的高度值 int dis_sk101101;/记录了每个点可以滑行的最大距离 int dx=-1,1,0,0;/为了方便上下左右侧的滑行的最大距离而使用的方便数组 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_skij)/如果已经求出来了，直接返回 return dis_skij; for(int k = 0; k h i+dxk j+dyk )/如果顺着该侧可以滑 temp = dis(i+dxk,j+dyk);/递归求dis(i+dxk,j+dyk)，并保存在临时变量temp中 dis_skij = dis_skij temp ? dis_skij : temp + 1;/如果dis_skij比temp小，则取temp+1 return dis_skij; 六、调试过程及实验结果(1)当输入数据为2 24 33 2时，输出为3. (2)原来的程序B为二维有符号整形数组，致使在移位时出现算术移位（即带符号位移位），使行列信息为负值，经改成无符号整形数组该问题得以解决。七、总结 通过这次实验，加深了我对动态规划算法的理解，对用备忘录自顶向下倒推有了更深刻的认识八、附录#include #include using namespace std;int h101101;/输入的高度值 int dis_sk101101;/记录了每个点可以滑行的最大距离 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 = 0 & j c; int dis(int i,int j) int temp; if(dis_skij)/如果已经求出来了，直接返回 return dis_skij; for(int k = 0; k h i+dxk j+dyk )/如果顺着该侧可以滑 temp = dis(i+dxk,j+dyk);/递归求dis(i+dxk,j+dyk)，并保存在临时变量temp中 dis_skij = dis_skij temp ? dis_skij : temp + 1;/如果dis_skij比temp小，则取temp+1 return dis_skij; int main() int max_dis = 0; int temp; int i,j; cin r c; for(i = 0; i r; i+) for(j = 0; j hij; dis_skij = 0; for(i = 0; i r; i+) f