《序关系计数问题》由会员分享，可在线阅读，更多相关《序关系计数问题（4页珍藏版）》请在金锄头文库上搜索。
1、题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 表中的序号，必须比等号后面的字母序号小
2、。基于这个思想，我们很容易写出解这道 题目的回溯算法：状态(Step, First, Can)：其中Step表示当前确定第Step个关系符号；First表示当 前大写字母中最小字母的序号；Can是一个集合，集合中的元素是还可以使用的大写字母序 号边界条件(step=n)：即确定了最后关系符号搜索范围(FirstWiWn)：枚举当前大写字母的序号约束条件(i in Can)：序号为i的大写字母可以使用 算法 1：procedure Count(Step ， First， Can)；从当前状态出发，递归计算序关系表达式数若确定了最后一个关系符号，则输出统beginif Step=n then be
3、gin计结果for i First to n do if i in Can then Inc(Total)；Exit回溯枚举当前的大序号为i的大写字母可添添end； then for iFirst to n do写字母if i in Can then begin以使用Count(Step+1， i+1， Can-i) ；等于号Count(Step+1， 1， Can-i) 小于号Endthenend； Count主程序调用Count(l, 1, l.n)后，Total的值就是结果。该算法的时间复杂度是W(n!)2、粗略利用信息算法 l 中存在大量冗余运算。如下图，三个方框内子树的形态完全一样。
4、一旦我们知 道了其中某一个方框内所产生的序关系数，就可以利用这个信息，直接得到另两个方框内将 要产生的序关系数。门弋时的解答树Rootpi J *J; J= J; J =J; J= =J; J =C C BC C BCCAAB B A显然，在枚举的过程中，若已经确定了前 k 个数，并且下一个关系符号是小于号，这 时所能产生的序关系数就是剩下的n-k个数所能产生的序关系数。设i个数共有Fi种不同的序关系，那么，由上面的讨论可知，在算法1中，调用一次 Count(Step+l, 1，Can-i)之后，Total的增量应该是Fn-Step。这个值可以在第一次调用 Count(Step+1，1, Ca
5、n-i)时求出。而一旦知道了 Fn-Step的值，就可以用 TotalTotal+Fn-Step 代替调用Count(Step+1， 1，Can-i)。这样，我们可以得到改进后的算法2。算法 2： procedure Count(Step， First， Can)；Step， First， Can 的含义同算法 1beginif Step=n then begin若确定了最后一个关系符号，则输出统计结果for iFirst to n do if i in Can then Inc(Total) ； Exit回溯end； thenfor iFirs t to n do枚举当前的大写字母ifiin
6、Can序号为 i 的大写字母可以使用then beginCount(Step+1， i+1， Can-i)；添AjV T. 口.等于号if Fn-Step=-1 then begin 第一次调用Fn-Step Total ；Count(Step+1，1，Can- i )；添小于号Fn-Step Total-Fn-StepFn-Step=Total的增量end thenelse TotalTotal+Fn-StepFn-Step已经求出endthenend ； count开始，将 F0, Fl,，Fn-1初始化为-1。调用 Count( 1,1, l.n)之后，Total 的值就是结果。算法2与
7、算法1 的差别仅限于程序中的粗体部分。算法2就是利用了 F0， F1,，Fn-1的值，使得在确定添小于号以后，能够避免多余的搜索，尽快地求出所需 要的方案数。该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为W(2n)。同 算法 1 相比，效率虽然有所提高，但仍不够理想。3、充分利用信息第一个小于号在第k个字母之后前k个字母由等于号连接继续搜索可以产生Fn-k个序关系数在搜索的过程中，如果确定在第k个大写字母之后添加第一个小于号，则可得到下面两条信 息：第一条信息：前k个大写字母都是用等号连接的。第二条信息：在此基础上继续搜索，将产生Fn-k个序关系表达式。如上图所示，序关系表达式中第
8、一个小于号将整个表达式分成了两个部分。由乘法原 理易知，上图所示的序关系表达式的总数，就是图中前半部分所能产生的序关系数，乘以后 半部分所能产生的序关系数。算法1-2实质上利用了第二条信息，直接得到图中后半部分将 产生Fn-k个序关系数，并通过搜索得到前半部分将产生的序关系数。但如果我们利用第一 条信息，就可以推知图中前半部分将产生的序关系数，就是n个物体中取k个的组合数，即Ck。这样，我们可以得到Fn的递推关系式：F n 工ckF n - k ，其中f 0 = 1 nnk 二 1 采用上述公式计算Fn的算法记为算法3,它的时间复杂度是W(n2)0 算法 3：varTotal：Comp ；答案
9、F： array 0. . maxn of Comp；Fi 为 i 个数的序关系表达式个数i， j： Integer；x： Comp；beginFillChar(F， Sizeof(F) ， 0) ；F初始化F0 T；for 1 to n do begin递推 F数组Fi -0；x 1； 计算for j 1 to i do beginFi计算 Cij Fi Fi+x*Fi-j输Endfor end ； for writeln(Fn) ； 出结果 end ； main在优化算法1的过程中，我们通过利用F0, Fl Fn-1的信息，得到算法2,时 间复杂度也从W(n!)降到W(2n)。在算法2中，进一步消除冗余运算，就得到了W(n2)的算法 3。算法3充分利用信息，通过两重循环的递推计算Fn,将时间复杂度降到W(n2),实现了 程序的最优性要求。
