数据结构期末课程设计

题目要求：

2. 病毒肆虐 【问题描述】 蓝星上遇到了千年一遇的病毒肆虐，现在科学家们需要研制新型的疫苗来对抗这 一病毒的传播。在研制疫苗的过程中，病毒也在不断变异，现在需要你来参与研 究病毒变异和疫苗研制的工作。 现在把病毒的变异路线抽象为一棵树，由原始病毒开始变异，结点之间路径的权 重有三个，分别为病毒沿这一路径进行变异所需要的时间，科学家沿这一路径研 制疫苗所需要的时间以及在疫苗研制成功后病毒沿这一路径变异所需要的时间， 而每个变异体都有三个属性，分别是潜伏期、传染能力以及致死率，众所周知， 当病毒有超长潜伏期、超强传染能力以及极高致死率时，蓝星将面临灭顶之灾。

现在希望你能编写程序来完成任务。要求如下:

【基本要求】

1、给定两个病毒的编号，找出一个变异体，这个变异体是这两个病毒在分化之 前的最近公共祖先。

2、若科学家沿某一路径研制疫苗时间比病毒沿某一路径变异所需要的时间短， 则该病毒不会再进行变异。

3、假定所有变异和疫苗研究可以并行进行，即每种病毒在诞生后，经过相应时 间后会变异出其所有孩子结点的病毒(病毒会分头行动，并行变异)，假定研制疫 苗不一定需要这种病毒已经出现，请编写程序计算每种变异体的疫苗是否能在该 变异出现前研制成功，若不能，会落后多长时间。

4、对病毒在人群中的传播和变异进行一次沙箱模拟，以天为单位输出，以小时 为每一次迭代的粒度。规则如下：

(1)、潜伏期为整数，以天为单位。

(2)、传染能力为一个实数，即每个感染者每小时会传染多少易感者，为简化 问题，假定感染者之间互相传播也计算在内。

(3)、潜伏期的传染能力为爆发期的十分之一，爆发之后患者将被隔离，隔离 后将无法传染。爆发到隔离的时间由输入决定，为一个定值。

(4)、致死率为一个三元组，每个感染的人每小时状态会发生一次转移，分别 是康复、持续以及死亡，转移到持续状态的即为继续治疗状态，一小时后进行 下一次状态转移。

(5)、在某种病毒感染到达相应天数后，则相应感染人群携带的病毒即会有 1/k 的概率变异为对应的病毒，该天数包括潜伏期。例: 假若有一个病毒有三个变 异体，且每一个病毒需要不同的变异时长，若其中两个变异体变异所需时间较 短，另一个较长。在到达较短时间时，"对应的病毒"指这两个变异体中的一个， 每一个概率为 1/2；若三个变异体的变异时间都到达，"对应的病毒"指三个中 的其中一个，每一个概率为 1/3。K 会根据到达变异时间的变异体数决定。

(6)、感染孩子结点的病毒并康复后不会再次感染这种病毒及其所有祖先，但 是有可能感染除此以外的变异体。

(7)、bonus（选做）：加入疫苗的研制，当某种疫苗研制成功后，将不会再有人 感染相应病毒。 (8)、bonus（选做）：将沙箱进行分割，即存在多个沙箱，沙箱之间会有人员流 动，如每天随机交换 10%的人员，不同沙箱从爆发到隔离的时间不同。 请自行决定输入方式，以天为粒度输出每一天每种病毒的感染、康复以及死亡的 人数，感染可分为潜伏期、爆发期以及隔离救治期

完整的课程设计报告及代码：见上传资源 virus.zip

以下为代码设计流程图：