Handsshaking

handsshaking.png

n=8でありうるパターンを考えてみる

Exampleではn=8のとき14 と書いてある。

hands.png このパターンが4個
hands2.png このパターンが2個
hands3.png このパターンが8個

で、4+2+8=合計14個

規則を持った階差数列だ!という場合のソースコード

2個の時1通り
4個の時2通り
8個の時14通り

6個の時がわかれば階差数列になるかな?

public class HandsShaking {
    public long countPerfect(int n){
        long ans=1;
        if(n==2) return 1;
        int num=n/2-1;
        for(int i=0;i<=num;i++){
            ans+=Math.pow(3,i-1);
        }
        return ans;
    }
}

動的計画法で解く場合

動的計画法のメモ配列で、漸化式を計算することが出来ます。
0 1 2 3 4
1 1 0 0 0
0 1 2 3 4
1 1 2 0 0
0 1 2 3 4
1 1 2 5 0
0 1 2 3 4
1 1 2 5 14
public class HandsShaking {
    long[] mMemo;
    MarkDown mLog=new MarkDown();
    public long countPerfect(int n){
        long[] mMemo=new long[n/2+1];
        mMemo[0]=1;
        for(int i=1;i<=n/2;i++){
            mMemo[i]=0;
            for(int j=0;j<i;j++){
                mMemo[i]+=mMemo[j]*mMemo[i-j-1];
            }
            mLog.addln(mMemo);
        }
        return mMemo[n/2];
    }
}

catalan-number

サポートサイト Wikidot.com catalan-number