急求此题程序，献上100分

用关系“〈“和”=“将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（n），且只消耗O(n*n)。 问题点数：20、回复次数：7Top

1 楼CMyMfc（星际人生:=E.F=FlyForEver）回复于 2005-06-02 20:01:31 得分 1

shanTop

2 楼humanity（城市边缘的狼）回复于 2005-06-02 20:12:52 得分 1

搬凳子，菜鸟能表示的只有关注，Top

3 楼Dev（东方云龙）回复于 2005-06-02 21:11:15 得分 1

有m个符号，n个数的计算公式是    
  n!*{m^(n-1)]    
   
  ^_^Top

4 楼mostideal（三甲）回复于 2005-06-02 21:42:34 得分 1

markTop

5 楼ddc（ddc）回复于 2005-06-02 21:59:38 得分 5

3个数2种符号有3!*2!*2!种排列，减去第一个为＝号的3*2,在减去第二个为等号的3*2,在加上一个都为＝号的。  
  如果写程序，全部组合出来在慢慢判断，应该可以，我不会:(Top

6 楼Dev（东方云龙）回复于 2005-06-02 22:23:02 得分 11

刚才的公式错了，忘了等号的特殊性，即   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  
   
   
  ^_^  
  Top

7 楼antijpn（antijpn）回复于 2005-08-11 20:26:10 得分 0

作业，转新手乐园Top

相关问题

• 排列
• 个数
• 号
• 关系

• 帖主：tushuguanboy
• CMyMfc
• humanity
• Dev
• mostideal
• ddc
• Dev

• C/C++ Blog
• C/C++类图书
• C/C++类源码下载