计算机算法分析与设计(第四版)习题算法分析部分详解(实验1).doc

实验参考代码VC+6.0测试通过/算法实现题1-2 字典序问题附：实验（设计）报告参考格式设计一多段图问题的动态规划算法与实现班级 学号 姓名 成绩 分一、 设计目的1. 掌握有向网的成本邻接矩阵表示法；2. 掌握多段图问题的动态规划递推算法；3. 进一步掌握动态规划法的基本思想和算法设计方法；二、 设计内容1 任务描述1）多段图问题简介2）设计任务简介设计求解多段图问题的动态规划算法，即设计和实现多段图问题的表示方案、动态规划递推算法，设计对算法或程序的测试方案并完成测试。2 多段图问题的表示方案本设计采用成本邻接矩阵表示多段图，针对多段图(可插入图例)描述成本邻接矩阵的规模与元素意义3 递推过程的抽象描述本设计采用前向或后向递推公式。用自然语言、伪程序设计语言或流程图等形式针对多段图问题的求解（抽象地）描述递推过程4 主要数据类型与变量typedef NodeNumber int; /* 节点编号 */typedef CostType int; /* 成本值类型 */CostType costnn=; /* 成本邻接矩阵, n为顶点数 */NodeNumber pathk; /* k段图最短路径上的节点编号数组 */NodeNumber cur= -1; /* 当前邻接节点 */（必要时，可对数据类型和变量进一步解释或说明，增加可读性）5 算法或程序模块int FindForward(CostType *costn, NodeNumber i, NodeNumber cur)功能: 根据邻接矩阵查找节点i的下一个前向邻接节点, 成功时返回节点编号, 否则返回-1; cur为当前的前向邻接节点, 第一次调用时其值为-1.int FindBackward(CostType *costn, NodeNumber i, NodeNumber cur)功能: 根据邻接矩阵查找节点i的下一个后向邻接节点, 成功时返回节点编号, 否则返回-1; cur为当前的后向邻接节点, 第一次调用时其值为-1.（必要时，可对算法或程序模块进一步解释或说明，增加可读性）三、 测试1 方案描述测试方案、测试模块、测试数据实例（文字数据、图或表等形式）2 结果结合测试数据实例描述测试过程和测试结果，最好给出表示测试过程和结果的抓图，对测试结果进行分析并得出结论。四、 总结与讨论可针对本设计谈体会、谈改进、谈设想等，展示你的概括、归纳和创新思维能力，看重的不是你的对与错，而是鼓励你的想象和创新思维。附：程序模块的源代码