数塔问题教学文案.ppt

数塔问题教学文案.ppt

ID:61277479

大小:197.50 KB

页数:17页

时间:2021-01-23

数塔问题教学文案.ppt_第1页
数塔问题教学文案.ppt_第2页
数塔问题教学文案.ppt_第3页
数塔问题教学文案.ppt_第4页
数塔问题教学文案.ppt_第5页
资源描述:

《数塔问题教学文案.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动态规划的思想和概念-基本思想动态规划的

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。