有哪些信誉好的足球投注网站- 1、本文档共25页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
第3章_动态规划_作业
课后练习 练习1：已知一组连乘矩阵A1A2A3A4A5的行列数如下面p向量所示： 如使用函数直接递归调用（穷举法）的形式求解，则是无效算法，请画出函数递归调用的递归树树形，并说明有哪些子问题被重复计算。 请用动态规划法求解最优计算顺序，写出计算过程以及加括号的计算顺序表达式。p = (5, 3, 9, 2, 2, 4) A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4) 函数递归调用的递归树树形 1:5 1:1 2:5 1:2 3:5 1:3 4:5 1:4 5:5 2:2 3:5 2:4 5:5 1:1 2:2 3:3 4:5 3:4 5:5 …… …… …… …… …… …… …… …… 用动态规划法求解最优计算顺序，写出计算过程以及加括号的计算顺序表达式。 A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4) 5×5 M矩阵 5×5 S矩阵 0 0 0 0 0 1 2 3 4 5 1. 计算m[i,i+1] (i=1, 2, 3, 4)： （矩阵链长度为2） m[1][2] = min 1≤k＜2 {m[1][1]+m[2][2]+p0p1p2} = 135 m[2][3] = min 2≤k＜3 {m[2][2]+m[3][3]+p1p2p3} = 54 m[3][4] = min 3≤k＜4 {m[3][3]+m[4][4]+p2p3p4} = 36 m[4][5] = min 4≤k＜5 {m[4][4]+m[5][5]+p3p4p5} = 16 135 54 36 16 1 2 3 4 A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4) 5×5 M矩阵 5×5 S矩阵 0 0 0 0 0 1 2 3 4 5 135 54 36 16 1 2 3 4 2. 计算m[i,i+2] (i=1, 2, 3)： （矩阵链长度为3） m[1][3] = min 1≤k＜3 {m[1][1]+m[2][3]+p0p1p3, m[1][2]+m[3][3]+p0p2p3} = min{84, 225} = 84 m[2][4] = min 2≤k＜4 {m[2][2]+m[3][4]+p1p2p4, m[2][3]+m[4][4]+p1p3p4} = min{90, 66} = 66 m[3][5] = min 3≤k＜5 {m[3][3]+m[4][5]+p2p3p5, m[3][4]+m[5][5]+p2p4p5} = min{88, 90} = 88 84 66 88 1 3 3 A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4) 5×5 M矩阵 5×5 S矩阵 0 0 0 0 0 0 0 0 0 0 135 54 36 16 1 2 3 4 84 66 88 1 3 3 3. 计算m[i,i+3] (i=1, 2)： （矩阵链长度为3） m[1][4] = min 1≤k＜4 { m[1][1] + m[2][4] + p0p1p4, m[1][2] + m[3][4] + p0p2p4, m[1][3] + m[4][4] + p0p3p4} = { 96, 261, 104 } = 96 96 1 A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4) 5×5 M矩阵 5×5 S矩阵 0 0 0 0 0 0 0 0 0 0 135 54 36 16 1 2 3 4 84 66 88 1 3 3 3. 计算m[i,i+3] (i=1, 2)： （矩阵链长度为3） m[2][5] = min 2≤k＜5 { m[2][2] + m[3][5] + p1p2p5, m[2][3] + m[4][5] + p1p3p5, m[2][4] + m[5][5] + p1p4p5} = { 196, 94, 90 } = 90 96 1 90 4 A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4) 5×5 M矩阵 5×5 S矩阵 0 0 0 0 0 0 0 0 0 0 135 54
文档评论（0）