文档介绍：例4、单词游戏
有N个盘子,每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序,使得相邻两个盘子中,前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。请你判断是否能达到这一要求。如果能,请给出你的理由。
数据规模 1≤N≤100000
分析通过对题目条件的一些初步分析,我们很容易得到下面的模型。
模型1:以N个盘子作为顶点;如果盘子i的末字母等于盘子j的首字母,那么从顶点i向顶点j连一条有向边。
例如,对于分别写有acm, malform, mouse的 3个盘,按模型1可以将问题抽象为图1。
这样,问题转化为在图中寻找一条不重复地经过每一个顶点的路径,即哈密尔顿路。然而,求哈密尔顿路是一个十分困难的问题,这样的模型没有给我们的解题带来任何便利。因此,我们必须另辟蹊径。
acmm
malformm
mouse
模型2:经过分析,我们发现模型1的失败之处在于,图中需要遍历的信息——也就是每一个盘子——表示在顶点上,而顶点的遍历问题不易解决。能否将遍历信息表示在边上呢?
考虑如下的构图方法:以26个字母作为顶点;对于每一个盘子,如果它的首字母为c1,末字母为c2,那么从c1向c2连一条有向边。
对于上述样例我们可以按图2所示的方式构图,图中未表示出的顶点均为孤立点,可以事先将其删去。
这样,问题转化为在图中寻找一条不重复地经过每一条边的路径,即欧拉路径。这个问题能够在O(N)时间内解决。
acm
mouse
a
e
m
malform
单词游戏
有6个盘子,每个盘子上分别写着由小写字母组成的英文单词thinking, good, different, dad, dark, kind。试问是否存在一个合适的顺序安排这些盘子,使得相邻两个盘子中,前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。
单词游戏
thinking
good
different
dad
kind
dark
模型一
单词游戏
t
g
d
k
模型二
thinking
good
different
kind
dark
dad
小结比较以上两个模型,模型1非常直观,模型2的建立则需要一点逆向思维:我们已经****惯于“顶点表示元素,边表示元素之间的关系”这种先入为主的思想,而模型2则是反其道而行之——将元素表示在边上,而顶点则起到连接各个元素的作用。这说明,我们考虑问题时,必须将算法进行反复地推敲、改进,甚至打破旧的思维模式,大胆创新,才能找到解决问题的最佳方法。
在Brooks hear给出的机器中,地址00到07的内存单元中包含以下内容:
地址内容
00 10
01 05
02 11
03 05
04 B1
05 00
06 C0
07 00
若程序计数器置为00,程序是否会终止,为什么?
⑴从00开始,将00放入程序计数器中,开始运行程序;
⑵提取地址为00的指令(2个字节),并把指令(1005)存放到指令寄存器中,程序计数器+2;
⑶执行指令1005,通过总线,将05地址中的值00取出来,放到0号寄存器中;
⑷提取地址为02的指令,并把指令(1105)存放到指令寄存器中,程序计数器+2;
⑸执行指令