密码分析问题——2003年第12期题解

问题描述见杂志2003年第12期。算法分析首先,抓住问题的两个关键因素:“特征”和“特征串”。一个“特征”是由两个有序整数组成的,例如有“特征”(2,3),那么,在对应的“特征串”中必然存在连续的两个数 a_i=2和 a_(i+1)=3。现在我们不妨把每个自然数抽象成一个顶点,i 对应的顶点是 V_i;把每个特征抽象成一条弧,〈l,r〉对应的弧就是〈V_i,V_j〉。如图一所示,假设特征串是(1,2,3.4,3,5,6.2,5)。那么,图一中,每一条有向边所表示的正是特征串的一个“特征”。而对“特征串”来说,可以从图一中的1点出发,画出一条路径,每条边经过且只经过一次。