课程设计报告课程设计题目：神秘国度的爱情故事学生姓名谢良斌学号1224269809专业软件工程班级1221809指导教师李翔2014年1月5日东华理工大学课程设计评分表学生姓名：谢良斌班级：1221809学号：201220180914课程设计题目：神秘国度的爱情故事项目内容满分实评选题能结合所学课程知识、有一定的能力训练。符合选题要求（5人一题）10工作量适中，难易度合理10能力水平能熟练应用所学知识，有一定查阅文献及运用文献资料能力10理论依据充分，数据准确，公式推导正确10能应用计算机软件进行编程、资料搜集录入、加工、排版、制图等10能体现创造性思维，或有独特见解10成果质量总体设计正确、合理，各项技术指标符合要求。10说明书综述简练完整，概念清楚、立论正确、技术用语准确、结论严谨合理；分析处理科学、条理分明、语言流畅、结构严谨、版面清晰10设计说明书栏目齐全、合理，符号统一、编号齐全。格式、绘图、表格、插图等规范准确，符合国家标准10有一定篇幅，字符数不少于500010总分100指导教师评语：指导教师签名：年月日一、课程设计题目：神秘国度的爱情故事二、课程设计内容：某个太空神秘国度中有很多美丽的小村，从太空中可以望见，小村间有路相连，更精确一点说，任意两村之问有且仅有一条路径。小村A中有位年轻人爱上了自己村里的美丽姑娘。每天早晨，姑娘都要去小村B里的面包房工作，傍晚6点回到家。年轻人终于决定要向姑娘表白，他打算在小村C等着姑娘路过的时候把爱慕说出来。问题是，他不能确定小村C是否在小村B到小村A之间的路径上。你可以帮他解决这个问题吗?三、算法设计：我们能够注意到条件中有一条“任意两村之间有且仅有一条路径”，这表明这是一棵N个节点的树，每次查询给定点C是否在其余两点A、B之间的路径上。最直接的解法是沿着A、B点往上找，直到相遇或者碰到C，不过这样对于全部节点在一条线上的树，每次查询的复杂度是O(N)，肯定超时。仔细观察，我们可以发现如果点C在A、B之间的路径上，那么它满足下面这个有趣的规律：点C在A、B之间的路径上当且仅当C仅是A、B其中一个节点的祖先——除了一个非常特殊的情况，就是当C是A、B两点的最低公共祖先时，点C也在A、B的路径上（其实这道题的关键就是判断这个特殊情况）。因此，我们得到如下的算法：判断点C是否仅是其中一个节点的祖先。如果是，那么C肯定在路径上（那么就有该青年可以等到这位美丽姑娘）；否则，如果C是A、B两点的共同祖先，则判断C是否为最低公共祖先，如果是，那么C肯定在路径上（那么就有该青年可以等到这位美丽姑娘），否则C不在路径上（该青年不可以等到这位美丽姑娘）。那么现在剩下两个问题：（1）如何快速判断一个点是否是另外一个点的祖先？（2）如果C是A、B两点的共同祖先，如何快速判断它是否是最低的？对于第一个问题，我们可以用图的深度优先搜索遍历一边，记录每一个节点的入栈时间及出栈时间，然后判断其包含关系。对于每一棵深度优先搜索树我们规定每个节点左下角的数字表示第一次访问该节点即入栈时间，右下角的数字表示离开该节点即出栈时间。要判断点C是否是点A（B）的祖先，只要判断点C所在的入栈与出栈时间的区间是否包含了点A（B）所在的入栈与出栈时间的区间即可。对于第二个问题，要判断C是否是A和B的最低公共祖先，其实就是看是否有比C更低的祖先，如果有则说明C不是最低的。我们采取的方法是：如果我们从左到右依次列出C的儿子节点的入栈时间与出栈时间，我们不难发现这个区间数列是递增的！于是我们只要在这个递增的区间数列中二分查找是否有A、B所在的大区间即可！具体的程序算法如下面的源代码所示。四、程序正确性验证（指边界测试数据，即程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果）：输入要求：输入有若干组测试数据组成。每组数据的第1行包含一正整数N，代表神秘国度中小村的数目，每个小村即从1到N-1编号。接下来有N-1行输入，每行包含一条双向道路的两个端点小村的编号，中间用空格分开。之后一行包含一正整数M，代表着该组测试问题的个数。接下来M行，每行给出A、B、C三个小村的编号，中间用空格分开。当N为0...