课程设计报告
课程设计题目: 神秘国度的爱情故事
学生姓名 谢良斌
学号 1224269809
专 业 软件工程 班
2014年 1月 5 日
级 1221809 指导教师李翔
东华理工大学 课程设计评分表
学生姓名: 谢良斌 班级:1221809 学号:201220180914 课程设计题目:神秘国度的爱情故事
一、 课程设计题目:神秘国度的爱情故事
二、 课程设计内容:
某个太空神秘国度中有很多美丽的小村,从太空中可以望见,小村间有路相连,更精确一点说,任意两村之问有且仅有一条路径。
小村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时,表示全部测试结束,不要对该数据做任何处理。
输出要求:对每一组测试给定的a、b、c,在一行里输出答案,即:如果c在a和b之间的路径上,输出“皇天不负有心人”,否则输出“白等”。
(边界测试数据说明:该输出里面有一组数据1 2 1,我们可看出a、c均为1,表明该年轻人住的村子与他等待的村子为同一个,有实际生活中我们可知道该年轻人一定能等到那位美丽姑娘。还有一组数据1 2 2,我们知道该年轻人等待的地方即是那位美丽姑娘工作的村子,由于题目要求该年轻人要在姑娘回家的路上等待,由于该年轻人在姑娘工作的村子等待,可知他一定等不到姑娘。)
下面为多个村子时的测试结果: