text.cpp

源代码用动态规划算法计算序列关系个数 用关系"<"和"="将3个数a

/*用关系"<"和"="将3个数a，b，c依次序排列时，有13种不同的序列关系：
a=b=c,a=b<c,a<b=v,a<b<c,a<c<b
a=c<b,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).

*/

#include <stdio.h>
long dyProgramming(long n)
{
long *ResultTemp = new long[n];
long dyProResult =0 ;
long i=0 , j=0 ;
for(i=0 ; i<n ; i++)
{
ResultTemp[i] = 0;
}
ResultTemp[0] = 1;
for(i=1 ; i<n ; i++)
{
long t1 = ResultTemp[0] , t2 = 0 ;
for(j=1 ; j<=i ; j++)
{
t2 = ResultTemp[j] ;
ResultTemp[j] = (t1 + t2) * (j+1);
t1 = t2 ;
}

}
for(i=0 ; i<n ; i++) dyProResult += ResultTemp[i];
delete ResultTemp;
return dyProResult;
}

int main(int argc, char* argv[])
{
int n;
for( n=1 ; n<11 ; n++)
{
printf("n=%d , result=%ld\n", n , dyProgramming(n));
}
return 0;
}