＋设为首页 ＋添加到收藏夹
用关系“〈“和”=“将3个数A，B和C依序排列时，有13种不同的序关系：
A=B=C，A=B〈C，A〈B=C，A〈B〈C，A〈C〈B
A=C〈B，B〈A=C，B〈A=C，B〈A〈C，B〈C〈A，B=C〈A
C〈A=B，C〈A〈B，C〈B〈A
若要将n个数依序进行排列，设计一个动态规划算法，计算出有多少种不同的序关系。要求算法只占用空间O，且只消耗O(n*n)。
shan
搬凳子，菜鸟能表示的只有关注，
有m个符号，n个数的计算公式是
n!*{m^(n-1)]
^_^
mark
3个数2种符号有3!*2!*2!种排列，减去第一个为＝号的3*2,在减去第二个为等号的3*2,在加上一个都为＝号的。
如果写程序，全部组合出来在慢慢判断，应该可以，我不会:(
刚才的公式错了，忘了等号的特殊性，即 a=b<c等同于b=a<c.
设
P(n,m)=n!/(n-m)! m个元素对n个位置的全排列
C(n,m)= n!/(n-m)!m! m个元素中选出n个元素
有m个符号(除等号外都不满足交换率），n个数的计算公式是
P(n,n)*[(m-1)^(n-1)]+∑[C(n-1,i)*C(n,i+1)*P(n-i-1,n-i-1)] (i=1...n-1)
当n=3,m=2时计算结果正好是13
^_^
