【题4】序关系计数问题.docVIP

【题4】序关系计数问题 用关系’’和’=’将3个数a、b和C依次排列有13种不同的关系： abC， ab=C， aCb， a=bC， a=b=C， a=Cb， baC， ba=C， bCa， b=Ca， Cab， Ca=b， Cba 输入n 输出n个数依序排列时有多少种关系。 1、枚举所有序关系表达式 我们可以采用回溯法枚举出所有的序关系表达式。n个数的序关系表达式，是通过n个大写字母和连接各字母的n-1个关系符号构成。依次枚举每个位置上的大写字母和关系符号，直到确定一个序关系表达式为止。 由于类似于‘a=b’和‘b=a’的序关系表达式是等价的，为此，规定等号前面的大写字母在aSCII表中的序号，必须比等号后面的字母序号小。基于这个思想，我们很容易写出解这道题目的回溯算法： 状态（Step，First，Can）：其中Step表示当前确定第Step个关系符号；First表示当前大写字母中最小字母的序号；Can是一个集合，集合中的元素是还可以使用的大写字母序号 边界条件（step=n）：即确定了最后关系符号 有哪些信誉好的足球投注网站范围（First≤i≤n）：枚举当前大写字母的序号 约束条件（i in Can）：序号为i的大写字母可以使用 算法1： procedure Count(Step，First，Can)； {从当前状态出发，递归计算序关系表达式数} begin if Step=n then begin {若确定了最后一个关系符号，则输出统计结果} for i←First to n do if i in Can then Inc(Total)； end；{then} for i←First to n do {枚举当前的大写字母} if i in Can then begin {序号为i的大写字母可以使用} Count(Step+1，i+1，Can-[i])； {添等于号} Count(Step+1，1，Can-[i]) {添小于号} End{then} end；{ Count} 主程序调用Count(1，1，[1..n])Total的值就是结果。该算法的时间复杂度是W(n!) 2、粗略利用信息 算法1中存在大量冗余运算。如下图，三个方框内子树的形态完全一样。一旦我们知道了其中某一个方框内所产生的序关系数，就可以利用这个信息，直接得到另两个方框内将要产生的序关系数。 显然，在枚举的过程中，若已经确定了前k个数，并且下一个关系符号是小于号，这时所能产生的序关系数就是剩下的n-k个数所能产生的序关系数。 设i个数共有F[i]种不同的序关系，那么，由上面的讨论可知，在算法1中，调用一次Count(Step+1，1，Can-[i])之后，Total的增量应该是F[n-Step]。这个值可以在第一次调用Count(Step+1，1，Can-[i])时求出。而一旦知道了F[n-Step]的值，就可以用Total←Total+F[n-Step] 代替调用Count(Step+1，1，Can-[i])。这样，我们可以得到改进后的算法2。 算法2： procedure Count(Step，First，Can)； {Step，First，Can if Step=n then begin {若确定了最后一个关系符号，则输出统计结果} for i←First to n do if i in Can then Inc(Total)； end；{then} for i←First to n do {枚举当前的大写字母} if i in Can {序号为i的大写字母可以使用} then begin Count(Step+1，i+1，Can-[i])； {添等于号} if F[n-Step]=-1 then begi