动态规划最长公共子序列问题

《动态规划最长公共子序列问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实训三最长公共子序列算法与实现任务分配编码陈健翔成绩综合分数测试朱敏成绩一、设计目的1）掌握；2）掌握；3）进一步掌握动态规划法的基本思想和算法设计方法；二、设计内容1．任务描述1）多段图问题简介……2）设计任务简介设计求解多段图问题的动态规划算法，即设计和实现多段图问题的表示方案、动态规划递推算法，设计对算法或程序的测试方案并完成测试。2．多段图问题的表示方案本设计采用成本邻接矩阵表示多段图，针对多段图(可插入图例)描述成本邻接矩阵的规模与元素意义……3．递推过程的抽象描述本设计采用前向或后向递推公式。用自然语言、伪程序设计语言或流程图等形式针对多段图问题的求解（抽象

2、地）描述递推过程……4．主要数据类型与变量typedefNodeNumberint;/*节点编号*/typedefCostTypeint;/*成本值类型*/CostTypecost[n][n]={…};/*成本邻接矩阵,n为顶点数*/NodeNumberpath[k];/*k段图最短路径上的节点编号数组*/NodeNumbercur=-1;/*当前邻接节点*/（必要时，可对数据类型和变量进一步解释或说明，增加可读性）5．算法或程序模块intFindForward(CostType*cost[n],NodeNumberi,NodeNumbercur)功能:根据邻接矩阵查找

3、节点i的下一个前向邻接节点,成功时返回节点编号,否则返回-1;cur为当前的前向邻接节点,第一次调用时其值为-1.intFindBackward(CostType*cost[n],NodeNumberi,NodeNumbercur)功能:根据邻接矩阵查找节点i的下一个后向邻接节点,成功时返回节点编号,否则返回-1;cur为当前的后向邻接节点,第一次调用时其值为-1.（必要时，可对算法或程序模块进一步解释或说明，增加可读性）三、测试1．方案描述测试方案、测试模块、测试数据实例（文字数据、图或表等形式）……举例：1．结果一、总结与讨论可针对本设计谈体会、谈改进、谈设想等，展

4、示你的概括、归纳和创新思维能力，看重的不是你的对与错，而是鼓励你的创新思维。附：程序模块的源代码几点说明(本行及以下内容不在报告中出现，请注意删除)1）建议将算法功能模块与测试模块分离、存盘，以备今后调用；2）除基本版式外，各大项的小项仅供参考，你可根据设计的具体内容灵活展现你的报告能力；3）撰写报告时，注意序号（设计一，二，……）；4）按规定时间准时提交，逾期不受理，补交报告，成绩打折扣；5）严禁抄袭，雷同者一律作废。