实验目的1.掌握动态规划的基本思想。2.掌握动态规划算法的设计步骤。3.能使用备忘录方法优化动态规划的递归实现。实验要求要求结伴编程两名同学坐在同一工作台前进行程序编写。与两名同学各自独立工作相比结伴编程能编写出质量更高的代码同时可以促进每名程序员自身功力的提高。实验任务1小白兔拔萝卜问题进阶——备忘录方法小白兔从一片田地的左上角进入右下角离开田地中每个方格里有数量不等的萝卜供小白兔拿取小白兔必须尽快离开田地以降低被猎人发现的概率(即小白兔每次必须选择向下或者向右走一格并拿走格子里的萝卜)在保证尽可能安全的前提下请为小白兔规划一条最佳的拿萝卜路径递推方程如下任务1利用备忘录方法(需要借助C[][]数组)在递归过程中记录并检查各个子问题的解使递归方法达到和递推方法类似的求解效率。#includeiostream #includeiomanip #includecstdlib #includecstdio #includectime using namespace std; const int M8;//萝卜地行数 const int N10;//萝卜地列数 int v[M][N],c[M][N];//萝卜数最优萝卜数 int memo_crt(int m,int n) {//用备忘录方法实现小白兔拔萝卜 // 已经计算过这个子问题直接返回保存的值 if(c[m][n] ! 0) return c[m][n]; // 起点 if(m 0 n 0) { c[m][n] v[m][n]; return c[m][n]; } // 第一行只能从左边来 if(m 0) { c[m][n] v[m][n] memo_crt(m, n-1); return c[m][n]; } // 第一列只能从上面来 if(n 0) { c[m][n] v[m][n] memo_crt(m-1, n); return c[m][n]; } // 其他位置取上方、左方较大值 c[m][n] v[m][n] max(memo_crt(m-1, n), memo_crt(m, n-1)); return c[m][n]; } void pathfind(int m,int n) { //反向寻找最优萝卜矩阵中最优解的来源 cout \n最优路径反向; while(true) { cout ( m , n ) ; if(m 0 n 0) break; if(m 0) { // 在第一行只能来自左边 n--; } else if(n 0) { // 在第一列只能来自上方 m--; } else { if(c[m-1][n] c[m][n-1]) m--; else n--; } } cout )\n说明坐标(i,j)只能向右向下走\n; } int main() { int i,j,start,end,t,count; cout萝卜地如下endl; for(i0;iM;i) { for(j0;jN;j) { v[i][j]rand()%10; c[i][j]0; coutsetw(5)v[i][j]; } coutendl; } startclock(); count memo_crt(M-1,N-1); endclock(); tend-start; cout记住小萝卜结果为count耗费时间:tmsendl; cout备忘录记录的最大萝卜累加矩阵如下endl; for(i0;iM;i) { for(j0;jN;j) { coutsetw(5)c[i][j]; } coutendl; } pathfind(M-1,N-1); return 0; }2爬楼梯问题的备忘录求解任务2爬楼梯问题和斐波那契数列的计算极其相似请编写程序利用备忘录的方法使递归程序达到和递推程序类似的求解效率。#includeiostream #include ctime using namespace std; const int N30;//台阶数 int c[N1];//保存子问题的最优解 int jumpstr_rec(int n) { //朴素递归求解 if(n 1) return 1; if(n 2) return 2; return jumpstr_rec(n-1) jumpstr_rec(n-2); } int jumpstr_memo(int n) { //备忘录求解 if(c[n] ! 0) //已经算过直接返回 return c[n]; if(n 1) { c[n] 1; return c[n]; } if(n 2) { c[n] 2; return c[n]; } c[n] jumpstr_memo(n-1) jumpstr_memo(n-2); return c[n]; } int main() { int i,start,end,t,count; for(i0;iN;i) c[i]0; startclock(); for(i0;i10;i) countjumpstr_rec(N); endclock(); tend-start; cout递归结果为count耗费时间:tmsendl; startclock(); for(i0;i10;i) countjumpstr_memo(N); endclock(); tend-start; cout备忘结果为count耗费时间:tmsendl; return 0; }任务3如果爬楼梯问题允许一次最多上3个台阶应该如何编写带有备忘录的递归程序求解请参照任务2代码进行编程实现#includeiostream #include ctime using namespace std; const int N30;//台阶数 int c[N1];//保存子问题的最优解 int jumpstr_rec(int n) { //朴素递归求解 if(n 0) return 1; if(n 1) return 1; if(n 2) return 2; return jumpstr_rec(n-1)jumpstr_rec(n-2)jumpstr_rec(n-3); } int jumpstr_memo(int n) { //备忘录求解 if(c[n] ! 0) return c[n]; if(n 0) { c[n] 1; return c[n]; } if(n 1) { c[n] 1; return c[n]; } if(n 2) { c[n] 2; return c[n]; } c[n] jumpstr_memo(n-1)jumpstr_memo(n-2)jumpstr_memo(n-3); return c[n]; } int main() { int i,start,end,t,count; for(i0;iN;i) c[i]0; startclock(); for(i0;i10;i) countjumpstr_rec(N); endclock(); tend-start; cout递归结果为count耗费时间:tmsendl; startclock(); for(i0;i10;i) countjumpstr_memo(N); endclock(); tend-start; cout备忘结果为count耗费时间:tmsendl; return 0; }实验总结1动态规划分析和求解问题的步骤1.划分问题阶段2.定义状态3.写出状态转移方程4.设置边界初始条件5.选择计算次序6.回溯构造最优解7.输出答案。2使用递归求解动态规划方程时如何避免重复计算使用备忘录。设置数组存储已经求解完成的子问题结果递归前查询备忘录已求解则直接返回未求解则递归计算计算完成后存入备忘录保证每个子问题只计算一次。编程提示在c语言中若使用rand函数生成随机数需要#includecstdlib随机生成种子srand((unsigned)time(NULL));//保证每次独立运行生成的随机序列不同int arand()%100;//生成0-99之间的一个随机数并复制给a若使用clock()记录当前系统时间需要#includectime