信息学奥赛数学一本通__组合数学

问题描述:

设有n个边长为1的正立方体,在一个宽为1的轨道上堆塔,但塔本身不能分离。要求每一个方块下面必须有支撑。在这就不细说了,自己看一下书比什么都好。

分析:

问题一:求有多少种堆塔方案。这里用到了排列组合的知识,高中的就够。从每一列的角度看问题。第一列有x1个,第二列有x2个……以此类推。这样就可以写出一个方程x1+x2+……xk=n(设有k列吧),然后利用组合数的知识,正整数解有C(n-1,k-1);k就是共有k列的时候。只有第一列C(n-1,1-1),有两列C(n-1,2-1)……;再有二项式定理,共有2^(n-1)种情况;

问题二:求堆成k层的话,方案数是多少。这样考虑,堆成k层;忽略掉第一行(其实忽略哪一行都行,没啥区别)而后分为两种情况,第一种,第一行不够k层,则后面一定有k层的,f(n-i,k)(n-i是去掉第一行剩余的,k是堆成k层的,i从1-k);第二种情况是第一行是k层的,其余的随意摆放f(n-k,i)(i从1-k);递推求解就行了。

#include<bits/stdc++.h>
using namespace std;
long long int f[41][41],n;
int main(){
    cin>>n;
    long long total=1;
    for(int i=0;i< n-1;i++)
        total*=2;
    cout<<total<<endl;
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;i++){
            for(int k=1;k<j;k++)f[i][j]+=f[i-k][j];
            for(int k=0;k<=j;k++)f[i][j]+=f[i-j][k];
        }
    for(int i=1;i<=n;i++)
        cout<<f[n][i]<<endl;
    return 0;
}

发表评论

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