哈工大软件工程ab 1：结对编程.doc

哈尔滨工业大学计算机科学与技术学院 2014年秋季学期《软件工程》 Lab 1：结对编程 目 录 1 1 2 待求解问题描述与数学模型 1 3 算法设计思路 1 3.1 设计思路 1 3.2 算法流程图 1 3.3 核心数据结构 1 4 实验结果 1 4.1 流程1 2 4.2 流程2 2 4.3 流程3 2 4.4 流程4 2 5 编程语言与环境 2 6 结对编程 2 6.1 角色切换与任务分工 2 6.2 工作照片 2 6.3 工作日志 2 6.4 对结对编程的体会 2 7 计划与实际进度 3 8 小结 3 [文档全部完成之后，请更新上述区域]  练习结对编程(pair programming)，体验敏捷开发中的两人合作； 两人一组，自由组合； 使用一台计算机，共同编码，完成实验要求； 在工作期间，两人的角色至少切换4次；使用JAVA+Eclipse编程。 待求解问题描述1：一个服务流程，由一组活动及其之间的关系构成，使用DAG 输入2：针对每个服务活动的候选服务集，各服务有功能和QoS信息； 输入3：客户针对服务流程的QoS需求； 输出：满足QoS需求的服务选择方案(使用DAG表示) ； 计算方式：Q = TR – TP/100，其中TR为最终方案的总体可靠性，TP为最终方案的总价格，Q值越大越好。 算法设计 主要思想为深度优先有哪些信誉好的足球投注网站，用到的数据是根据数据表第四个值（即价格）有小到大排好序的数据，以排好序的各个字母最小的价格值对应的Q值作为初始判断条件值。寻找一条完整路径可以划分为两个部分，一部分是还没有有哪些信誉好的足球投注网站到最后一个字母，另一个是到了最后一个字母有哪些信誉好的足球投注网站。 第一部分有哪些信誉好的足球投注网站存在三种情况，一是有哪些信誉好的足球投注网站字母对应的500个数据时还没有到达第500个数据，这样在不满足条件的情况下，可以继续向下一个数据有哪些信誉好的足球投注网站；另一个是如果已经到达最后一个数据即第500个数据，仍然没有满足条件，此时需要去路径上一级字母标记（记录字母的下标）的下个数据开始寻找；三是在满足条件的情况下，此时只需保存记录，同时向路径的下一级字母展开有哪些信誉好的足球投注网站即可。 第二部分有哪些信誉好的足球投注网站是到达最后一个字母，需遍历所有的数据。如果满足条件不仅需要保存记录，还需要更新Q值作为新的判断条件；如果不满足条件，返回上一级字母标记的下一个数据开始继续有哪些信誉好的足球投注网站。 有哪些信誉好的足球投注网站完成后，根据记录可以得到各个字母对应的下标，即得到最优路径。 算法流程图 递归 此流程为寻找一个服务流程的最优解。多个流程时，只需循环多次即可 核心数据结构 一维数组g[],h[]，二维数组p[][],r[][],c[][],index[][] 时间复杂度分析 假设一个服务流程有n个节点，每个节点对应有m个不同的候选服务。 首先程序开始有将数据排序，用到的是选择排序,时间复杂度为:o(m*m*n) 算法用到的是剪枝法，最坏时间复杂度应该为o(m^n),考虑到实际约束条件和排好序的结果，程序不会每个点都运行到，所以时间会远小于上述值。 实验结果流程图示化展示(A-355,B-91),(A-355,C-308),(C-308,D-124),(B-91,G-162),(D-124,G-162), 第二组 (A-355,B-91),(A-355,C-308),(C-308,D-405),(C-308,E-420),(B-91,G-390),(D-405,G-390),(E-420,H-432),(G-390,K-89),(H-432,K-89) 第三组 (A-355,B-91),(A-355,C-308),(C-308,D-405),(C-308,E-420),(C-308,F-420),(B-91,G-390),(D-405,G-390),(E-420,H-454),(F-420,I-396),(F-420,J-79),(G-390,K-89),(H-454,K-89),(K-89,L-231),(I-396,L-231),(J-79,L-231) 第四组 (A-355,B-91),(A-355,C-308),(C-308,D-405),(C-308,E-420),(C-308,F-420),(B-91,G-390),(D-405,G-390),(E-420,H-454),(F-420,I-396),(F-420,J-311),(G-390,K-89),(H-454,K-89),(K-89,L-231),(I-396,L-231),(J-311,L-231),(G-390,M-444),(I-396,M-444),(M-444,N-256),(L-231,N-256), 需求 (0.9