order.cpp

编程计算出将n个数(1<=n<=50)依序排列时有多少种序关系.

////////////////////////////////////////////////////////////////////
//        当用j个"<"号来连接i个数时，具有下图所示的形式。         //
//                                                                //
//                 [    ]<[    ]< …… <[    ]                    //
//                   S1     S2           Sj+1                     //
//                                                                //
//        其中方框Sk，1≤k≤j+1中的各数用等号"="连接。            //
//        用A[i,j]表示用j个"<"号连接i个数时产生的不同             //
//        序关系数，当j>i-1时，A[i,j]=0，A[i,0]=1，i=1～n。       //
//        对于A[i,j]，在i-1个数的基础上增加一个数，新增加         //
//        的数可以在图中的j+1个框Si，i=1～j+1中任何一个           //
//        框内。当x∈Si，且i-1个数已有j个"<"号，此时产生          //
//        的不同的序关系为A[i-1,j]；当i-1个数时只有j-1个"<"       //
//        号时，Si={x}，且新赠一个"<"号，此时的不同序关系有       //
//        A[i-1,j-1]。因此，x∈Si时产生的不同序关系数为           //
//        A[i-1,j-1]+A[i-1,j]。由于x∈Si，1≤i≤j+1，共有j+1      //
//        种不同的情形，因此，产生的所有不同的序关系数为          //
//                                                                //
//                A[i,j]=(j+1)(A[i-1,j-1]+A[i-1,j])               //
//                                                                //
//        只要保存第i-1行的数据就可以了。                         //
//        (采用动态规划算法，算法只要O(n)空间和O(n2)计算时间)     //
////////////////////////////////////////////////////////////////////

#include<stdio.h>
#include<fstream.h>
#include "algorithm"


ofstream& operator<<(ofstream& out,__int64 i)      //重载运算符"<<"，实现64位整数的输出
{
	char buf[20];
	sprintf(buf,"%I64d",i);
	out<<buf;
	return out;
} 


__int64 ORDERINGS(int n)                           //采用动态规划算法，利用推导的公式
 {                                                 //A[i,j]=(j+1)(A[i-1,j-1]+A[i-1,j])求序关系数。
	 int j;
	 int i;
	 __int64 F;                                    //保存结果。
	 __int64* a=new __int64[n];
	 a[0]=1;                                       //用0个"<"号连接时，只有"="号连接，所以序关系只有1个，例如：a=b与b=a一样，只能算1个序关系。
	 for(j=1;j<n;j++) a[j]=0;                      //初始化都为0。
	 for(i=2;i<=n;i++)
		 for(j=i-1;j>0;j--)
			 a[j]=(j+1)*(a[j-1]+a[j]);             //利用推导的公式A[i,j]=(j+1)(A[i-1,j-1]+A[i-1,j])求序关系数，递归调用，只要用到i-1行的两个数据。
		 F=1;                                      //当j=0时，与a[0]=1同理。
		 for(j=1;j<n;j++)
			 F=F+a[j];
		 delete[] a;
		 return(F);
 }
 


void main()
{
	int n;
    __int64 result;
	ifstream input("input.txt");
    ofstream output("output.txt");
	input>>n;                                      //从文件读取n个数
	result=ORDERINGS(n);                           //调用函数，求序关系数
	output<<result;                                //向文件输出序关系总数
}