天津做网站找津坤科技学校网站模板

  现在有28个小朋友，每个人手上有一把钥匙，每一个钥匙都只能打开自己的房间门，现在将所有钥匙都收上来，然后再随机打乱分给每个小朋友，也就是有28！的分法，请问现在其中14个小朋友的钥匙能恰好打开自己的房间门（其他14个小朋友不能打开自己的房间门的情况）有多少钟，答案直接返回一个结果数。

首先看到14个小朋友可以开自己的门，那么其实这就是组合问题，也就是C（14，28），然后14个小朋友不是对应的钥匙则是一个错排问题

假设错排函数是An，表示的含义是n个人都不对应自己的钥匙，则现在拿出其中一个小朋友i，单独讨论，假设已经确定i选择了3号的钥匙，那么对于3号小朋友来说如果他选择占用i的钥匙那么剩下的n-2把钥匙又就行An-2的讨论，如果他不选择占用i的位置那么问题就等同于1不拿1的钥匙，2不拿2的钥匙，3不拿i的钥匙，4不拿4的钥匙，以此类推也就是An-1。

用这个推理可以知道

An = C（1,n-1）*(An-2+An-1);

那么综合起来就是C（14，28）*A14。

现在问题来了要是我们按照组合的定义来实现C（14，28），则一定会在算的过程中爆掉，因为28的阶乘很大，然后我发现在这个题不知道是不是特意设置的数，边乘边除居然可以算出来了，但是不建议这样去写，玩意有数据改了中间会出现除不尽的结果，那么组合数就会出错，

最后就是把这两个算法实现了，代码很简单就不打了写一个求组合数的正确写法

for(int i=0;i<=28;i++){for(int j=0;j<=i;j++){if(j==0)c[i][j]=1;elsec[i][j] = c[i-1][j]+c[i-1][j-1];}
}//c[28][14]就是组合数结果