资源描述：
《数塔问题教学文案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数塔问题2枚举最保险的思路，列举出所有可能的路径再比较，得出和最大的路径。9121510682189519710416重复工作：循环、递归。如何循环？递归如何？使问题向边界条件转化的规则(递归定义)。递归边界条件；2枚举-递归算法1inta[100][100];//下三角形存放数据intmax(inti,intj,intn)//递归函数{intleft,right;if((i==n)
2、
3、(j==n))//到达边缘returna[i][j];left=max(i+1,j,n);//左边right=max(i+1,j+1,n);//右边return
4、(left>right)?(left+a[i][j]):(right+a[i][j]);}max(1,1,n)max(2,1,n)max(2,2,n)max(3,1,n)max(3,2,n)………………9121510682189519710416重叠子问题：计算了两次18的最大路径。3动态规划的手工计算912 1510 6 82 18 9 519 7 10 4 16阶段5阶段4阶段3阶段2(21)(28)(19)(21)(38)(34)(29)(50)(49)(59)决策决策决策决策阶段159504938
5、34292128192119710416取第i行第j个数，一般有两种方案。3动态规划的手工计算912 1510 6 82 18 9 519 7 10 4 16(33)(49)(41)(37)(31)(30)(32)(21)(24)(52)(56)(59)(45)(53)决策决策决策决策阶段1阶段2阶段3阶段4阶段53动态规划的手工计算顺序与逆序解法本质上无区别；一般当初始状态唯一给定时可用逆序解法；如需比较到达不同终点状态的各个路径及最大结果时，使用顺序法比较简便；如需知道塔中每一点到最下层的最大值和路径
6、时，使用逆序法比较简便。4动态规划的算法实现原始信息存储层数用整型变量n存储；数塔中的数据用二维数组data[][]存储，下三角阵。动态规划过程存储必须用二维数组d[][]存储各阶段的决策结果。二维数组d的存储内容如下：d[n][j]=data[n][j]，其中j=1,2,……,n；d[i][j]=max(d[i+1][j]，d[i+1][j+1])+data[i][j]，其中i=n-1,n-2,……1，j=1,2,……,i；逆序法5950493834292128192119710416最后d[1][1]存储的就是问题的最大值。可以通过分析d，
7、得到路径。4动态规划的算法实现输出data[1][1]“9”；b=d[1][1]-data[1][1]=59-9=50b与d[2][1],d[2][2]比较b与d[2][1]相等，输出data[2][1]“12”；b=d[2][1]-data[2][1]=50-12=38b与d[3][1],d[3][2]比较b与d[3][1]相等，输出data[3][1]“10”；b=a[3][1]-data[3][1]=38-10=28b与d[4][1],d[4][2]比较b与d[4][2]相等，输出data[4][2]“18”；b=d[4][2]-data
8、[4][2]=28-18=10b与d[5][2],d[5][3]比较b与d[5][3]相等，输出data[5][3]“10”。数组d5950493834292128192119710416数组data91215106821895197104164动态规划的算法实现为了设计简洁的算法，可以用三维数组a[50][50][3]存储以上确定的三个数组的信息。a[50][50][1]代替数组data，a[50][50][2]代替数组d,a[50][50][3]记录解路径。for(i=1;i<=n;i++)for(j=1;j<=i;j++){input(a
9、[i][j][1]); a[i][j][2]=a[i][j][1]; a[i][j][3]=0;}for(i=n-1;i>=1;i--)for(j=1;j>=i;j++)if(a[i+1][j][2]>a[i+1][j+1][2]){a[i][j][2]=a[i][j][2]+a[i+1][j][2]; a[i][j][3]=0;}else{a[i][j][2]=a[i][j][2]+a[i+1][j+1][2]; a[i][j][3]=1;} print('max=’,a[1][1][2]);for(i=1;i<=n-1;i++){print
10、(a[i][j][1],‘->’); j=j+a[i][j][3];} print(a[n][j][1]);5动态规划的思想和概念-基本思想动态规划的
