序关系计数问题

序关系计数问题

时间: 1ms        内存:64M

描述:

用关系“<”和“=”将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<C<A,
B=C<A,C<A=B,C<A<B,C<B<A。
将n 个数(1≤n≤50)依序排列时有多少种序关系。
计算出将n个数(1 ≤ n ≤ 50)依序排列时有多少种序关系。

输入:

输入数据只有一行,提供一个数n。

输出:

输出数据只有一个整数,表示找到的序关系数。

示例输入:

3

示例输出:

13

提示:

参考答案(内存最优[1696]):

#include<cstdio>
#include<iostream>
using namespace std;
 
int main()
{
    long long int a[55][55];
    int n,i,j;
    while(cin>>n)
    {
    for(i=1;i<=n;i++)
        a[i][1]=1;
    a[1][2]=0;
    for(i=2;i<=n;i++)
    {
        for(j=2;j<=i;j++)
        {
            a[i][j]=j*(a[i-1][j-1]+a[i-1][j]);
        }
        a[i][i+1]=0;
    }
    long long int sum=0;
    for(i=1;i<=n;i++)
    {
        sum+=a[n][i];
    }
    printf("%lld\n",sum);
    }
    return 0;
}

参考答案(时间最优[0]):

#include<cstdio>
#include<iostream>
using namespace std;
 
int main()
{
    long long int a[55][55];
    int n,i,j;
    while(cin>>n)
    {
    for(i=1;i<=n;i++)
        a[i][1]=1;
    a[1][2]=0;
    for(i=2;i<=n;i++)
    {
        for(j=2;j<=i;j++)
        {
            a[i][j]=j*(a[i-1][j-1]+a[i-1][j]);
        }
        a[i][i+1]=0;
    }
    long long int sum=0;
    for(i=1;i<=n;i++)
    {
        sum+=a[n][i];
    }
    printf("%lld\n",sum);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注